Целочисленное программирование

Введение

В наше время всё человечество находиться на такой стадии развития, что дальнейший прогресс связан с огромными затратами ресурсов. Не каждая страна или крупная корпорация может позволить себе вести исследования в передовых областях науки. Примером таких исследований служит освоение космоса, создание реактора ядерного синтеза и изучение короткоживущих элементарных частиц. Очевидно, что ошибка в проекте может привести к провалу всего начинания. Ресурсы, затраченные на проект, также не являются бесконечными. В такой обстановке большое влияние на успех всего оказывают процессы моделирования и оптимизации. Теории, позволяющей оптимизировать любое выражение, не существует, однако, для определённых видов выражений построен математический аппарат, позволяющий найти оптимум.

В данной курсовой работе приведены примеры решения фундаментальных задач оптимизации наиболее распространенными методами.

Линейное программирование

Решение задачи 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. Количество итераций зависит от того, на сколько «далеко» находится начальное базисное решение от оптимального.

Целочисленное программирование

Наши рекомендации