Решение и постоптимальный анализ задачи линейного программирования (стр. 2 из 2)

(d_N) < ∆ < ∞

2. Содержательная постановка задачи

Вариант 3/2

Транспортная компания для перевозки инжира из Багдада в Мекку использует мулов, одногорбых и двугорбых верблюдов. Двугорбый верблюд может перевезти - 1000 фунтов, одногорбый – 500 фунтов, а мул – 300 фунтов. За один переход двугорбый верблюд потребляет 2 кипы сена и 40 галлонов воды. Одногорбый верблюд потребляет 2 кипы сена и 30 галлонов воды. Мул – 1 кипу сена и 10 галлонов воды. Пункты снабжения компании, расположенные в различных оазисах вдоль пути, могут выдать не более 900 галлонов воды и 35 кип сена. Верблюды и мулы арендуются у пастуха близ Багдада, арендная плата равна 12 пиастрам за двугорбого верблюда, 5 пиастрам за одногорбого и 4 пиастрам за мула.

Если компания должна перевести 8000 фунтов инжира из Багдада в Мекку, сколько надо использовать верблюдов и мулов для минимизации арендной платы пастуху?

3. Математическая постановка задачи

Переменные:

Х1 - Двугорбый верблюд

Х2 - Одногорбый верблюд

Х3 – Мул

Целевая функция – минимизация арендной платы.

Zmin = 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

4. Решения задачи симплекс-методом

ЦФ:

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

5. Постоптимальный анализ решения

5.1 Определения статуса и ценности ресурсов

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

5.2 Ценности ресурсов

№ ресурса	Наименования	Статус	Ценность
1-й	Вода	Недефицитный	0
2-й	Сено	Недефицитный	0
3-й	Соотношение	Дефицитный	0,01

Согласно теории двойственности, двойственная переменная Yi (і = 1,2,3) определяет ценность і-го ресурса – величину, на которую изменится значения целевой функции при увеличении на единицу уровня запаса соответствующего ресурса.

Таким образом, при изменении в некоторых границах уровней запасов ресурсов имеем:

- при увеличении на 1 единицу ресурса «вода» не приведут к изменению

- при увеличении на 1 единицу ресурса «сено» не приведут к изменению

- при увеличении на 1 фунта перевозки, повысится арендная плата на 0,01 пиастров.

5.3 Определения допустимых диапазонов изменения уровней запасов ресурсов

Недефицитные ресурсы:

Переменная S1 – базисная, ресурс «вода» недефицитный.

Ограничения имеет знак « < »

-420 < ∆1 < ∞

Абсолютный диапазон изменения:

480 <b1 < ∞

Переменная S2 – базисная, ресурс «сено» недефицитный.

Ограничения имеет знак « < »

-3 < ∆2 < ∞

Абсолютный диапазон изменения:

32 <b2 < ∞

Дефицитные ресурсы:

Переменная R1 – не базисная, ресурс дефицитный.

-8000 < ∆3 < 750

Абсолютный диапазон изменения:

0 <b3 < 8750

5.4 Определение допустимых диапазонов изменения коэффициентов целевой функции

Базисные переменные:

Переменная X2 – базисная:

-∞ < ∆2 < 1

Абсолютный диапазон изменения коэффициента ЦФ:

-∞ < С2 < 13

Не базисные переменные:

Переменная Х1 – не базисная:

2 < ∆1 < ∞

Абсолютный диапазон изменения коэффициента ЦФ:

14 <C1 < ∞

Переменная Х3 – не базисная:

1 < ∆3 < ∞

Абсолютный диапазон изменения коэффициента ЦФ:

5 <C3 < ∞

6. Ответ

Оптимальное решения задачи:

- использование «двугорбый верблюд» - 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 < ∞

7. Задание на применения графического способа решения задач линейного программирования

№ 28

Z = 2X1 + X2 → min

X1 - X2 > 4 (1)

X1 + X2 > 4 (2)

4X1 - X2 < 16 (3)

7X1 + X2 < 14 (4)

X1, X2 > 0

Ответ: Нет решений

№ 58

Z = -X1 + 3X2 → max

-2X1 + X2 < 2 (1)

X1 + 2X2 > 6 (2)

X1 > 2 (3)

3X1 + 4X2 < 24 (4)

X1, X2 > 0

Ответ: X1 = 2

X2 = 4.5

Z = 11.5

СПИСОК ЛИТЕРАТУРЫ

1. Исследование операций. В 2-ух томах. Методологические основы и математические методы. / Под ред. Дж. Моудера, С. Элмаграби. - М.: Мир, 1981. Т. 1.-712 с.

2. Муртаф Б. Современное линейное программирование. Теория и практика -М.: Мир, 1984.- 224 с. Т.

3. Таха X. Введение в исследование операций: В 2-ух томах. - М.: Мир, 1985. Т. 1.-325с.

4. Калихман И.Л. Линейная алгебра и программирование. - М.: Высшая школа, 1967.-428 с.

5. Конспект лекций.