АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. ABC-аналіз як метод оптимізації абсолютної величини затрат підприємства
  2. I. ПРЕДМЕТ И МЕТОД
  3. I.ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
  4. II. Документация как элемент метода бухгалтерского учета
  5. II. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ СТУДЕНТОВ
  6. II. Методична робота.
  7. II. МЕТОДЫ, ПОДХОДЫ И ПРОЦЕДУРЫ ДИАГНОСТИКИ И ЛЕЧЕНИЯ
  8. II. МЕТОДЫ, ПОДХОДЫ И ПРОЦЕДУРЫ ДИАГНОСТИКИ И ЛЕЧЕНИЯ
  9. III. Mix-методики.
  10. III. ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ ДО ВИКОНАННЯ КОНТРОЛЬНИХ РОБІТ .
  11. III. ИНФОРМАЦИОННО-МЕТОДИЧЕСКАЯ ЧАСТЬ
  12. III. Методы оценки функции почек

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

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).


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

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



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