3. Задача линейного программирования. Симплекс – метод

Задачей линейного программирования называется задача оптимизации (максимизации или минимизации) линейной функции на полиэдре.

Общая задача линейного программирования имеет вид:

→ max (min)

(3.1)

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

1. Преобразование общей задачи к стандартному (каноническому) виду.

2. Нахождение опорного решения.

3. Оптимизация найденного решения.

На первом этапе общая задача преобразуется к виду:

→min (3.2)

При этом для перехода от задачи на минимум к задаче на максимум достаточно изменить на противоположные знаки в правой части целевой функции, то есть

Для перехода от неравенств к равенствам, перепишем, каждое из неравенств в виде

; s=1,…,k

и введем дополнительные переменные

; s=1,…,k

При этом, очевидно, что .

Если какая – либо переменная х_i может по условию задачи принимать не только положительные, но и отрицательные значения, то ее можно представить в виде разности дополнительных неотрицательных переменных , ; .

На втором этапе исследуется стандартная (каноническая) задача (3.2). В рассматриваемой задаче область допустимых значений будет существовать только в случае m<n (если m=n, то система линейно независимых уравнений имеет единственное решение, а при m>n система вообще не имеет решений). Следовательно, m переменных можно выразить через остальные.

(3.3)

Неизвестные х₁,…,х_m называются базисными, а неизвестные х_m+1, …, x_n – свободными. Очевидно, что система (3.3) имеет бесконечное число решений. Если положить все свободные неизвестные равными нулю, то базисные неизвестные будут равны свободным коэффициентам в равенствах (3.3),

х₁ =b^/₁,…, х_т= b^/_m , x_m+1 = …= x_n = 0.

Полученное решение называется базисным. При этом может оказаться, что некоторые b_i будут отрицательными, и полученное базисное решение не будет удовлетворять системе (3.2). Система (3.3) имеет базисных решений.

Базисное решение, у которого все значения х_i ≥ 0, называется опорным. Для нахождения опорного решения можно воспользоваться методом исключений Жордана- Гаусса.

Пусть система ограничений (3.2) записана в виде:

(3.4)

Такая система называется приведенной к единичному базису.

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

	х1	х2	…	хт	хт+1	…	хп	b	(3.5)
x1	1	0	…	0	d1m+1	…	d1n	b1
x2	0	1	…	0	d2m+1	…	d2n	b2
…	.	.	…	.	.	…	.	.
xm	0	0	…	1	dmm+1	…	dnn	bm

Символы в первом столбце указывают базисные неизвестные. Преобразуем таблицу (3.5) таким образом, чтобы все элементы последнего столбца стали неотрицательными. Для этого выберем среди всех строк с отрицательными b_i такую, у которой b_i наибольший по абсолютной величине. Пусть эта строка имеет номер s. Умножим эту строку на -1 и прибавим ко всем строкам, для которых b_i < 0. Тем самым получим новую таблицу, в которой все элементы последнего столбца будут неотрицательными. При этом в отличие от всех остальных уравнений системы s – e уравнение не будет разрешено относительно базисной неизвестной. Приведем систему к единичному базису, сохранив достигнутую неотрицательность последнего столбца. Для этого используем алгоритм симплексных преобразований таблиц, а именно:

1. Выбираем разрешающий столбец из условия, что элемент d_sp , расположенный на пересечении этого столбца и выбранной ранее s-ой строки был положительным. Если такого элемента не окажется, то система не имеет опорного решения.

2. Для всех положительных элементов b_iр выбранного р- го разрешающего столбца составляем отношения и выбираем l- ю разрешающую строку из условия минимума этого отношения. Элемент d_lp, расположенный на пересечении l-ой разрешающей строки и р-го разрешающего столбца, называется разрешающим или опорным элементом.

3. Разделим разрешающую строку на разрешающий элемент l, то есть произведем пересчет элементов l- й строки по формуле . В результате на пересечении разрешающей строки и разрешающего столбца будет единица.

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

При выполнении указанного алгоритма симплексных преобразований возможны три случая.

1. Разрешающий элемент d_lp, определенный в пункте 2 симплексного алгоритма, принадлежит выбранной s-ой строке, то есть l=s. Тогда после выполнения итерации симплексных преобразований система будет приведена к единичному базису и последний столбец, полученной таблицы будет описывать опорное решение.

2. Разрешающий элемент d_lp не принадлежит выбранной s- ой строке (l ≠ s). В этом случае проводится следующая итерация по описанному симплексному алгоритму.

3. При выполнении преобразований все элементы, какой- либо строки, за исключением последнего, окажутся не положительными, то есть d_ik ≤ 0, b_i > 0. Тогда система уравнений не имеет опорного решения.

Пусть опорное решение системы (3.2) найдено и х₁,…, х_т – базисные неизвестные, то есть х₁ = β₁, х₂ = β₂,…, х_т = β_т, х_т+1 = х_т+2 =…=х_п = 0.

В этом случае система (3.2) преобразуется в систему равенств

где β_i ≥ 0, i =1, …, m

Выразим целевую функцию z через свободные неизвестные. Тогда задача (3.1) запишется в виде:

z+ γ_m+1 x_m+1 + γ_m+2 x_m+2 + …+ γ_n x_n = γ₀ → max (3.6)

(3.7)

Для поиска оптимального решения задачи (3.6) с ограничениями (3.7) будем использовать симплекс-метод.

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

Составим симплекс – таблицу из коэффициентов системы (3.6) и (3.7) следующим образом: в первую строку запишем неизвестные, следующие т строк составляют коэффициенты системы (3.7), в последнюю строку записываем коэффициенты из равенства (3.6), называемые оценками. В первом столбце таблицы выписываем базисные неизвестные.

	х1	х2	…	хт	хт+1	…	хп		(3.8)
х1	1	0	…	0	α1т+1	…	α1п	β1
х2	0	1	…	0	α2т+1	…	α2п	β2
…	.	.	…	.	.	…	.
хт	0	0	…	1	αтт+1	…	amп	βт
z	0	0	…	0	γm+1	…	γn	γ0

Заметим, что последний столбец таблицы описывает опорное решение.

Для преобразования таблицы (3.8) используем алгоритм симплекс – метода.

1. Выбираем l-й разрешающий столбец из условия γ_l < 0 и хотя бы один элемент α_rl > 0.

2. Выбираем s- ю разрешающую строку из условия для всех α_rl > 0.

3. Производим пересечет элементов s-й строки по формуле , то есть все элементы разрешающей строки делим на разрешающий элемент, расположенный на пересечении s-й строки и l-го столбца.

4. Вычисляем элементы всех остальных строк по формуле α^/_rk = α_rk – α^/_sk α_rl. Полученные строки пишутся на месте прежних. При этом вместо х_s в символьной столбец таблицы пишется х_l.

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

Если после выполнения очередного шага:

а) найдется хотя бы одна отрицательная оценка в последней строке и в каждом столбце с такой оценкой окажется хотя бы один положительный элемент, то можно оптимизировать решение, выполнив следующий шаг;

б) найдется хотя бы одна отрицательная оценка, столбец которой не содержит положительных элементов, то функция z не ограничена в области допустимых решений, что означает отсутствие оптимального решения;

в) все оценки в последней строке окажутся неотрицательными, то получено оптимальное решение.

Если в некоторых уравнениях системы (3.7) свободные члены β_i = 0, соответствующие базисные неизвестные также равны нулю. В этом случае базисное решение называется вырожденным. При решении такой задачи симплексным методом на каком–либо шаге может получиться симплекс-таблица, идентичная одной из предыдущих, то есть может произойти зацикливание в схеме расчета. Для устранения зацикливания разрешающую строку выбирают в соответствии со следующим правилом.

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

Используем симплекс – метод для решения задачи.

Предприятию нужно перевезти по железной дороге изделия трех видов: изделий первого вида не более 273, изделий второго вида не более 300, изделий третьего вида не более 380. Подразделение железной дороги может выделить для этого вагоны двух видов А и В. Для полной загрузки вагона следует помещать в него изделия всех трех видов.

При этом в вагон типа А входят 3 изделия первого вида, 3 изделия второго вида и 2 изделия третьего вида. В вагон типа В входят 2 изделия первого вида, 3 изделия второго вида и 5 изделий третьего вида. Экономия от перевозки в вагоне типа А составляет 40 тысяч рублей, а в вагоне типа В – 50 тысяч рублей. Сколько вагонов каждого типа следует выделить для перевозки, чтобы суммарная экономия от перевозки груза была наибольшей?

Составим математическую модель задачи.

Обозначим за х₁ используемое число вагонов типа А, за х₂ - число вагонов типа В.

Целевая функция – суммарная экономия – имеет вид

z = 40х₁ + 50х₂ → mах

Ограничения записываются в виде неравенств

3х₁ + 2х₂ ≤ 273

3х₁ + 3х₂ ≤ 300 (3.9)

2х₁ + 5х₂ ≤ 380

х₁ ≥ 0; х₂ ≥ 0.

Преобразуем задачу к каноническому виду. Для этого введем новые неизвестные

х₃ = 273 – 3х₁ – 2х₂

х₄ = 300 – 3х₁ – 3х₂

х₅ = 380 – 2х₁ – 5х₂

Очевидно, что в силу (3.9) х₃ ≥ 0, х₄ ≥ 0; х₅ ≥ 0.

Соответствующая каноническая задача имеет вид

z- 40х₁ – 50х₂ = 0 → mах

3х₁+ 2х₂+ х₃ = 273

3х₁+ 3х₂+ х₄ = 300 (3.10)

2х₁+ 5х₂+ х₅ = 380

х_i ≥ 0, i= 1,…, 5

В системе (3.10) неизвестные х₃, х₄, х₅ выражаются через неизвестные х₁ и х₂, то есть получившаяся система уже приведена к единичному базису и х₃, х₄, х₅ – базисные неизвестные. Такой системе соответствует базисное решение х₁ = 0, х₂ = 0, х₃ = 273,

х₄ = 300, х₅ = 380. Все неизвестные неотрицательны, то есть базисное решение является опорным. Целевая функция z выражена через свободные неизвестные х₁ и х₂.

Составим симплекс- таблицу:

	х1	х2	х3	х4	х5
х1	3	2	1	0	0	273
х2	3	3	0	1	0	300
х3	2	5	0	0	1	380
z	-40	-50	0	0	0	0

В последней строке имеем две отрицательные оценки, следовательно, найденное опорное решение не оптимально. Применим симплексный алгоритм.

За разрешающий столбец выбираем первый. В этом столбце три положительных элемента 3, 3 и 2. Разделим на эти числа соответствующие свободные коэффициенты системы (3.10), записанные в последнем столбце таблицы. Имеем ; ;

. Наименьшее из полученных частных 91 соответствует первой строке, которую выбираем за разрешающую. Таким образом, разрешающий элемент расположен на пересечении первой строки и первого столбца и равен 3. Для составления следующей таблицы разделим элементы разрешающей строки на разрешающий элемент и полученную строку пишем на месте прежней. К каждой из остальных строк прибавляем (вычитаем) вновь полученную, умноженную на такое число, чтобы в клетках разрешающего столбца появились нули и пишем преобразованные строки на месте прежних. Новый базис составляют неизвестные х₁, х₄ и х₅.

	х1	х2	х3	х4	х5
х1	1	2/3	1/3	0	0	91
х4	0	1	-1	1	0	27
х5	0	11/3	-2/3	0	1	198
z	0	-70/3	40/3	0	0	3640

Полученной таблице соответствует опорное решение х₁ = 91, х₂ = 0, х₃ = 0,

х₄ = 27, х₅ = 198 и значение экономии z=3640 тысяч рублей. Последняя строка содержит отрицательную оценку во втором столбце, поэтому полученное решение не оптимально.

Выберем второй столбец за разрешающий. В этом столбце три положительных элемента. Разделим на них соответствующие элементы последнего столбца. Получаем 91: (2/3)=273/2, 27 : 1=27, 198: (11/3)=54. Следовательно, за разрешающую строку выбираем вторую. Повторяя описанную выше процедуру пересчета, получим новую симплекс – таблицу.

	х1	х2	х3	х4	х5
х1	1	0	1	-2/3	0	73
х2	0	1	-1	1	0	27
х5	0	0	3	-11/3	1	99
z	0	0	-10	70/3	0	4270

Получено новое опорное решение х₁ = 73, х₂ = 27, х₃ = 0, х₄ = 0, х₅ = 99 и z=4270 тысяч рублей.

Это решение не оптимальное, поскольку в последней строке имеется отрицательная оценка.

На следующем этапе за разрешающий столбец выбираем третий. Так как 73:1=73 и 99:3=33, за разрешающую строку выбираем третью. Применяя рассмотренный выше вычислительный алгоритм, получим

	х1	х2	х3	х4	х5
х1	1	0	0	5/9	-1/3	40
х2	0	1	0	-2/9	1/3	60
х3	0	0	1	-11/9	1/3	33
z	0	0	0	100/9	10/3	4600

В последней строке таблицы отрицательных оценок нет. Следовательно, эта таблица соответствует оптимальному решению х₁ = 40, х₂ = 60, х₃ = 33, х₄ = 0, х₅ = 0.

Таким образом, для оптимальной перевозки следует выделить 40 вагонов типа А и 60 вагонов типа В. При этом останутся на складе 33 изделия первого вида (х₃=33), а изделия второго и третьего видов будут перевезены полностью (х₄=0, х₅=0). Сумма экономии составит 4600 тысяч рублей.