Метод искусственного базиса

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

a_i1 X₁ + a_i2 X₂ +…a_in X _n ≥ b_i (7)

или уравнений a_i1 X₁ + a_i2 X₂ +…a_in X _n = b_i (7*),

то невозможно получить опорный план в искомом виде. В этом случае для соблюдения равенств (7*) вводится искусственный базис Y_i, причем искусственные переменные не имеют непосредственного отношения к содержанию поставленной задачи, но позволяют построить опорный (стартовый) план:

a_i1 X₁ + a_i2 X₂ +…a_in X _n +Y_i = b_i (8).

Целевая функция при решении задачи на максимум запишется в виде:

Z(X) =∑C_jX_j+(-M)∑Y_i (9),

при решении аналогичной задач на минимум:

Z(X)=∑C_jX_j+(M)∑Y_i (9*),

где М – очень большое положительное число, своего рода штраф за использование искусственных переменных.

В случае неравенств (7) первоначально вводим дополнительные переменные Х_n+i со знаком минус. Их матрица не будет единичной, поэтому в каждое неравенство системы (7) вводим искусственные переменные У_i:

a_i1X₁+a_i2X₂+…a_inX_n–X_n+i+Y_i=b_i (10) Целевая функция при этом Z(X)=∑C_jX_j+0∑X_n+i+(-M)∑Y_i (для нахождения максимума). Применение искусственного базиса придает симплексному методу большую гибкость и позволяет использовать его для широкого круга задач.

Пример №4.

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

Математически ограничения выпуска продукции запишутся в виде смешанной системы:

1Х₁ + 1Х₂≤ 6,

2Х₁ + 1Х₂ =8.

Введем для первого неравенства базисную переменную Х₃, а для второго уравнения искусственную переменную Y₁:

1Х₁ + 1Х₂+ Х₃ = 6,

2Х₁ + 1Х₂ +Y₁ =8.

Выразим из полученной системы уравнений Х₃ и Y₁ и для определения максимума целевую функцию представим:

Z(X)= 3X₁+ 2X₂+0X₃ –MY₁= 3X₁+ 2X₂ –M(8 -2X₁ –X₂)=

= 3X₁+ 2X₂ –8M +2MX₁ + MX₂ = (2M + 3)X₁ + (M + 2)X₂ -8M

Для опорного плана - Х=(0,0,6,8). Построим симплексную таблицу:

Как правило, улучшение опорного плана начинается с выведения из базиса искусственной переменной Y₁.Оптимальный план Х=(2,4,0,0) получен на второй итерации, при этом доход максимален 14тыс. руб., а коэффициенты индексной строки неотрицательны. Легко убедиться, что в данной задаче при оптимальном плане ресурсы использованы полностью (2*1+4*1=6; 2*2+1*4=8).

При нахождении минимальной доходности иначе формулируем целевую функцию (в качестве слагаемого вводится +MY₁:

Z(X)= 3X₁+ 2X₂+0X₃ +MY₁= 3X₁+ 2X₂ +M(8 -2X₁ –X₂)=

= 3X₁+ 2X₂ +8M - 2MX₁ - MX₂ = (3 - 2M)X₁ + (2 - M)X₂ +8M

Опорный план тот же, но коэффициенты индексной строки в симплексной таблице иные. Ведущий столбец, по-прежнему, выбираем по наибольшему по абсолютному значению положительному коэффициенту при X_1, ведущая строка определяется по минимальному значению Q_min=4.При первой итерации из базиса выводится искусственная переменная Y₁.

Полученные отрицательные значения коэффициентов в индексной строке X_i свидетельствуют об оптимальности 1-ого плана, при этом минимальный доход 12 тыс. рублей.

Он обеспечивается только выпуском продукции А (продукция В не выпускается), сырье не используется полностью (остаток Х₃=2т), при этом выполнено основное условие - рабочие полностью заняты на производстве.

Пример №5.

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

Математически ограничения выпуска продукции запишутся в виде системы неравенств:

3X₁ + 2X₂ ≤ 12,

X₁ + X₂ ≥ 5.

Введем для первого неравенства базисную переменную Х₃, а для второго уравнения отрицательную Х₄ и искусственную переменную Y₁:

3X₁ + 2X₂ + X₃ = 12,

X₁ + X₂ – X₄ + Y₁ = 5.

Выразим из полученной системы уравнений Х₃ и Y₁ и для определения максимума целевую функцию представим:

Z(X) = 2X₁+ 1X₂+0X₃ +0Х₄ –MY₁=2X₁+ 1X₂ –M*(5 - X₁ –X₂ + Х₄) =

= (2 + М)X₁+ (1 + М)X₂ –MХ₄ - 5M

Для нулевого опорного плана Х=(0,0,12,5) построим симплексную таблицу:

Полученный план Х=(2,3,0,0), при этом доход максимален 7тыс. руб., ресурсы использованы полностью (2*3+3*2=12) и выполнено условие маркетинга (2*1+3*1=5).

Поиск по сайту: