Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Содержательная постановка задачи ⇐ ПредыдущаяСтр 3 из 3
Вариант 3/2 Транспортная компания для перевозки инжира из Багдада в Мекку использует мулов, одногорбых и двугорбых верблюдов. Двугорбый верблюд может перевезти - 1000 фунтов, одногорбый – 500 фунтов, а мул – 300 фунтов. За один переход двугорбый верблюд потребляет 2 кипы сена и 40 галлонов воды. Одногорбый верблюд потребляет 2 кипы сена и 30 галлонов воды. Мул – 1 кипу сена и 10 галлонов воды. Пункты снабжения компании, расположенные в различных оазисах вдоль пути, могут выдать не более 900 галлонов воды и 35 кип сена. Верблюды и мулы арендуются у пастуха близ Багдада, арендная плата равна 12 пиастрам за двугорбого верблюда, 5 пиастрам за одногорбого и 4 пиастрам за мула. Если компания должна перевести 8000 фунтов инжира из Багдада в Мекку, сколько надо использовать верблюдов и мулов для минимизации арендной платы пастуху? Математическая постановка задачи
Переменные: Х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
Составляем симплекс таблицу:
В итоге: 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
Ценности ресурсов
Согласно теории двойственности, двойственная переменная 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 < ∞ Задание на применения графического способа решения задач линейного программирования
№ 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. Конспект лекций. |
Последнее изменение этой страницы: 2020-02-16; Просмотров: 150; Нарушение авторского права страницы