double arrow

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


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

ai1 X1 + ai2 X2 +…ain X n ≥ bi (7)

или уравнений ai1 X1 + ai2 X2 +…ain X n = bi (7*),

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

ai1 X1 + ai2 X2 +…ain X n +Yi = bi (8).

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

Z(X) =∑CjXj+(-M)∑Yi (9),

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

Z(X)=∑CjXj+(M)∑Yi (9*),

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

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

ai1X1+ai2X2+…ainXn–Xn+i+Yi=bi (10) Целевая функция при этом Z(X)=∑CjXj+0∑Xn+i+(-M)∑Yi (для нахождения максимума). Применение искусственного базиса придает симплексному методу большую гибкость и позволяет использовать его для широкого круга задач.

Пример №4.

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

Виды ресурсов Нормы затрат на производство 1 т Запасы ресурсов
Группа А Группа В
Сырье ,т 1,0 1,0
Рабочее время чел.-час 2,0 1,0
Доход с 1 т, тыс. руб.  

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

1 + 1Х2≤ 6,

1 + 1Х2 =8.

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

1 + 1Х2+ Х3 = 6,

1 + 1Х2 +Y1 =8.

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

Z(X)= 3X1+ 2X2+0X3 –MY1= 3X1+ 2X2 –M(8 -2X1 –X2)=

= 3X1+ 2X2 –8M +2MX1 + MX2 = (2M + 3)X1 + (M + 2)X2 -8M

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

План Базис Ci/Cj Знач. Xi X1 X2 X3 Y1 Qmin
  X3 6/1=6
Y1 -M 8/2=4
Z(X) = -8M -2M-3 -M-2 Индексная строка
X3 0,5 -0,5 2/0,5=4
→X1 0,5 0,5 4/0,5=8
Z(X) = 3*4=12 - 0,5 М+1,5 Индексная строка
→X2 -1 -
X1 -1 -
Z(X) =3*2+2*4=14 М+1 Индексная строка

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

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

Z(X)= 3X1+ 2X2+0X3 +MY1= 3X1+ 2X2 +M(8 -2X1 –X2)=

= 3X1+ 2X2 +8M - 2MX1 - MX2 = (3 - 2M)X1 + (2 - M )X2 +8M

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

План Базис Ci/Cj Знач. Xi X1 X2 X3 Y1 Qmin
X3 6/1=6
Y1 M 8/2=4
Z(X) = 8М 2M-3 M-2 Индексная строка
X3 0,5 -0,5 2/0,5=4
→X1 0,5 0,5 4/0,5=8
Z(X) = 3*4=12 - 0,5 -М+1,5 Индексная строка
                     

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

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

Пример №5.

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

Виды ресурсов Нормы затрат на производство 1 т Запасы ресурсов
Группа А Группа В
Сырье ,т 3,0 2,0
Доход с 1 т, тыс. руб.  

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

3X1 + 2X2 ≤ 12,

X1 + X2 ≥ 5.

Введем для первого неравенства базисную переменную Х3, а для второго уравнения отрицательную Х4 и искусственную переменную Y1:

3X1 + 2X2 + X3 = 12,

X1 + X2 – X4 + Y1 = 5.

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

Z(X) = 2X1+ 1X2+0X3 +0Х4 –MY1=2X1+ 1X2 –M*(5 - X1 –X2 + Х4) =

= (2 + М)X1+ (1 + М)X2 –MХ4 - 5M

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

План Базис Ci/Cj Знач. Xi X1 X2 X3 Х4 Y1 Qmin
X3 12/3=4
Y1 -M -1 5/1=5
Z(X) = - 5М -M-2 -M-1 М Индекс строка
→X1 2/3 1/3 4/(2/3)=6
Y1 -M 1/3 -1/3 -1 1/(1/3)=3
Z(X) = 2*4 - M=8-M -M/3+1/3 (M+2)/3 M Индекс строка
X1 -2 -
→X2 -1 -3 -
Z(X) = 2*2+1*3=7 2/3M+1 М-1 Индекс строка

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


Сейчас читают про: