Автор: Пользователь скрыл имя, 23 Сентября 2011 в 11:41, курсовая работа
Поиски оптимальных решений привели к созданию специальных
математических методов и уже в 18 веке были заложены математические основы
оптимизации (вариационное исчисление, численные методы и др). Однако до
второй половины 20 века методы оптимизации во многих областях науки и
техники применялись очень редко, поскольку практическое использование
математических методов оптимизации требовало огромной вычислительной
работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев -
невозможно.
ВВЕДЕНИЕ…….………………………………………………………………...3
1. Постановка задачи оптимизации……………………………………….…8
2. Построение аналитической модели…………………………………….…9
3. Обоснование и описание вычислительной процедуры………………..11
1. Приведение задачи линейного программирования к стандартной
форме………………..………………………………………………….11
2. Основная идея симлекс-метода……………………………………..12
3. Двухэтапный симплекс-метод………………………………………12
4. Решение задачи оптимизации на основе симплекс-таблиц……………14
1. Приведение задачи к стандартной форме………..………………..14
2. Определение начального допустимого решения…………………14
3. Построение искусственного базиса………...………………………15
4. Первый этап двухэтапного симплекс-метода…………………….16
5. Второй этап двухэтапного метода………………………………….19
5. Анализ модели на чувствительность……………………………………..22
1. Статус ресурсов……….………………………………………………22
2. Ценность ресурсов……………………………………………………22
3. Анализ на чувствительность к изменениям правых частей
ограничений……………………………………………………….…..23
4. Анализ на чувствительность к изменениям коэффициентов
целевой функции……………………………………………...………25
6. Определение оптимального целочисленного решения…………………26
6.1. Метод Гомори для частично целочисленных задач……..……….26
ЗАКЛЮЧЕНИЕ…………………………………………………………...……33
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ………………….……..34
УСЛОВНЫЕ СОКРАЩЕНИЯ………………………….……………………35
ПРИЛОЖЕНИЕ…………………………………………………………….…..
------------------------------
Ведущий элемент
находится в 5 столбце и 2 строке.
Вывод промежуточных
результатов оптимизации.
+-----------------------------
------------------------------
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+--------+--------+--
¦ 3¦ E ¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦
0.00¦ -1.00¦ 1.50¦ 0.00¦
¦ +----+--------+--------+------
----+--------+--------+
¦ ¦ -W ¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦
0.00¦ 1.00¦ 1.00¦ 0.00¦
¦ +----+--------+--------+------
----+--------+--------+
¦ ¦ X4 ¦ 0.33¦ 0.00¦ -0.33¦ 1.00¦ 0.00¦ -0.33¦ 0.00¦
0.00¦ 0.00¦ 0.17¦ 0.00¦
¦ ¦ X5 ¦ 0.00¦ 0.33¦ -0.67¦ 0.00¦ 1.00¦ -0.67¦ 0.00¦
0.00¦ -0.33¦ 0.33¦ 0.00¦
¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦
0.00¦ 0.00¦ 0.00¦ 8.00¦
¦ ¦ X8 ¦ -0.33¦ -0.33¦ 1.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦
1.00¦ 0.33¦ -0.50¦ 8.00¦
+-----------------------------
------------------------------
Вывод промежуточных
результатов оптимизации.
+-----------------------------
-------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+---
¦ 3¦ E ¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦ 0.00¦ -5.00¦ 0.00¦
0.00¦ 0.00¦
¦ +----+--------+--------+------
----+-
¦ ¦ X4 ¦ 0.33¦ 0.00¦ -0.33¦ 1.00¦ 0.00¦ -0.33¦ 0.00¦
0.00¦ 0.00¦
¦ ¦ X5 ¦ 0.00¦ 0.33¦ -0.67¦ 0.00¦ 1.00¦ -0.67¦ 0.00¦
0.00¦ 0.00¦
¦ ¦ X7 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦
0.00¦ 8.00¦
¦ ¦ X8 ¦ -0.33¦ -0.33¦ 1.00¦ 0.00¦ 0.00¦ 2.00¦ 0.00¦
1.00¦ 8.00¦
+-----------------------------
-------------+
Ведущий элемент
находится в 3 столбце и 3 строке.
Вывод промежуточных
результатов оптимизации.
+-----------------------------
-------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+---
¦ 4¦ E ¦ 5.00¦ 5.00¦ 0.00¦ 0.00¦ 0.00¦ -5.00¦ 5.00¦
0.00¦ 40.00¦
¦ +----+--------+--------+------
----+--
¦ ¦ X4 ¦ 0.67¦ 0.33¦ 0.00¦ 1.00¦ 0.00¦ -0.33¦ 0.33¦
0.00¦ 2.67¦
¦ ¦ X5 ¦ 0.67¦ 1.00¦ 0.00¦ 0.00¦ 1.00¦ -0.67¦ 0.67¦
0.00¦ 5.33¦
¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦
0.00¦ 8.00¦
¦ ¦ X8 ¦ -1.33¦ -1.33¦ 0.00¦ 0.00¦ 0.00¦ 2.00¦ -1.00¦
1.00¦ 0.00¦
+-----------------------------
-------------+
Ведущий элемент
находится в 6 столбце и 4 строке.
Вывод промежуточных
результатов оптимизации.
+-----------------------------
-------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+---
¦ 5¦ E ¦ 1.67¦ 1.67¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 2.50¦
2.50¦ 40.00¦
¦ +----+--------+--------+------
----+--
¦ ¦ X4 ¦ 0.44¦ 0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.17¦
0.17¦ 2.67¦
¦ ¦ X5 ¦ 0.22¦ 0.56¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.33¦
0.33¦ 5.33¦
¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦
0.00¦ 8.00¦
¦ ¦ X6 ¦ -0.67¦ -0.67¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ -0.50¦
0.50¦ 0.00¦
+-----------------------------
-------------+
Результаты оптимизации.
Базис Значение
X4 2.67
X5 5.33
X3 8.00
X6
0.00
Максимум функции
равен 40.00
Вывод промежуточных
результатов оптимизации.
+-----------------------------
----------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦ X9 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+--------+---
¦ 1¦ E ¦ 1.67¦ 1.67¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 2.50¦
2.50¦ 0.00¦ 40.00¦
¦ +----+--------+--------+------
----+--------+-
¦ ¦ X4 ¦ 0.44¦ 0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ 0.17¦
0.17¦ 0.00¦ 2.67¦
¦ ¦ X5 ¦ 0.22¦ 0.56¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.33¦
0.33¦ 0.00¦ 5.33¦
¦ ¦ X3 ¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦
0.00¦ 0.00¦ 8.00¦
¦ ¦ X6 ¦ -0.67¦ -0.67¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ -0.50¦
0.50¦ 0.00¦ 0.00¦
¦ ¦ X9 ¦ -0.44¦ -0.11¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ -0.17¦
-0.17¦ 1.00¦ -0.67¦
+-----------------------------
----------------------+
Ведущий элемент
находится в 1 столбце и 5 строке.
Вывод промежуточных
результатов оптимизации.
+-----------------------------
----------------------+
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦ X9 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+--------+--
¦ 2¦ E ¦ -0.00¦ 1.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.88¦
1.88¦ 3.75¦ 37.50¦
¦ +----+--------+--------+------
----+--------+--
¦ ¦ X4 ¦ -0.00¦ -0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.00¦
-0.00¦ 1.00¦ 2.00¦
¦ ¦ X5 ¦ -0.00¦ 0.50¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.25¦
0.25¦ 0.50¦ 5.00¦
¦ ¦ X3 ¦ -0.00¦ 0.75¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.62¦
-0.38¦ 2.25¦ 6.50¦
¦ ¦ X6 ¦ -0.00¦ -0.50¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.25¦
0.75¦ -1.50¦ 1.00¦
¦ ¦ X1 ¦ 1.00¦ 0.25¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.38¦
0.38¦ -2.25¦ 1.50¦
+-----------------------------
----------------------+
Результаты оптимизации.
Базис Значение
X4 2.00
X5 5.00
X3 6.50
X6 1.00
X1
1.50
Максимум функции
равен 37.50
Вывод промежуточных
результатов оптимизации.
+-----------------------------
------------------------------
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+--------+--------+--
¦ 2¦ E ¦ -0.00¦ 1.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.88¦
1.88¦ 3.75¦ 0.00¦ 37.50¦
¦ +----+--------+--------+------
----+--------+--------+-
¦ ¦ X4 ¦ -0.00¦ -0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.00¦
-0.00¦ 1.00¦ 0.00¦ 2.00¦
¦ ¦ X5 ¦ -0.00¦ 0.50¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.25¦
0.25¦ 0.50¦ 0.00¦ 5.00¦
¦ ¦ X3 ¦ -0.00¦ 0.75¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.62¦
-0.38¦ 2.25¦ 0.00¦ 6.50¦
¦ ¦ X6 ¦ -0.00¦ -0.50¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.25¦
0.75¦ -1.50¦ 0.00¦ 1.00¦
¦ ¦ X1 ¦ 1.00¦ 0.25¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.38¦
0.38¦ -2.25¦ 0.00¦ 1.50¦
¦ ¦ X10¦ 0.00¦ -0.25¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ -0.38¦
-0.38¦ -2.25¦ 1.00¦ -0.50¦
+-----------------------------
------------------------------
Ведущий элемент
находится в 9 столбце и 6 строке.
Вывод промежуточных
результатов оптимизации.
+-----------------------------
------------------------------
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+--------+--------+--
¦ 3¦ E ¦ -0.00¦ 0.83¦ 0.00¦ 0.00¦ 0.00¦ 0.00¦ 1.25¦
1.25¦ -0.00¦ 1.67¦ 36.67¦
¦ +----+--------+--------+------
----+--------+--------+-
¦ ¦ X4 ¦ -0.00¦ -0.11¦ 0.00¦ 1.00¦ 0.00¦ 0.00¦ -0.17¦
-0.17¦ -0.00¦ 0.44¦ 1.78¦
¦ ¦ X5 ¦ -0.00¦ 0.44¦ 0.00¦ 0.00¦ 1.00¦ 0.00¦ 0.17¦
0.17¦ -0.00¦ 0.22¦ 4.89¦
¦ ¦ X3 ¦ -0.00¦ 0.50¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ 0.25¦
-0.75¦ -0.00¦ 1.00¦ 6.00¦
¦ ¦ X6 ¦ -0.00¦ -0.33¦ -0.00¦ -0.00¦ -0.00¦ 1.00¦ -0.00¦
1.00¦ -0.00¦ -0.67¦ 1.33¦
¦ ¦ X1 ¦ 1.00¦ 0.50¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.75¦
0.75¦ -0.00¦ -1.00¦ 2.00¦
¦ ¦ X9 ¦ -0.00¦ 0.11¦ -0.00¦ -0.00¦ -0.00¦ -0.00¦ 0.17¦
0.17¦ 1.00¦ -0.44¦ 0.22¦
+-----------------------------
------------------------------
Результаты оптимизации.
Базис Значение
X4 1.78
X5 4.89
X3 6.00
X6 1.33
X1 2.00
X9
0.22
Максимум функции
равен 36.67
Вывод промежуточных
результатов оптимизации.
+-----------------------------
------------------------------
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦ X9 ¦ X10 ¦ X11 ¦Баз.Реш.¦
Информация о работе Решение оптимизационной задачи линейного программирования