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

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

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

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

1. число, стоящее в табл. 2.5 на пересечении столбца вектора Р₀ и 1-й строки (360);
2. число, стоящее в табл. 2.5 на пересечении столбца вектора Р₃ и 1-й строки (12);
3. число, стоящее в табл. 2.6 на пересечении столбца вектора Р₀ и 2-й строки (24).

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

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

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

1. по формуле F₀=(С, Р₀), т. е. F₀=0*72+ I6*24+0*108 =384;

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

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

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

1. по формуле z₁-c₁ = (С, Р₁)-c₁ имеем 0*9+16*3/4+0*11/4-9=3;
2. по правилу треугольника получим -9-(-16)*(3/4)=3.

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

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

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

    По  окончании расчета всех элементов табл. 2.6 в ней получится новый опорный план и коэффициенты разложения векторов Р_j ( ) через базисные векторы Р₄, Р₃, Р₆ и значения ∆’_j и F’₀. Как видно из этой таблицы, новым опорным планам задачи является план Х= (0; 0; 24; 72; 0; 108). При данном плане производства изготовляется 24 изделия С и остается неиспользованным 72 кг сырья 1 вида и 108 кг сырья 3 вида. Стоимость всей производимой при этом плане продукции равна 384 руб. Указанные числа записаны в столбце вектора Р₀ табл. 2.6. Как видно, данные этого столбца по-прежнему представляют собой параметры рассматриваемой задачи, хотя они претерпели значительные изменения. Изменились данные и других столбцов, а их экономическое содержание стало более сложным. Так, например, возьмем данные столбца вектора Р₂. Число 1/2 во 2-й строке этого столбца показывает, на сколько следует уменьшить изготовление изделий С, если запланировать выпуск одного изделия B. Числа 9 и 3/2 в 1-й и 3-й строках вектора Р₂, показывают соответственно, сколько потребуется сырья 1 и 2 вида при включении в план производства одного изделия В, а число -2 в 4-й строке показывает, что если будет запланирован выпуск изделия В, то это обеспечит увеличение выпуска продукции в стоимостном выражении на 2 руб. Иными словами, если включить в план производства продукции одно изделие В, то это потребует уменьшения выпуска изделия С на 1/2 ед. и потребует дополнительных затрат 9 кг сырья 1 вида и 3/2 кг сырья 3 вида, а общая стоимость изготовляемой продукции в соответствии с новым оптимальным планом возрастет на 2 руб. Таким образом, числа 9 и 3/2 выступают как бы новыми «нормами» затрат сырья 1 и 3 вида на изготовление одного изделия B (как видно из табл. 2.5, ранее они были равны 15 и 3), что объясняется уменьшением выпуска изделий С.

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

    Из  изложенного выше экономического содержания данных табл. 2.6 следует, что найденный на 2 итерации план задачи не является оптимальным. Это видно и из 4-й строки табл. 2.6, поскольку в столбце вектора Р₂ этой строки стоит отрицательное число -2. Значит, в базис следует ввести вектор Р₂, т. е. в новом плане следует предусмотреть выпуск изделий В. При определении возможного числа изготовления изделий В следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий B определяется min(b’_i /a’_i2) для a’_i2>0, т. е. находим

θ₀=min(72/9; 24*2/1; 108*2/3)=72/9=8.

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

Таблица 2.7

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

    Затем заполняем элементы столбцов векторов базиса и по правилу треугольника вычисляем элементы остальных столбцов. В результате в табл. 2.7 получаем новый опорный план Х== (0;8; 20; 0; 0; 96) и коэффициенты разложения векторов Р_j , ( ) через базисные векторы Р₂, Р₃, Р₆ и соответствующие значения ∆’’_j и F’’₀.

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

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

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

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

Таблица 2.8