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

Введение

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

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

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

Решение задачи 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