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

Введение

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

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

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

Решение задачи 1.1

Максимизировать целевую функцию:

Y=-x₁+9x₂-3x₃ → max

При ограничениях:

-x₁-2x₂-x₃ ≥ -5

-x₁+x₂-2x₃ ≤ -5

x₁+2x₂+x₃ ≤ 7

x_1,2,3,4 ≥ 0

 

Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x₄, x₅, x₆.

x₁+2x₂+x₃ +x₄+0x₅+0x₆=5

x₁-x₂+2x₃ +0x₄-x₅+0x₆=5

x₁+2x₂+x₃ +0x₄+0x₅+1x₆=7

Выразим допустимый базис в форме Таккера:

X₄=5-( x₁+2x₂+x₃)

X₅=-5-(-x₁+x₂-2x₃)

X₆=7-( x₁+2x₂+x₃)

Целевая функция в форме Таккера:

Y=0-(1x₁-9x₂+3x₃)

На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 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=2x₁-5x₂+7x₃ → max

При ограничениях:

0x₁-2x₂+x₃ ≤ 1

2x₁+x₂+x₃ ≤ 4

-x₁-2x₂+0x₃ ≤ -1

0x₁+2x₂+0x₃≤3

 

x_1,2,3 ≥ 0

 

Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x₄, x₅, x₆ и х₇.

0x₁-2x₂+x₃+1x₄+0x₅+0x₆+0x₇ = 1

2x₁+x₂+x₃+0x₄+1x₅+0x₆+0x₇ = 4

x₁+2x₂+0x₃+0x₄+0x₅+1x₆+0x₇ = 1

0x₁+2x₂+0x₃+0x₄+0x₅+0x₆+1x₇=3

Выразим допустимый базис в форме Таккера:

X₄=1-(0x₁-2x₂+x₃)

X₅=4-(2x₁+x₂+x₃)

X₆=-1-(-x₁-2x₂+0x₃)

X₇=3-(0x₁+2x₂+0x₃)

Целевая функция в форме Таккера:

Y=0-(-2x₁+5x₂-7x₃)

На основании целевой функции и полученных ограничений можно составить симплекс-таблицу (Таблица 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=-4x₁-x₂+3x₃-2x₄ → max

При ограничениях:

1x₁+2x₂+0x₃+0x₄ ≥ 3

-2x₁+0x₂+0x₃+2x₄ ≤ -9

-x₁-x₂+x₃+2x₄ ≤ -5

x₁+0x₂-2x₃+x₄ ≥ 2

x_1,2,3,4 ≥ 0

 

Нужно привести систему ограничений к каноническому виду. Для этого следует добавить дополнительные переменные x₅, x₆, x₇ и x₈.

1x₁+2x₂+0x₃+0x₄ -1x₅+0x₆+0x₇+0x₈=3

2x₁+0x₂+0x₃-2x₄ +0x₅-1x₆+0x₇+0x₈=9

x₁+x₂-x₃-2x₄ +0x₅+0x₆-1x₇+0x₈=5

x₁+0x₂-2x₃+x₄ +0x₅+0x₆+0x₇-1x₈=2

Выразим допустимый базис в форме Таккера:

X₅=-3-(-1x₁-2x₂+0x₃+0x₄)

X₆=-9-(-2x₁+0x₂+0x₃+2x₄)

X₇=-5-( -x₁-x₂+x₃+2x₄)

X₈=-2-( -x₁+0x₂+2x₃-x₄)

Целевая функция в форме Таккера:

Y=0-(4x₁+x₂-3x₃+2x₄)

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

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