Целочисленное программирование
Введение
В наше время всё человечество находиться на такой стадии развития, что дальнейший прогресс связан с огромными затратами ресурсов. Не каждая страна или крупная корпорация может позволить себе вести исследования в передовых областях науки. Примером таких исследований служит освоение космоса, создание реактора ядерного синтеза и изучение короткоживущих элементарных частиц. Очевидно, что ошибка в проекте может привести к провалу всего начинания. Ресурсы, затраченные на проект, также не являются бесконечными. В такой обстановке большое влияние на успех всего оказывают процессы моделирования и оптимизации. Теории, позволяющей оптимизировать любое выражение, не существует, однако, для определённых видов выражений построен математический аппарат, позволяющий найти оптимум.
В данной курсовой работе приведены примеры решения фундаментальных задач оптимизации наиболее распространенными методами.
Линейное программирование
Решение задачи 1.1
Максимизировать целевую функцию:
Y=-x1+9x2-3x3 → max
При ограничениях:
-x1-2x2-x3 ≥ -5
-x1+x2-2x3 ≤ -5
x1+2x2+x3 ≤ 7
x1,2,3,4 ≥ 0
Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x4, x5, x6.
x1+2x2+x3 +x4+0x5+0x6=5
x1-x2+2x3 +0x4-x5+0x6=5
x1+2x2+x3 +0x4+0x5+1x6=7
Выразим допустимый базис в форме Таккера:
X4=5-( x1+2x2+x3)
X5=-5-(-x1+x2-2x3)
X6=7-( x1+2x2+x3)
Целевая функция в форме Таккера:
Y=0-(1x1-9x2+3x3)
На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.1).
Таблица 1.1
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 |
| X4 | |||||||
| X5 | -5 | -1 | -2 | ||||
| X6 | |||||||
| Y | -9 |
Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X5. Результат отображен в таблице 1.2.
Таблица 1.2
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 |
| X4 | -1 | ||||||
| X1 | -1 | -1 | |||||
| X6 | -1 | ||||||
| Y | -5 | -8 |
Используем обычный симплекс-метод. Вводим в базис X2, выводим из базиса X4. Результат отображен в таблице 1.3.
Таблица 1.3
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 |
| X2 | -1/3 | 1/3 | 1/3 | ||||
| X1 | 5/3 | 1/3 | -2/3 | ||||
| X6 | -1 | ||||||
| Y | -5 | -5/3 | 8/3 | 11/3 |
Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X1. Результат отображен в таблице 1.4.
Таблица 1.4
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 |
| X2 | 1/5 | 2/5 | 1/5 | ||||
| X3 | 3/5 | 1/5 | -2/5 | ||||
| X6 | -1 | ||||||
| Y |
В столбце свободных членов и в строке коэффициентов отсутствуют отрицательные элементы, а следовательно, полученный план оптимален. Произведём проверку, подставив полученные значения для переменных в начальные условия и убедившись в их верности, выписываем ответ.
Ответ : Решения оптимально
Y=0
X=(0;1;3;0;0;2)
Количество итераций=3
Решение задачи 1.2
Максимизировать целевую функцию:
Y=2x1-5x2+7x3 → max
При ограничениях:
0x1-2x2+x3 ≤ 1
2x1+x2+x3 ≤ 4
-x1-2x2+0x3 ≤ -1
0x1+2x2+0x3≤3
x1,2,3 ≥ 0
Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x4, x5, x6 и х7.
0x1-2x2+x3+1x4+0x5+0x6+0x7 = 1
2x1+x2+x3+0x4+1x5+0x6+0x7 = 4
x1+2x2+0x3+0x4+0x5+1x6+0x7 = 1
0x1+2x2+0x3+0x4+0x5+0x6+1x7=3
Выразим допустимый базис в форме Таккера:
X4=1-(0x1-2x2+x3)
X5=4-(2x1+x2+x3)
X6=-1-(-x1-2x2+0x3)
X7=3-(0x1+2x2+0x3)
Целевая функция в форме Таккера:
Y=0-(-2x1+5x2-7x3)
На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 1.5).
Таблица 1.5
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 |
| X4 | -2 | |||||||
| X5 | ||||||||
| X6 | -1 | -1 | -2 | |||||
| X7 | ||||||||
| Y | -2 | -7 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X6. Результат отображен в таблице 1.6.
Таблица 1.6
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 |
| X4 | -2 | |||||||
| X5 | -3 | |||||||
| X1 | -1 | |||||||
| X7 | ||||||||
| Y | -7 | -2 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X3, выводим из базиса X4. Результат отображен в таблице 1.7.
Таблица 1.7
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 |
| X3 | -2 | |||||||
| X5 | -1 | -1 | ||||||
| X1 | -1 | |||||||
| X7 | ||||||||
| Y | -5 | -2 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X2, выводим из базиса X1. Результат отображен в таблице 1.8.
Таблица 1.8
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 |
| X3 | -1 | |||||||
| X5 | 3/2 | 1/2 | -1 | 3/2 | ||||
| X2 | 1/2 | 1/2 | -1/2 | |||||
| X7 | -1 | |||||||
| Y | 23/2 | 5/2 | -9/2 |
Решение не оптимально, так как имеем в строке Y отрицательные элементы. Используем обычный симплекс-метод. Вводим в базис X6, выводим из базиса X5. Результат отображен в таблице 1.9.
Таблица 1.9
| БП | СЧ | X1 | X2 | X3 | X4 | X5 | X6 | X7 |
| X3 | 4/3 | 1/3 | 2/3 | |||||
| X6 | 1/3 | -2/3 | 2/3 | |||||
| X2 | 2/3 | -1/3 | 1/3 | |||||
| X7 | -4/3 | 2/3 | -2/3 | |||||
| Y |
В столбце свободных членов и в строке коэффициентов отсутствуют отрицательные элементы, а следовательно, полученный план оптимален. Произведём проверку, подставив полученные значения для переменных в начальные условия и убедившись в их верности, выписываем ответ.
Ответ : Решение оптимально
Y=16
X=(0;1;3;0;0;1;1)
Количество итераций=4
Решение задачи 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. Количество итераций зависит от того, на сколько «далеко» находится начальное базисное решение от оптимального.
Целочисленное программирование