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

В итоге: 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 Ценности ресурсов

Согласно теории двойственности, двойственная переменная 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. Конспект лекций.

 Скачать реферат