Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение задачи 1.3
|
|
Максимизировать целевую функцию:
Y=-4x1-x2+3x3-2x4 → max
При ограничениях:
1x1+2x2+0x3+0x4 ≥ 3
-2x1+0x2+0x3+2x4 ≤ -9
-x1-x2+x3+2x4 ≤ -5
x1+0x2-2x3+x4 ≥ 2
x1, 2, 3, 4 ≥ 0
Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x5, x6, x7 и x8.
1x1+2x2+0x3+0x4 -1x5+0x6+0x7+0x8=3
2x1+0x2+0x3-2x4 +0x5-1x6+0x7+0x8=9
x1+x2-x3-2x4 +0x5+0x6-1x7+0x8=5
x1+0x2-2x3+x4 +0x5+0x6+0x7-1x8=2
Выразим допустимый базис в форме Таккера:
X5=-3-(-1x1-2x2+0x3+0x4)
X6=-9-(-2x1+0x2+0x3+2x4)
X7=-5-(-x1-x2+x3+2x4)
X8=-2-(-x1+0x2+2x3-x4)
Целевая функция в форме Таккера:
Y=0-(4x1+x2-3x3+2x4)
На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.10).
Таблица 1.10
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
| X5 | -3 | -1 | -2 | ||||||
| X6 | -9 | -2 | |||||||
| X7 | -5 | -1 | -1 | ||||||
| X8 | -2 | -1 | -1 | ||||||
| Y | -3 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X6. Результат отображен в таблице 1.11.
Таблица 1.11
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
| X5 | 3/2 | -2 | -1 | -1/2 | |||||
| X1 | 9/2 | -1 | -1/2 | ||||||
| X7 | -1/2 | -1 | -1/2 | ||||||
| X8 | 5/2 | -2 | -1/2 | ||||||
| Y | -18 | -3 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7. Результат отображен в таблице 1.12.
Таблица 1.12
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
| X5 | 5/2 | -2 | -3 | 1/2 | -2 | ||||
| X1 | 9/2 | -1 | -1/2 | ||||||
| X2 | 1/2 | -1 | -1 | 1/2 | -1 | ||||
| X8 | 5/2 | -2 | -1/2 | ||||||
| Y | -37/2 | -2 | 3/2 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X8. Результат отображен в таблице 1.13.
Таблица 1.13
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
| X5 | -5 | -2 | |||||||
| X1 | 9/2 | -1 | -1/2 | ||||||
| X2 | 7/4 | -2 | 1/4 | -1 | 1/2 | ||||
| X3 | 5/4 | -1 | -1/4 | 1/2 | |||||
| Y | -16 |
В столбце свободных членов и в строке коэффициентов отсутствуют отрицательные элементы, а следовательно, полученный план оптимален. Произведём проверку, подставив полученные значения для переменных в начальные условия и убедившись в их верности, выписываем ответ.
Ответ: Решение оптимально
Y=-16
X=(9/2; 7/4; 5/4; 0; 5; 0; 0; 0)
Количество итераций=3
Выводы к Главе 1
§ В первой главе на примере данных трех задач продемонстрированы основные этапы и приемы, применяемые при решении задач линейного программирования.
§ Сложность решения задач линейного программирования определяется количеством переменных и ограничений в исходной задачe. Количество итераций зависит от того, на сколько «далеко» находится начальное базисное решение от оптимального.
Целочисленное программирование
Решение полностью целочисленной задачи
Максимизировать целевую функцию:
Y=-4x1-x2+3x3-2x4 → max
При ограничениях:
x1+2x2+0x3+0x4 ≥ 3
-2x1+0x2+0x3+2x4 ≤ -9
-x1-x2+x3+2x4 ≤ -5
x1+0x2-2x3+x4 ≥ 2
x1, 2, 3, 4 ≥ 0 и целые
|
|