Общая характеристика симплекс метода

Симплекс метод - это универсальный метод для решения линейных систем уравнений или неравенств и линейного функционала [25].

Общая идея симплекс метода для решения ЗЛП (задачи линейного программирования) состоит в:

- умении находить начальный опорный план;

- наличии признака оптимальности опорного плана;

- умении переходить к нехудшему опорному плану.

Пусть ЗЛП представлена системой ограничений в каноническом виде:

.

Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.

Пусть система ограничений имеет вид

Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные . Получим систему, эквивалентную исходной:

,

которая имеет предпочтительный вид

.

В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю .

Пусть далее система ограничений имеет вид

Сведём её к эквивалентной вычитанием дополнительных переменных из левых частей неравенств системы. Получим систему

Однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные

входят в левую часть (при ) с коэффициентами, равными –1. Поэтому, вообще говоря, базисный план

не является допустимым. В этом случае вводится так называемый искусственный базис. К левым частям ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные . В целевую функцию переменные , вводят с коэффициентом М в случае решения задачи на минимум и с коэффициентом -М для задачи на максимум, где М - большое положительное число. Полученная задача называется М-задачей, соответствующей исходной. Она всегда имеет предпочтительный вид.

Пусть исходная ЗЛП имеет вид

(2.1)

(2.2)

(2.3)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

Экологические заметки

Роль экотоксиканта никеля в экологии сегодня и его эволюционное влияние в далеком прошлом
Многие ученые (профессор-окулист З.Ф. Веселовская, иммунологи и др.) связывают тенденции роста частоты случаев некоторых неинфекционных заболеваний человека с глобальным ухудшением ...

Состояние природной среды Смоленской области и ее охрана
Несмотря на спад производства и осуществление ряда мер как на федеральном, так и на региональном уровнях, экологическая обстановка в наиболее населенных и промышленно-развитых рай ...

Человек и биосфера как объекты синергетической философии
Биосферой называется оболочка Земли, населенная и активно преобразуемая живыми существами. В.И. Вернадский определял биосферу, как оболочку, в которой существует или существовала в ...