Математическая постановка задачи
Переменные:
Х1 - Двугорбый верблюд
Х2 - Одногорбый верблюд
Х3 – Мул
Целевая функция – минимизация арендной платы.
Z min = 12Х1 + 5Х2+ 4Х3
Ограничения:
Использования ресурса «вода» не более 900 галлонов:
40Х1 + 30Х2+ 10Х3 < 900
Использования ресурса «сено» не более 35 кип:
3Х1 + 2Х2+ Х3 < 35
Компания должна перевести 8000 фунтов инжира:
1000Х1 + 500Х2 + 300Х3 =8000
Все переменные должны быть не отрицательны:
Х1, Х2, Х3 > 0
Решения задачи симплекс-методом
ЦФ:
Zmin = 12X1 + 5X2 + 4X3
Ограничения:
40X1 + 30X2 + 10X3 < 900
3X1 + 2X2 + X3 < 35
1000X1 + 500X2 + 300X3 = 8000
X1, X2, X3 > 0
Приведем задачу к канонической форме и введём искусственные переменные:
Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – MR1
40X1 + 30X2 + 10X3 + 0S1 = 900
3X1 + 2X2 + X3 + 0S2 = 35
1000X1 + 500X2 + 300X3 + R1 = 8000
X1, X2, X3 > 0
R1 = – 1000X1 – 500X2 – 300X3 + 8000
Zmin = 12X1 + 5X2 + 4X3 + 0S1 + 0S2 – M (– 1000X1 – 500X2 – 300X3 + 8000) = (12 + 1000M) X1 + (5 + 500M) X2 + (4 + 300M) X3 – 8000M
Z + (–12 – 1000M) X1 + (–5 – 500M) X2 + (–4 – 300M) X3 = – 8000M
Составляем симплекс таблицу:
| Шаг 0 |
|
|
|
|
|
|
| ||
| БП | X 1 | X2 | X3 | S1 | S2 | R1 | решение | ||
| S1 | 40 | 30 | 10 | 1 | 0 | 0 | 900 | ||
| S2 | 3 | 2 | 1 | 0 | 1 | 0 | 35 | ||
| R1 | 1000 | 500 | 300 | 0 | 0 | 1 | 8000 | ||
| Z | -1000M+12 | -500M+5 | -300M+4 | 0 | 0 | 0 | -8000M | ||
|
|
|
|
|
|
|
|
| ||
| Шаг 1 |
|
|
|
|
|
|
| ||
| S1 | 0 | 10 | -2 | 1 | 0 | -1/25 | 580 | ||
| S2 | 0 | 1/2 | 1/10 | 0 | 1 | -3/1000 | 11 | ||
| X1
| 1 | 1/2 | 3/10 | 0 | 0 | 1/1000 | 8 | ||
| Z | 0 | -1 | 2/5 | 0 | 0 | M-3/250 | -96 | ||
|
|
|
|
|
|
|
|
| ||
| Шаг 2 |
|
|
|
|
|
|
| ||
| S1 | -20 | 0 | -8 | 1 | 0 | -3/50 | 420 | ||
| S2 | -1 | 0 | -1/5 | 0 | 1 | -1/250 | 3 | ||
| X2 | 2 | 1 | 3/5 | 0 | 0 | 1/500 | 16 | ||
| Z | 2 | 0 | 1 | 0 | 0 | M-1/100 | -80 |
В итоге: Z = 80, X1 = 0, X2 = 16, X3 = 0
Постоптимальный анализ решения
Определения статуса и ценности ресурсов
Zmin = 12X1 + 5X2 + 4X3
40X1 + 30X2 + 10X3 + S1 = 900
3X1 + 2X2 + X3 + S2 = 35
1000X1 + 500X2 + 300X3 = 8000
Двойственная задача имеет вид:
ω max = 900Y1 + 35Y2 + 8000Y3
40Y1 + 3Y2 + 1000Y3 < 12 (X1)
30Y1 + 2Y2 + 500Y3 < 5 (X2)
10Y1 + 1Y2 + 300Y3 < 4 (X3)
Y1 < 0 (S1)
Y2 < 0 (S2)
В оптимальной таблице прямой задачи базисными переменными являются S1, S2 и X2. Согласно с соотношениями дополняющей нежесткости соответствующие этим переменным ограничения – неравенства двойственной задачи в точке оптимума выполняются как равенства. Таким образом, получаем следующую систему линейных равенств.
30Y1 + 2Y2 + 500Y3 = 5 Y1 = 0
Y1 = 0 Y2 = 0
Y2 = 0 Y3 = 0,01
Решения полученной системы линейных уравнений:
Y1 = 0; Y2 = 0; Y3 = 0,01
По основной теореме двойственности решения прямой и двойственной задачи должны совпадать:
ω = 900*0 + 35*0 + 8000*0.01 = 80 => ω = Z
|
|
|
Ценности ресурсов
| № ресурса | Наименования | Статус | Ценность |
| 1-й | Вода | Недефицитный | 0 |
| 2-й | Сено | Недефицитный | 0 |
| 3-й | Соотношение | Дефицитный | 0,01 |
Согласно теории двойственности, двойственная переменная Yi (і = 1,2,3) определяет ценность і-го ресурса – величину, на которую изменится значения целевой функции при увеличении на единицу уровня запаса соответствующего ресурса.
Таким образом, при изменении в некоторых границах уровней запасов ресурсов имеем:
- при увеличении на 1 единицу ресурса «вода» не приведут к изменению
- при увеличении на 1 единицу ресурса «сено» не приведут к изменению
- при увеличении на 1 фунта перевозки, повысится арендная плата на 0,01 пиастров.
Определения допустимых диапазонов изменения уровней запасов ресурсов
Недефицитные ресурсы:
Переменная S1 – базисная, ресурс «вода» недефицитный.
Ограничения имеет знак « < »
-420 < ∆1 < ∞
Абсолютный диапазон изменения:
480 < b1 < ∞
Переменная S2 – базисная, ресурс «сено» недефицитный.
Ограничения имеет знак « < »
-3 < ∆2 < ∞
Абсолютный диапазон изменения:
32 < b2 < ∞
Дефицитные ресурсы:
|
|
|
Переменная R1 – не базисная, ресурс дефицитный.
-8000 < ∆3 < 750
Абсолютный диапазон изменения:
0 < b3 < 8750
Определение допустимых диапазонов изменения коэффициентов целевой функции
Базисные переменные:
Переменная X2 – базисная:
-∞ < ∆2 < 1
Абсолютный диапазон изменения коэффициента ЦФ:
-∞ < С2 < 13
Не базисные переменные:
Переменная Х1 – не базисная:
2 < ∆1 < ∞
Абсолютный диапазон изменения коэффициента ЦФ:
14 < C1 < ∞
Переменная Х3 – не базисная:
1 < ∆3 < ∞
Абсолютный диапазон изменения коэффициента ЦФ:
5 < C3 < ∞
Ответ
Оптимальное решения задачи:
- использование «двугорбый верблюд» - 0
- использование «одногорбый верблюд» - 16
- использования «мул» - 0
При этом оптимум = 80 пиастрам
Диапазон изменения уровня запасов:
- запасы воды -420 < ∆1 < ∞
- запасы сена -3 < ∆2 < ∞
- соотношение -8000 < ∆3 < 750
Абсолютные диапазоны изменения уровней запасов:
- запасы воды 480 < b1 < ∞
- запасы сена 32 < b2 < ∞
- соотношение 0 < b3 < 8750
Ценность ресурсов:
|
|
|
- при увеличении на 1 единицу ресурса «вода» не приведут к изменению
- при увеличении на 1 единицу ресурса «сено» не приведут к изменению
- при увеличении на 1 фунта перевозки, повысится арендная плата на 0,01 пиастров.
Диапазон изменения коэффициентов:
- двугорбый верблюд 2 < ∆1 < ∞
- одногорбый верблюд ∞ < ∆2 < 1
- мул 1 < ∆3 < ∞
Абсолютные диапазоны изменения:
- двугорбый верблюд 14 < C1 < ∞
- одногорбый верблюд -∞ < С2 < 13
- мул 5 < C3 < ∞
Дата добавления: 2019-07-15; просмотров: 156; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!