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

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

Таблица 7

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

      Для определения остальных элементов  табл. 7 применяем правило треугольника. Эти элементы могут быть вычислены  и непосредственно по рекуррентным формулам.

      Вычислим  элементы табл. 7, стоящие в столбце  вектора Р₀. Первый из них находится в 1-й строке этого столбца. Для его вычисления находим три числа:

1) число, стоящее в табл. 6 на пересечении  столбца вектора Р₀ и 1-й строки (360);

2) число, стоящее в табл. 6 на пересечении столбца вектора P₃ и 1-й строки (12);

3) число, стоящее в табл. 7 на пересечении  столбца вектора Р₀ и 2-й строки (24).

      Вычитая из первого числа произведение двух других, находим искомый элемент: 360 – 12 х 24=72; записываем его в 1-й строке столбца вектора Р₀ табл. 7.

      Второй  элемент столбца вектора Р₀ табл. 7 был уже вычислен ранее. Для вычисления третьего элемента столбца вектора Р₀ также находим три числа. Первое из них (180) находится на пересечении 3-й строки и столбца вектора Р₀ табл. 6, второе (3) – на пересечении 3-й строки и столбца вектора P₃ табл. 6, третье (24) – на пересечении 2-й строки и столбца вектора Р₀ табл. 8. Итак, указанный элемент есть 180 – 24 х 3=108. Число 108 записываем в 3-й строке столбца вектора Р₀ табл. 7.

      Значение  F₀ в 4-й строке столбца этого же вектора можно найти двумя способами:

1) по формуле  , т.е.

2) по правилу треугольника; в данном  случае треугольник образован  числами 0, -16, 24. Этот способ приводит  к тому же результату: 0 - (-16) х 24=384.

      При определении по правилу треугольника элементов столбца вектора Р₀ третье число, стоящее в нижней вершине треугольника, все время оставалось неизменным и менялись лишь первые два числа. Учтем это при нахождении элементов столбца вектора P₁ табл. 7. Для вычисления указанных элементов первые два числа берем из столбцов векторов P₁ и Р₃ табл. 6, а третье число – из табл. 7. Это число стоит на пересечении 2-й строки и столбца вектора P₁ последней таблицы. В результате получаем значения искомых элементов: 18 – 12 х (3/4) =9; 5 – 3 х (3/4) = 11/4.

      Число в 4-й строке столбца вектора P₁ табл. 7 можно найти двумя способами:

1) по формуле Z₁-С₁=(C,P₁)-C₁ имеем

2) по правилу треугольника получим 

Аналогично  находим элементы столбца вектора  P₂.

      Элементы  столбца вектора Р₅ вычисляем по правилу треугольника. Однако построенные для определения этих элементов треугольники выглядят иначе.

      При вычислении элемента 1-й строки указанного столбца получается треугольник, образованный числами 0,12 и 1/8. Следовательно, искомый  элемент равен 0 – 12 х (1/8) = -3/2. Элемент, стоящий в 3-й строке данного столбца, равен 0 - 3 х (1 /8) = -3/8.

      По  окончании расчета всех элементов  табл. 7 в ней получены новый опорный  план и коэффициенты разложения векторов через базисные векторы P₄, P₃, P₆ и значения и . Как видно из этой таблицы, новым опорным планом задачи является план X=(0; 0; 24; 72; 0; 108). При данном плане производства изготовляется 24 изделия С и остается неиспользованным 72 кг сырья 1 вида и 108 кг сырья III вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора Р₀ табл. 7. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они претерпели значительные изменения. Изменились данные и других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмем данные столбца вектора Р₂. Число 1/2 во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий С, если запланировать выпуск одного изделия В. Числа 9 и 3/2 в 1-й и 3-й строках вектора P₂ показывают соответственно, сколько потребуется сырья I и II вида при включении в план производства одного изделия В, а число – 2 в 4-й строке показывает, что если будет запланирован выпуск одного изделия В, то это обеспечит увеличение выпуска продукции в стоимостном выражении на 2 руб. Иными словами, если включить в план производства продукции одно изделие В, то это потребует уменьшения выпуска изделия С на 1/2 ед. и потребует дополнительных затрат 9 кг сырья I вида и 3/2 кг сырья III вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастет на 2 руб. Таким образом, числа 9 и 3/2 выступают как бы новыми “нормами” затрат сырья I и III вида на изготовление одного изделия В (как видно из табл. 6, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий С.

      Такой же экономический смысл имеют  и данные столбца вектора Р₁ табл. 7. Несколько иное экономическое содержание имеют числа, записанные в столбце вектора Р₅. Число 1/8 во 2-й строке этого столбца, показывает, что увеличение объемов сырья II вида на 1 кг позволило бы увеличить выпуск изделий С на 1/8 ед. Одновременно потребовалось бы дополнительно 3/2 кг сырья I вида и 3/8 кг сырья III вида. Увеличение выпуска изделий С на 1/8 ед. приведет к росту выпуска продукции на 2 руб.

      Из  изложенного выше экономического содержания данных табл. 7 следует, что найденный  на II итерации план задачи не является оптимальным. Это видно и из 4-й  строки табл. 7, поскольку в столбце  вектора P₂ этой строки стоит отрицательное число – 2. Значит, в базис следует ввести вектор P₂, т. е. в новом плане следует предусмотреть выпуск изделий В. При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий В определяется для , т. е. находим

      Следовательно, исключению из базиса подлежит вектор Р₄ иными словами, выпуск изделий В ограничен имеющимся в распоряжении предприятия сырьем I вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить 8 изделий В. Число 9 является разрешающим элементом, а столбец вектора P₂ и 1-я строка табл. 7 являются направляющими. Составляем таблицу для III итерации (табл. 8).

Таблица 8

      В табл. 8 сначала заполняем элементы 1-й строки, которая представляет собой строку вновь вводимого  в базис вектора Р₂. Элементы этой строки получаем из элементов 1-й строки табл. 7 делением последних на разрешающий элемент (т.е. на 9). При этом в столбце С_б данной строки записываем .

      Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов. В результате в табл. 8 получаем новый  опорный план X=(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов через базисные векторы и соответствующие значения и

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

      Следовательно, план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 руб.

      Оптимальным планом производства продукции не предусматривается изготовление изделий А. Введение в план выпуска продукции изделий вида А привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки столбца вектора P₁, где число 5 показывает, что при данном плане включение в него выпуска единицы изделия А приводит лишь к уменьшению общей величины стоимости на 5 руб.

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

Таблица 9

Пример 10.

Найти максимум функции  при условиях

Решение. Систему уравнений задачи запишем в векторной форме:

где

Так как среди векторов имеется три единичных вектора, то для данной задачи можно непосредственно найти опорный план. Таковым является план Х=(0, 0, 20, 24; 0; 18). Составляем симплексную таблицу (табл. 10) и проверяем, является ли данный опорный план оптимальным.

Таблица 10

      Как видно из табл. 10, исходный опорный план не является оптимальным. Поэтому переходим к новому опорному плану. Это можно сделать, так как в столбцах векторов P₁ и p₅, 4-я строка которых содержит отрицательные числа, имеются положительные элементы. Для перехода к новому опорному плану введем в базис вектор p₅ и исключим из базиса вектор p₄. Составляем таблицу II итерации.

Таблица 11

      Как видно из табл. 11, новый опорный план задачи не является оптимальным, так как в 4-й строке столбца вектора P₁ стоит отрицательное число -11/3. Поскольку в столбце этого вектора нет положительных элементов, данная задача не имеет оптимального плана.  

ПРЯМАЯ  И  ДВОЙСТВЕННАЯ  ЗЛП.

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

(32)

при условиях

(33)

(34)

Определение 13.

Задача, состоящая в нахождении минимального значения функции

(35)

при условиях

(36)

(37)

называется  двойственной по отношению к задаче (32) – (34). Задачи (32) – (34) и (35) – (37) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) – на минимум. 

2. Матрица

(38)

составленная  из коэффициентов при неизвестных  в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица 

(39)

в двойственной задаче (35) – (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а  столбцов – строками).

3. Число переменных в двойственной  задаче (35) – (37) равно числу ограничений  в системе (33) исходной задачи (32) – (34), а число ограничений  в системе (36) двойственной задачи  – числу переменных в исходной  задаче.

4. Коэффициентами при неизвестных  в целевой функции (35) двойственной  задачи (35) – (37) являются свободные  члены в системе (33) исходной  задачи (32) – (34), а правыми частями  в соотношениях системы (36) двойственной  задачи – коэффициенты при  неизвестных в целевой функции  (32) исходной задачи.