Линейное программирование

1) для j=m+1, (при ). Поэтому в данном случае числа для всех j от 1 до n;

2) для некоторого j, и все соответствующие этому индексу величины

3) для некоторых индексов j, и для каждого такого j , по крайней мере, одно из чисел положительно.

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

      Для определения вектора, подлежащего  исключению из базиса, находят  для всех Пусть этот минимум достигается при i=r. Тогда из базиса исключают вектор , а число называют разрешающим элементом.

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

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

(25)

а коэффициенты разложения векторов через векторы нового базиса, соответствующего новому опорному плану, – по формулам

(26)

      После вычисления и согласно формулам (25) и (26) их значения заносят в табл. 4. Элементы -й строки этой таблицы могут быть вычислены либо по формулам

(27)

(28)

либо  на основании их определения.

Таблица 3

Таблица 4

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

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

      Итак, переход от одного опорного плана  к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы  можно вычислить как с помощью  рекуррентных формул (25)-(28), так и  по правилам, непосредственно вытекающим из них. Эти правила состоят в  следующем.

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

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

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

      1) число, стоящее в исходной симплекс-таблице  на месте искомого элемента  новой симплекс-таблицы;

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

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

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

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

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

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

1. Находят опорный план.

2. Составляют симплекс-таблицу.

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

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

5. По формулам (25) – (28) определяют  положительные компоненты нового  опорного плана, коэффициенты  разложения векторов Pj по векторам нового базиса и числа , . Все эти числа записываются в новой симплекс-таблице.

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

Пример 9.

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

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

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

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

(29)

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

(30)

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

(31)

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

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

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

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

где

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

      Составляем  симплексную таблицу для I итерации (табл. 6), подсчитываем значения и проверяем исходный опорный план на оптимальность:

Для векторов базиса

Таблица 6

      Как видно из таблицы 6, значения всех основных переменных равны нулю, а дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Эти значения переменных отвечают такому “плану”, при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т. е. стоимость произведенной продукции отсутствует). Этот план, конечно, не является оптимальным.

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

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

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