Симплексный метод

новой симплекс-таблицы;

2. число, стоящее в исходной симплекс-таблице на пересечении строки, в

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

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

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

    После заполнения новой симплекс-таблицы  просматривают элементы (m+1)-й строки. Если все , то новый опорный план является оптимальным. Если же среди указанных чисел имеются отрицательные, то, используя описанную выше последовательность действий, находят новый опорный план. Этот процесс продолжают до тех пор, пока либо не получают оптимальный план задачи, либо не устанавливают ее неразрешимость.

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

    Итак, нахождение оптимального плана симплексным  методом включает следующие этапы:

1. Находят опорный план.
2. Составляют симплекс-таблицу.
3. Выясняют, имеется ли хотя бы одно отрицательное число . Если нет, то

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

4. Находят направляющие столбец и строку. Направляющий столбец определяется

наибольшим  по абсолютной величине отрицательным  числом , а направляющая строка - минимальным из отношений компонент столбца вектора Р₀ к положительным компонентам направляющего столбца.

5. По формулам (2.38) — (2.41) определяют положительные компоненты нового опорного плана, коэффициенты разложения векторов Р_j по векторам нового базиса и числа , . Все эти числа записываются в новой симплекс-таблице.
6. Проверяют найденный опорный план на оптимальность. Если план не оптимален и необходимо перейти к новому опорному плану, то возвращаются к этапу 4, а в случае получения оптимального плана или установления неразрешимости процесс решения задачи заканчивают.

    Пример.

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

Таблица 2.4

 

    Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но производство ограничено выделенным предприятию сырьем каждого вида.

    Составить план производства изделий, при котором  общая стоимость всей произведенной предприятием продукции является максимальной.

    Решение. Составим математическую модель задачи. Искомый выпуск изделий А обозначим через х₁, изделий В - через х₂, изделий С - через х₃. Поскольку имеются ограничения на выделенный предприятию фонд сырья каждого вида, переменные х₁, х₂, и х₃ должны удовлетворять следующей системе неравенств:

 (2.42)

    Общая стоимость произведенной предприятием продукции при условии выпуска  х₁ изделий А, х₂ изделий В и х₃ изделий С составляет:

     . (2.43)

    По  своему экономическому содержанию переменные х₁, х₂, и х₃ могут принимать только лишь неотрицательные значения:

    х₁, х₂, х₃ ≥ 0. (2.44)

    Таким образом, приходом к следующей математической задаче: среди всех неотрицательных решений системы неравенств (2.42) требуется найти такое, при котором функция (2.43) принимает максимальное значение.

    Запишем эту задачу в форме основной задачи линейного программирования. Для  этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в  результате чего ограничения запишутся в виде системы уравнений:

    Эти дополнительные переменные по экономическому смыслу означают не используемое при  данном плане производства количество сырья того или иного вида. Например, х₄ - это неиспользуемое количество сырья 1 вида.

    Преобразованную систему уравнений запишем в  векторной форме:

,

где ; ; ; ; ; ; .

    Поскольку среди векторов Р₁, Р₂, Р₃, Р₄, Р₅, Р₆ имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план Х=(0; 0; 0, 360; 192; 180), определяемый системой трехмерных единичных Р₄, Р₅, Р₆, которые образуют базис трехмерного векторного пространства.

    Составляем  симплексную таблицу для 1 итерации (табл.5), подсчитываем значения F₀, z_j - c_j, и проверяем исходный опорный план на оптимальность:

F₀=(С, Р₀)=0; z₁=(С, Р₁)=0;  z₂=(С, Р₂)=0;  z₃=(С, Р₃)=0;

z₁ - c₁= 0 - 9= - 9;  z₂ - c₂ = 0 - 10 = - 10;  z₃ - c₃ = - 16.

    Для векторов базиса z_j - c_j = 0. 

Таблица 2.5

 

    Как видно из табл. 2.5, значения всех основных переменных х₁, х₂, и х₃ равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Эти значения переменных отвечают такому «плану», при котором ничего не производится, сырье не используется и значение левой функции равно нулю (т. е. стоимость произведенной продукции отсутствует). Этот план, конечно, не является оптимальным.

    Это видно и из 4-й строки табл. 2.5, так как в ней имеется три отрицательных числа: z₁-c₁=  - 9, z₂-c₂= - 10, z₃-c₃= - 16. Отрицательные числа не только свидетельствуют о возможности увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или другого вида продукции.

    Так, число -9 означает, что при включении  в план производства одного изделия  А обеспечивает увеличение выпуска  на 9 руб. Если включить в план производства по одному изделию В и С, то общая  стоимость изготовленной продукции  возрастает соответственно на 10 и 16 руб. Поэтому с экономической точки зрения наиболее целесообразным является включение в план производства изделий С. Это же необходимо сделать и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное число стоит в 4-й строке столбца вектора Р₃. Следовательно, в базис введем вектор Р₃. Определяем вектор, подлежащий исключению из базиса. Для этого находим для a_i3>0, т. е. .

    Найдя число 192/8=24, мы тем самым с экономической  точки зрения определили, какое количество изделий С предприятие может изготовлять с учетом норм расхода и имеющихся объемов сырья каждого вида. Так как сырья данного вида соответственно имеется 360, 192 и 180 кг, а на одно изделие С требуется затратить сырья каждого вида соответственно 12, 8 и З кг, то максимальное число изделий С, которое может быть изготовлено предприятием, равно min(360/12; 192/8; 180/3) = 192/8=24, т. е. ограничивающим фактором для производства изделий С является имеющийся объем сырья 2 вида. С учетом его наличия предприятие может изготовить 24 изделия С. При этом сырье 2 вида будет полностью использовано.

    Следовательно, вектор Р₅ подлежит исключению из базиса. Столбец вектора Р₃ и 2-я строка являются направляющими. Составляем таблицу для 2 итерации (табл. 2.6)  
 
 
 
 

Таблица 2.6