С помощью симплекс-метода
Симплекс-метод предназначен для решения канонической задачи линейного программирования.
Итак, рассмотрим задачу линейного программирования с ограничениями в форме уравнений. Дана система ограничений
(3.25)
, 
(3.26)
и целевая функция
. (3.27)
Для начала работы по симплекс-методу требуется, чтобы заданная система уравнений была приведена к допустимому виду. Это означает, что какие-то из неизвестных должны быть выражены через остальные, причем свободные члены этих выражений неотрицательны.
Пример 3.6. Рассмотрим пример допустимой системы:
Здесь свободные члены равны соответственно 3, 4, 0.
После того как выделен допустимый базис неизвестных, можно в выражении для целевой функции заменить каждое базисное неизвестное его выражением через свободные неизвестные.
Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать.
Пусть требуется найти максимальное значение функции
при условиях
(3.28)
.
Здесь 
, 
и 
(i=1,2,…,m; j=1,2,…,n) – заданные постоянные числа, причем 
и >0.
Векторная форма данной задачи имеет следующий вид: найти максимум функции
при условиях
, (3.29)
где
, 
,…, 
,
,…, 
, 
.
Т.к. 
то план X=( 
, 0, …, 0) является опорным планом данной задачи. Этот план определяется системой единичных векторов 
, которые образуют базис m-мерного пространства. Поэтому каждый из векторов 
, а также вектор 
могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть
(j=0, 1,…,n).
Положим 
; 
.
Т.к. векторы P1, P2,…, Pm – единичные, то 
и 
, а 
.
Теорема 3.2 (признак оптимальности опорного плана). Опорный план X=( 
, 0, …, 0) является оптимальным, если 
для любого j (j=1, 2,…, n).
Замечание. Если требуется найти минимальное значение, которое принимает целевая функция, то опорный план X=( , 0, …, 0) будет являться оптимальным, если 
для любого j (j=1, 2,…, n).
Теорема 3.3.Если 
для некоторого j=k и среди чисел 
нет положительных, то целевая функция не ограничена на множестве ее планов.
Замечание.В задаче на минимум если 
для некоторого j=k и среди чисел 
нет положительных, то целевая функция не ограничена на множестве ее планов.
Теорема 3.4.Если опорный план X не вырожден и 
, но среди чисел есть положительные, то существует опорный план X* такой, что 
.
Замечание. В задаче на отыскание минимального значения целевой функции если опорный план X не вырожден и , но среди чисел есть положительные, то существует опорный план X* такой, что 
.
Сформулированные теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.
Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если условия задачи и первоначальные данные, полученные после определения исходного опорного плана, записать так, как показано в таблице 3.5.
Таблица 3.5. Симплекс-таблица
| i | Базис | 
|
| 
| 
| … | 
| … | 
| 
| … | 
| … | 
|
| 
| … | 
| … | 
| 
| … | 
| … | 
| ||||
| 1 |
|
| 
| … | … | 
| … | 
| ... | 
| ||||
| 2 |
|
| 
| … | … | 
| … | 
| … | 
| ||||
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| r |
|
| 
| … | … | 
| … | 
| … | 
| ||||
| … | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
| m |
|
| 
| … | … | 
| … | 
| … | 
| ||||
| m+1 | 
| 
| … | … | 
| … | 
| … | 
|
В таблице 3.5 первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора 
-значение .
Значение 
находится как скалярное произведение вектора (j=1,2,…,m) на вектор 
:
.
Значение z0 равно скалярному произведению вектора P0 на вектор :
.
После заполнения таблицы 3.5 исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки таблицы. В результате может иметь место один из следующих трех случаев:
1) для j=m+1, m+2,…,n (j=1,2,…,m, 
). Поэтому в данном случае числа для всех j от 1 до n;
2) 
<0 для некоторого j, и все соответствующие этому индексу величины 
(i=1,2,…,m);
3) 
<0 для некоторых индексов j, и для каждого такого j по крайней мере одно из чисел положительно.
В первом случае на основании признака оптимальности исходный опорный план является оптимальным. Во втором случае целевая функция не ограничена сверху на множестве планов, а в третьем случае можно перейти от исходного плана к новому опорному плану, при котором значение целевой функции увеличится. Этот переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вектора, вводимого в базис, можно взять любой из векторов , имеющий индекс j, для которого <0. Пусть, например, 
<0 и решено ввести в базис вектор .
Для определения вектора, подлежащего исключению из базиса, находят 
для всех >0. Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор , а число 
называют разрешающим элементом.
Замечание. C целью упрощения вычислительного процесса в дальнейшем будем вектор, вводимый в базис, определять, исходя из максимальной абсолютной величины отрицательных чисел 
. Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же индекс, как и максимальное из чисел , определяемых данными числами ( <0).
Столбец и строку, на пересечении которых находится разрешающий элемент, называют направляющими.
После выделения направляющей строки и направляющего столбца находят новый опорный план и коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану. Это легко реализовать, если воспользоваться методом Жордана - Гаусса.
После вычисления 
и 
их значения заносят в следующую таблицу (II итерация).
После заполнения новой симплекс-таблицы просматривают элементы (m+1) - й строки. Если все 
, то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то находят новый опорный план. Этот процесс продолжают до тех нор, пока либо не получают оптимальный план задачи, либо не устанавливают ее неразрешимость.
Пример 3.7. Для изготовления различных изделий А, В и С предприятие использует три различных вида сырья. Нормы расхода сырья на производство одного изделия каждого вида, цена одного изделия А, В и С, а также общее количество сырья каждого вида, которое может быть использовано предприятием, приведены в таблице 3.6.
Таблица 3.6. Исходные данные для примера 3.7
| Вид сырья | Нормы затрат сырья (кг) на одно изделие | Общее количество сырья (кг) | ||
| A | В | С | ||
| I | ||||
| II | ||||
| III | ||||
| Цена одного изделия (руб.) |
Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида.
Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной.
Решение. Составим математическую модель задачи. Искомый выпуск изделий А обозначим через 
, изделий В - через 
, изделий С - через 
. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные , , должны удовлетворять следующей системе неравенств:
(3.30)
Общая стоимость произведенной предприятием продукции при условии выпуска изделий А, изделий В и изделий С составляет
. (3.31)
По своему экономическому содержанию переменные , , могут принимать только лишь неотрицательные значения:
(3.32)
Таким образом, приходим к следующей математической задаче: среди всех неотрицательных решений системы неравенств (3.30) требуется найти такое, при котором функция (3.31) принимает максимальное значение.
Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений
Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства количество сырья того или иного вида. Например, 
- это неиспользуемое количество сырья I вида.
Преобразованную систему уравнений запишем в векторной форме:
где
, 
, 
, 
, 
, 
, 
.
Поскольку среди данных векторов имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план X=(0; 0; 0; 400; 120; 160), определяемый системой трехмерных единичных векторов 
, которые образуют базис трехмерного векторного пространства.
Составляем симплексную таблицу (таблица 3.7), подсчитываем значения , и проверяем исходный опорный план на оптимальность:
= 
; 
= 
;
= 
;
= 
;
; 
; 
.
Для векторов базиса =0.
Таблица 3.7. Первая симплекс-таблица для примера 3.7
| i | Базис |
| 
| 21 | 42 | 25 | 0 | 0 | 0 |
|
|
| 
| 
| 
| 
| ||||
| 1 |
| ||||||||
| 2 |
| ||||||||
| 3 |
| 40 | |||||||
| 4 |
| -21 | -42 | -25 |
Согласно данным таблицы 3.7, значения всех основных переменных , , равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Эти значения переменных отвечают такому «плану», при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т.е. стоимость произведенной продукции отсутствует).
Данный план не является оптимальным, т.к. в 4-й строке таблицы 3.7 имеется три отрицательных числа: -21, -42, -25. Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции.
Так, число -21 означает, что при включении в план производства одного изделия А обеспечивается увеличение выпуска продукции на 21 руб. Если включить в план производства по одному изделию В и С, то общая стоимость изготовляемой продукции возрастет соответственно на 42 и 25 руб. Поэтому с экономической точки зрения наиболее целесообразным является включение в план производства изделий В. Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число стоит в 4-й строке столбца вектора . Следовательно, в базис введем вектор . Определяем вектор, подлежащий исключению из базиса. Для этого находим θ0= 
для 
, т. е. θ0=min(400/10; 120/20; 160/40)=160/40=4.
Найдя число 160/40=4, мы тем самым с экономической точки зрения определили, какое количество изделий В предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида. Так как сырья данного вида соответственно имеется 400, 120 и 160 кг, а на одно изделие В требуется затратить сырья каждого вида соответственно 10, 20 и 40 кг, то максимальное число изделии В, которое может быть изготовлено предприятием, равно θ0=min(400/10; 120/20; 160/40)=160/40=4, т.е. ограничивающим фактором для производства изделий В является имеющийся объем сырья III вида. С учетом его наличия предприятие может изготовить 4 изделия В. При этом сырье III вида будет полностью использовано.
Следовательно, вектор подлежит исключению из базиса. Столбец вектора и 3-я строка являются направляющими. Составляем вторую симплкс-таблицу (таблица 3.8).
Таблица 3.8. Вторая симплекс-таблица для примера 3.7
| i | Базис |
|
| 21 | 42 | 25 | 0 | 0 | 0 |
|
|
|
|
|
|
| ||||
| 1 |
| 35/2 | -1/4 | ||||||
| 2 |
| 7 | -1/2 | ||||||
| 3 |
| 1/4 | 2/5 | 1/40 | |||||
| 4 |
| -21/2 | -41/5 | 21/20 |
Сначала заполняем строку вектора, вновь введенного в базис, т. е. строку, номер которой совпадает с номером направляющей строки. Здесь направляющей является 3-я строка. Элементы этой строки таблицы 3.8 получаются из соответствующих элементов таблицы 3.7 делением их на разрешающий элемент (т.е. на 40). При этом в столбце записываем коэффициент 
, стоящий в столбце вводимого в базис вектора .
Для определения остальных элементов таблицы 3.8 применяем метод исключения неизвестных Жордана-Гаусса. Затем заполняем 4-ю строку таблицы.
По окончании расчета всех элементов таблицы 3.8 в ней получены новый опорный план и коэффициенты разложения векторов (j=1,2,…,6) через базисные векторы 
и значения 
и 
. Новым опорным планом задачи является план X=(0; 4; 0; 360; 40; 0). При данном плане производства изготовляется 4 изделия В и остается неиспользованным 360 кг сырья I вида и 40 кг сырья II вида. Стоимость всей производимой при этом плане продукции равна 168 руб. Указанные числа записаны в столбце вектора P0 таблицы 3.8. Возьмем данные столбца вектора . Число 1/4 в 3-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий В, если запланировать выпуск одного изделия А. Числа 35/2 и 7 в 1-й и 2-й строках вектора показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия А, а число -21/2 в 4-й строке показывает, что если будет запланирован выпуск одного изделия А, то это обеспечит увеличение выпуска продукции в стоимостном выражении на 21/2 руб. Иными словами, если включить в план производства продукции одно изделие А, то это потребует уменьшения выпуска изделия В на 1/4 ед. и потребует дополнительных затрат 35/2 кг сырья I вида и 7 кг сырья II вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастет на 21/2 руб. Таким образом, числа 35/2 и 7 выступают как бы новыми «нормами» затрат сырья I и II вида на изготовление одного изделия А (как показано в таблице 3.7, ранее они были равны 20 и 12), что объясняется уменьшением выпуска изделий В.
Такой же экономический смысл имеют и данные столбца вектора таблицы 3.8. Несколько иное экономическое содержание имеют числа, записанные в столбце вектора . Число 1/40 в 3-й строке этого столбца, показывает, что увеличение объемов сырья III вида на 1 кг позволило бы увеличить выпуск изделий В па 1/40 ед. Одновременно потребовалось бы дополнительно 1/4 кг сырья I вида и 1/2 кг сырья II вида. Увеличение выпуска изделий В на 1/40 ед. приведет к росту выпуска продукции на 21/20 руб.
Из изложенного выше экономического содержания данных таблицы 3.8 следует, что найденный на II итерации план задачи не является оптимальным. Об этом можно судить и по 4-й строке таблицы 3.8, поскольку в столбце вектора этой строки стоит отрицательное число -21/2. Значит, в базис следует ввести вектор , т. е. в новом плане следует предусмотреть выпуск изделий А. При определении возможного числа изготовления изделий А следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделии А определяется min ( 
), т. е. находим
θ0=min (360/(35/2); 40/7; 4/(1/4))=40/7.
Следовательно, исключению из базиса подлежит вектор , иными словами, выпуск изделий А ограничен имеющимся в распоряжении предприятия сырьем II вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить 40/7 изделий А. Число 7 является разрешающим элементом, а столбец вектора и 2-я строка таблицы 3.8 являются направляющими. Составляем третью симплекс-таблицу:
Таблица 3.9. Третья симплекс-таблица для примера 3.7
| i | Базис |
|
| 21 | 42 | 25 | 0 | 0 | 0 |
|
|
|
|
|
|
| ||||
| 1 |
| -19 | -5/2 | ||||||
| 2 |
| 40/7 | 22/7 | 1/7 | -1/14 | ||||
| 3 |
| 18/7 | -27/70 | -1/28 | 3/70 | ||||
| 4 |
| 124/5 | 3/2 | 3/10 |
В результате в таблице 3.9 получаем новый опорный план X=(40/7; 18/7; 0; 260; 0; 0) и коэффициенты разложения векторов (j=1,2,…,6) через базисные векторы 
и соответствующие значения 
и 
.
Т.к. в 4-ой строке таблицы 3.9 нет отрицательных чисел, то найденный опорный план является оптимальным и 
.
Следовательно, план выпуска продукции, включающий изготовление 40/7 изделий А и 18/7 изделии В, является оптимальным. При данном плане выпуска изделий полностью используется сырье II и III видов и остается неиспользованным 260 кг сырья I вида, а стоимость производимой продукции равна 228 руб.
Таблица 3.10. Сводная симплекс-таблица для примера 3.7
| i | Базис |
|
| 21 | 42 | 25 | 0 | 0 | 0 |
|
|
|
|
|
|
| ||||
| 1 |
| ||||||||
| 2 |
| ||||||||
| 3 |
| ||||||||
| 4 |
| -21 | -42 | -25 | |||||
| 1 |
| 35/2 | -1/4 | ||||||
| 2 |
| -1/2 | |||||||
| 3 |
| 1/4 | 2/5 | 1/40 | |||||
| 4 |
| -21/2 | -41/5 | 21/20 | |||||
| 1 |
| -19 | -5/2 | ||||||
| 2 |
| 40/7 | 22/7 | 1/7 | -1/14 | ||||
| 3 |
| 18/7 | -27/70 | -1/28 | 3/70 | ||||
| 4 |
| 124/5 | 3/2 | 3/10 |
Оптимальным планом производства продукции не предусматривается изготовление изделии С. Введение в план выпуска продукции изделий вида С привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки таблицы 3.9 столбца вектора , где число 124/5 показывает, что при данном плане включение в него выпуска единицы изделия С приводит лишь к уменьшению общей величины стоимости на 124/5 руб.
Решение данного примера можно было бы проводить, используя лишь одну симплекс-таблицу (таблица 3.10), в которой последовательно записаны одна за другой все три итерации вычислительного процесса.
Пример 3.8.Найти максимум функции 
при условиях
xj 
( j=1,2,…,6).
Решение. Систему уравнений запишем в векторной форме:
где
, 
, 
, 
, 
, , 
.
Так как среди векторов 
имеется три единичных вектора, то для данной задачи можно непосредственно найти опорный план. Таковым является план Х=(0; 0; 20; 24; 0; 18). Составляем симплексную таблицу 3.11 и проверяем, является ли данный опорный план оптимальным.
На основе данных таблицы 3.11 делаем вывод, что исходный опорный план не является оптимальным. Поэтому переходим к новому опорному плану. Это можно сделать, так как в столбцах векторов и 4-я строка которых содержит отрицательные числа, имеются положительные элементы.
Таблица 3.11. Первая симплекс-таблица для примера 3.8
| i | Базис |
|
| 2 | -6 | 0 | 0 | 5 | 0 |
|
|
|
|
|
|
| ||||
| 1 |
| -2 | |||||||
| 2 |
| -1 | -2 | ||||||
| 3 |
| -1 | -12 | ||||||
| 4 |
| -2 | -5 |
Для перехода к новому опорному плану введем в базис вектор и исключим из базиса вектор . Составляем таблицу II итерации.
Таблица 3.12. Вторая симплекс-таблица для примера 3.8
| i | Базис |
|
| 2 | -6 | 0 | 0 | 5 | 0 |
|
|
|
|
|
|
| ||||
| 1 |
| -5/3 | 5/3 | -1/3 | |||||
| 2 |
| -1/3 | -2/3 | 1/3 | |||||
| 3 |
| -1 | -9 | ||||||
| 4 |
| -11/3 | 8/3 | 5/3 |
Согласно данным таблицы 3.12, новый опорный план задачи не является оптимальным, так как в 4-й строке столбца вектора стоит отрицательное число -11/3. Поскольку в столбце этого вектора нет положительных элементов, данная задача не имеет оптимального плана.
Пример 3.9. Решим с помощью симплексного метода следующую задачу линейного программирования.
Найти минимальное значение линейной функции
при ограничениях
(j=1,2,3).
Решение. Первоначальный опорный план рассмотренным методом находится сразу только при неотрицательных правых частях системы ограничений, поэтому умножим второе неравенство на (-1):
(j=1,2,3).
Перейдем от неравенств к равенствам, прибавляя к левым частям неотрицательные дополнительные переменные (напомним, что дополнительным переменным в линейной функции соответствуют коэффициенты, равные нулю):
(j=1,2,…,6).
Запишем систему в векторной форме:
где
, 
, 
, , , , 
.
Единичные векторы выберем за базис первоначального опорного плана, свободные неизвестные 
приравниваем нулю. В результате получим первоначальный опорный план X=(0; 0; 0; 1; 2; 5).
Для проверки данного плана на оптимальность составляем первую симплексную таблицу (таблица 3.13) и подсчитываем значение и оценок . Имеем: =0; 
; 
; 
.
Для векторов базиса оценки равны нулю. Среди полученных оценок имеются две положительные: 
=1>0; 
=3>0. Это означает, что первоначальный опорный план не является оптимальным и его можно улучшить, включив в базис вектор , которому соответствует наибольшая положительная оценка (3).
Таблица 3.13. Первая симплекс-таблица для примера 3.9
| i | Базис |
|
| 1 | -1 | -3 | 0 | 0 | 0 |
|
|
|
|
|
|
| ||||
| 1 |
| -1 | |||||||
| 2 |
| -4 | -1 | ||||||
| 3 |
| ||||||||
| 4 |
| -1 |
Для того, чтобы определить какой вектор нужно исключить из базиса, найдем θ0=min (1/1; 5/1)=1/1=1. Таким образом, разрешающим элементом является число 1, стоящее на пересечении первой строки и третьего столбца, первая строка и третий столбец являются направляющими; необходимо вектор включить в базис, а вектор исключить.
Составим вторую симплексную таблицу (таблица 3.14).
Таблица 3.14. Вторая симплекс-таблица для примера 3.9
| i | Базис |
|
| 1 | -1 | -3 | 0 | 0 | 0 |
|
|
|
|
|
|
| ||||
| 1 |
| -3 | -1 | ||||||
| 2 |
| -2 | |||||||
| 3 |
| -1 | |||||||
| 4 |
| -3 | -7 | -3 |
Подсчитаем новые элементы направляющей строки. Для этого старые элементы направляющей строки разделим на разрешающий элемент (на 1) и с помощью этой строки произведем одно преобразование по методу полных исключений, т. е. сложим со второй строкой, вычтем из третьей, умножим на 3 и вычтем из 4-й строки. В результате получим все элементы таблицы 3.14.
В данной таблице получен второй опорный план Х=(0; 0; 1; 0; 3; 4), которому соответствует значение линейной функции 
.
В 4-й строке =3+1=4>0, значит, план не является оптимальным и вектор подлежит включению в базис.
Определяем θ0=min (3/1; 4/1)=3/1=3. Число 1, стоящее на пересечении второго столбца и второй строки, является разрешающим элементом, вектор исключается из базиса. Составляем таблицу, в которой в последней итерации получен оптимальный план (таблица 3.15).
Так как в 4-й строке четвертой итерации все оценки неположительные, то план Х=(1/3; 11/3; 4; 0; 0; 0) является оптимальным и ему соответствует 
. На основании оценок в 4-й cтроке можно заключить, что оптимальный план для данной задачи является единственным, так как нулевые оценки соответствуют только векторам, входящим в базис.
Таблица 3.15. Симплекс-таблица III и IV итерации для примера 3.9