Решение задачи симплексным методом

Рассмотрим алгоритм симплексного метода на примере задачи, которая была решена графическим способом.

Запишем условия задачи в канонической форме:

x₁+x₂+x₃=5;

30x₁+150x₂+x₄=300;

x₁ 0, x₂ 0, x₃ 0, x₄ 0

при целевой функции Z_max = 4x₁+10x₂+0x₃+0x₄. Переменные х₁ и х₂, которые фигурировали в системе до приведения ее в каноническую форму, называют основными переменными задачи. В канонической форме эта система состоит из двух уравнений с четырьмя пере­менными. Переменные х₃ и х₄ называются дополнительными. Они обозначают недоиспользование ресурсов (пашни и труда). Такая система, как известно, является неоп­ределенной и имеет бесконечное множество решений.

Рассмотрим решение системы. Вначале выпишем коэффициенты при неизвестных (а_ij) и свободные члены (b_i) в виде матрицы:

x₁ x₂ x₃ x₄ b_i

1 1 1 0 5

30 150 0 1 300

Коэффициен­ты при дополнительных переменных образуют подмат­рицу, по главной диагонали которой стоят единицы; та­кую матрицу называют единичной.

Набор k переменных, коэффициенты которых обра­зуют единичную матрицу, называют базисом k-мерного векторного пространства, соответствующие им перемен­ные - базисными переменными, остальные – свободными.

В общем случае, если система в канонической фор­ме содержит n переменных и m уравнений, то n - m = s являются свободными переменными. В рассматри­ваемом примере две свободные переменные (4-2 = 2). Чтобы решить систему, нужно задать свободным пе­ременным некоторое произвольное значение. Обычно их принимают равными нулю.

В рассматриваемой системе базисными переменны­ми являются х₃, х₄.. Если свободные переменные х₁ и х₂ приравнять к нулю, то решением системы будет: х₃ = 5; x₄ = 300; (при x₁ = 0 и х₂ = 0). Сле­довательно, решением системы является матрица-стол­бец свободных членов, и при этом все переменные не­отрицательны (х_j 0). Решение, где все переменные не­отрицательны, называют допустимым. Такое решение, полученное приравниванием свободных переменных ну­лю, называют опорным (базисным) решением или опор­ным планом. Оптимальный вариант плана обязательно находится в числе допустимых решений.

Хотя задача линейного программирования имеет большое количество допустимых решений, число базисных решений ограничено. Это позволяет выбирать оптимальный вариант из сравнительно небольшого числа решений. Опорные решения геометрически соответствуют только вершинам выпуклого многогранника.

Схема поиска оптимального плана строится так: сначала определяют некоторый опорный план (как правило, он оказывается неоптимальным); найденный план проверяется на оптимальность. Если опорный план оказался неоптимальным, вычисляется другой, лучший, который снова проверяется на оптимальность, и т. д. до получения оптимального варианта.

Симплексным методом предусмотрена такая схема расчетов, когда на каждом новом этапе план улучшается. Поэтому он называется также методом последовательного улучшения плана.

Нахождение первого опорного плана. Приступая к решению задачи, в качестве базисных переменных берут дополнительные переменные (х₃, х₄,) , а в качестве свободных – основные переменные (х₁, х₂), т.е. те, которые были в системе до приведения ее в каноническую форму. Затем, приравняв нулю свободные переменные х₁ = 0 и х₂ = 0, получают первое опорное решение. Для этого выразим базисные переменные через ободные – преобразуем исходные уравнения так, чтобы в правой части были только свободные переменные:

х₃ = 5 – х₁ – х₂; х₄ = 300 – 30х₁ – 150х₂ .

Подставляя в уравнения нулевые значения свободных переменных (х₁=0 и х₂=0), получим первое опорное решение: х₃ =5; х₄ =300. Полученный вариант плана формально является допустимым (все х_j 0), но экономически он неприемлем, так как площади зерновых культур и сахарной свеклы равны нулю, продукция не производится, а целевая функция равна нулю. Равенство дополнительных переменных свободным членам уравнений показывает, что наличные ресурсы не используются.

Экономический смысл дополнительных переменных состоит в следующем. Записывая ограничение по пашне в виде нестрогого неравенства х₁+х₂ 5, допускались следующие два случая: а) вся пашня будет использована, тогда х₁+х₂=5 (и х₃ =0); б) если при сложившихся ус­ловиях хозяйству невыгодно использовать всю пашню, т.е. х₁+х₂<5 (и х₃>0), то в этом случае х₃ показывает неиспользуемую часть паш­ни. Переменная х₄ отра­жает неиспользованную часть ресурсов труда. Неисполь­зуемые ресурсы не могут увеличивать значение целевой функции. Поэтому коэффициенты при допол­нительных переменных в целевой функции равны нулю. Развернутая форма записи целевой функции представ­ляется так: Z_max = 4x₁+10x₂+ 0х₃+ 0x₄.

Поскольку полученный опорный план не является оптимальным (в дальнейшем будет введен формальный признак оптимальности), его нужно улучшить.

Улучшение первого опорного плана. Чтобы произвес­ти продукцию (и соответственно увеличить Z), очевид­но, необходимо ввести в число базисных переменных ту, которая обеспечивает наибольший прирост целевой функции Z.

Поскольку наибольший коэффициент в це­левой функции при х₂, введем ее в базис. Соответствен­но, одну из переменных нужно вывести из базиса.

Чтобы возраста­ла целевая функция Z, нужно увеличить х₂. Но нельзя увеличивать эту переменную безгранично, так как она связана с другими переменными. Если х₂ придать очень большое значение, то другие переменные могут стать отрицательными, что недопустимо по условиям задачи. Предельно допустимое значение х₂ можно определить, вычислив так называемые симплексные отношения. Они получаются делением свободного члена каждого урав­нения (в канонической записи) на положительный ко­эффициент при вводимой в базис переменной (т.е. при х₂):

или (5; 2).

Минимальное симплексное отношение (2) пока­зывает, что необходимо выводить из базиса в число свободных переменных х₄ из второго уравнения. На втором этапе расчетов базисными переменными будут х₂, х₃, а свободными - пере­менные х₁и х₄.

Далее снова базисные переменные выражают через свободные, и расчеты, аналогично изложенным выше, повторяют до тех пор, пока возможно увеличение значе­ния целевой функции. Однако поиск оптимального пла­на методом логических рассуждений и путем преобра­зований системы исходных уравнений громоздок и не­удобен, хотя и важен для понимания существа метода. Схема расчетов может быть формализована в ви­де строгого и более простого алгоритма. Наиболее удоб­но вести решение задачи с использованием специальных так называемых симплексных табли­ц.

Построение макета и заполнение первой симплексной таблицы. Первая симплексная таблица представляет форму выражения опорного плана, когда свободные пе­ременные равны нулю, ресурсы не используются и Z=0. Поэтому при заполнении первой таблицы допол­нительные переменные считаются базисными (x₃, х₄), аосновные переменные (х₁, х₂)– свободными. Каждая строка таблицы отражает соответствующее уравнение системы в канонической форме, хотя столбцы распола­гаются в иной последовательности, чем достигаются оп­ределенные технические удобства в расчетах. Располо­жение переменных показано в таблице 4.

Таблица 4 – Первая симплексная таблица

	cj
сi	П Б	b0	x1	x2	x3	x4	co
	x3
	x4						2
	j		-4	-10

В первом столбце записываются коэффициенты це­левой функции с_j для базисных переменных х₃, х₄.В первом опорном решении все они равны нулю. Во втором столбце перечислены буквенные сим­волы базисных переменных (х₃, х₄) и Z. В первой верх­ней строке таблицы приводятся коэффициенты целевой функции с_j при всех переменных.

Во вторую строку записываются буквенные символы всех переменных, причем свободные члены указывают­ся в начале ряда и обозначаются b_io. Третья и четвертая строки таблицы заполнены коэффициентами соответствующих уравнений систе­мы, то есть представляют собой ее матрицу, включая единичную подматрицу.

Расположение базисных переменных и свободных членов в рядом стоящих столбцах таблицы позволяет легко читать результат опорного решения при равенстве свободных переменных нулю.

Последняя строка таблицы называется оценочной (или индексной) и содержит оценочные коэффициенты переменных ( _j).

Для х₁ оценка равна:

₁=(0 1+0 30) – 4 = -4;

для х₂: ₂= (0 1 +0 150) – 10 = - 10;

для х₃ и х₄: ₃ = 0; ₄ = 0.

Полученные величины занесем в последнюю строку симплексной таблицы.

Последняя строка таблицы соответст­вует записи приведенной формулы целевой функции, когда все члены с неизвестными перенесены в левую часть уравнения:

Z – 4х₁ – 10х₂ – 0х₃ – 0х₄ = 0.

Таким образом, первая симплексная таблица (соот­ветственно и полученное опорное решение) получается непосредственно из канонической формы записи системы.

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

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

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

Столбец, содержащий переменную, которую нужно ввести в базис, называют разрешающим столбцом (k-столбец). В первой симплексной таб­лице разрешающим является столбец х₂ (k=2) .

Если в оценочной строке окажется несколько оди­наковых минимальных значений, то в качестве разре­шающего выбирается столбец с наименьшим номером.

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

Рассчитаем по симплексной таблице от­ношения b_io:a_ik и найдем из них минимальное. По строке х₃ находим: 5/1=5; по строке x₄: 300/150 = 2.

Определяем минимальное значение из полученных от­ношений:

min = min {5; 2} = 2.

Минимальное симплексное отношение находится в строке x₄ (r = 4). На пере­сечении разрешающей строки r и разрешающего столб­ца k, находится разрешающий элемент (а_ik) = 150. Разрешающую строку и разрешающий столбец в симп­лексной таблице выделяют жирными линиями.

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

Элементы разрешающей строки делятся на разрешающий элемент и получают строку для таблицы 5 с новыми значениями элементов.

Таблица 5 – Вторая симплексная таблица

	cj
сi	П Б	b0	x1	x2	x3	x4	co
	x3		4/5			-1/150	3
	x2		1/5			1/150
	j		-2			1/15

Длястолбца b_io имеем 300:150=2,0; для столбца х₁ ответственно 30: 150=0,2. По разрешающему столбцу получим а_rk =1 и т. д.

Все остальные элементы таблицы (включая и оценки) пересчитывают по правилу «прямоугольника»:

= .

Для столбца b_io по строке х₃ получим:

5 - = 3;

для оценочной строки:

0 - = 20.

Новые элементы столбца х₁ по строке х₃:

1 - = 0,8;

для индексной строки:

- 4 - = -2.

Поскольку в разрешающей строке элемент равен 0 (а₂₃ = 0), то числитель дроби и вся дробь равна 0, а элементы столбца х₃ можно переписать в новую таблицу без изменений.

Столбец х₄:

=0 - =-1/150;

0 - =1/15.

Элементы оценочной (индексной) строки можно вычислить и по формуле, используемой для расчетов в таблице 4.

В оценочной (индексной) строке имеется отрицательный элемент (-2 по столбцу х₁).Следовательно, план не является оптимальным. Поэтому столбец х₁ в следующей таблице рассматривается как разрешающий, апеременную х₁ вводят в базис.

Рассчитаем ивпишем в таблицу 5 значения симплексных отношений (столбец СО). По строке х₃:

=3,75;

по строке х₂:

=10.

Разрешающей является строка х₃,так как ми­нимальное значение СО наблюдается по этой строке:

min = min {3,75; 10} =3,75.

Таблица 6 – Третья симплексная таблица (с оптимальным планом)

	cj
сi	П Б	b0	x1	x2	x3	x4
	х1	3			1	-1/120
	х2	1			-1/4	1/120
	j	27,5			2,5	1/20

Результаты расчетов приведены в таблице 6.

В третьей (последней) симплексной таблице нет ни одного от­рицательного коэффициента индексной строки. Следовательно, получен оптимальный план. В соответствии с данными таблицы 6, значения базисных переменных, выписанные из столб­ца b_io, равны:

х₁= 3,75; х₂=1,25.

Согласно оптимальному плану, 3,75 га пашни сле­дует занять зерновыми культурами и 1,25 га – сахарной свеклой. Следовательно, вся пашня и трудовые ресурсы будут использованы полностью. Максимальная стоимость товарной продукции равна 27500 руб.