Автор: Пользователь скрыл имя, 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
ПРИЛОЖЕНИЕ…………………………………………………………….…..
переменной Х3 и небазисных переменных Х2 , Х7 , Х9 ? 0 (0,75?0, 0,625?0,
2,25?0), то коэффициент при переменной Х2 рассчитаем по формуле (3):
L1={0,75}=0,75, коэффициенты при переменных Х7 и Х9 рассчитаем по формуле
(1): L3=0,625, L4=2,25. Так как коэффициент на пересечении базисной
переменной Х3 и небазисной переменной Х8<0, то коэффициент при переменной
Х8 рассчитаем
по формуле (2): L2=({6,5}*(-0,375))/({6,5}-1)=
{В3}={Х3} = {6,5} = 0,5. Ограничение будет иметь вид:
0,25Х2 + 0,625Х7 + 0,375Х8 + 2,25Х9 ? 0,5
Или, после
приведения к стандартному
-0,25Х2 – 0,625Х7 – 0,375Х8 – 2,25Х9 + Х10 = -0,5
Добавим
это ограничение к нашей
|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |БР |
|E |0 |1,25 |0 |0 |0 |0 |1,875 |1,875 |3,75 |0 |37,5 |
|Х3 |0 |0,75 |1 |0 |0 |0 |0,625 |-0,375|2,25 |0 |6,5 |
|X6 |0 |-0,5 |0 |0 |0 |1 |-0,25 |0,75 |-1,5 |0 |1 |
|X4 |0 |0 |0 |1 |0 |0 |0 |0 |1 |0 |2 |
|X5 |1 |0,5 |0 |0 |1 |0 |0,2 |0,25 |0,5 |0 |5 |
|Х1 |1 |0,25 |0 |0 |0 |0 |0,375 |0,375 |-2,25 |0 |1,5 |
|X10 |0 |-0,25
|0 |0 |0 |0 |-0,375|-0,375|-2,25
|1 |-0,5 |
Переменная, исключаемая из базиса – это X10, т.к. ее значение –0,5 -
это максимальный по модулю отрицательный элемент столбца решений. В базис
включаем переменную X9, т.к. |3,75/(-2,25)|=1,67, |1,25/(-0,25)|=5,
|1,875/(-0,375)|=5, 1,67 – минимальное по модулю отношение элемента Е-
строки к отрицательным элементам ведущей строки. Ведущий элемент равен
–2,25. Получим новую
симплекс-таблицу:
|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |БР |
|E |0 |0,83 |0 |0 |0 |0 |1,25 |1,25 |0 |1,67 |36,67 |
|Х3 |0 |0,5 |1 |0 |0 |0 |0,25 |-0,75 |0 |1 |6 |
|X6 |0 |-0,33 |0 |0 |0 |1 |0 |1 |0 |-0,67 |1,33 |
|X4 |0 |0,111 |0 |1 |0 |0 |-0,17 |-0,17 |0 |0,44 |1,78 |
|X5 |0 |0,444 |0 |0 |1 |0 |0,17 |0,17 |0 |0,22 |4,89 |
|Х1 |1 |0,5 |0 |0 |0 |0 |0,75 |0,75 |0 |-1 |2 |
|X9 |0
|0,11 |0 |0 |0 |0
|0,17 |0,17 |1 |-0,44 |0,22 |
Решение все еще не целочисленное, поэтому переходим к следующей
итерации. Переменная, имеющая максимальную дробную часть – это Х5
({4,89}=0,89), она должна быть целой, переменные Х7 , Х8 и Х10 могут быть
дробными, переменная Х2 должна быть целой, поэтому, согласно формуле,
составим новое дополнительное ограничение. Так как коэффициенты на
пересечениях базисной переменной Х5 и небазисных переменных Х2, X7, X8,
Х10?0 (0,44?0, 0,17?0, 0,22?0), то коэффициент при переменной Х2 рассчитаем
по формуле (3): L1={0,44}=0,44, коэффициенты при переменных Х7, Х9 и Х10
рассчитаем по формуле (1): L2=0,17, L3=0,17, L4=0,22. {В5}={Х5} = {4,89} =
0,89. Ограничение будет иметь вид:
0,44Х2 + 0,17Х7 + 0,17Х8 + 0,22Х10 ? 0,89
Или, после
приведения к стандартному
-0,44Х2 – 0,17Х7 – 0,17Х8 – 0,
Добавим
это ограничение к нашей
|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |Х11 |БР |
|E |0 |0,83 |0 |0 |0 |0 |1,25 |1,25 |0 |1,67 |0 |36,67 |
|Х3 |0 |0,5 |1 |0 |0 |0 |0,25 |-0,75 |0 |1 |0 |6 |
|X6 |0 |-0,3 |0 |0 |0 |1 |0 |1 |0 |-0,67 |0 |1,33 |
|X4 |0 |0,11 |0 |1 |0 |0 |-0,17|-0,17 |0 |0,44 |0 |1,78 |
|X5 |0 |0,44 |0 |0 |1 |0 |0,17 |0,17 |0 |0,22 |0 |4,89 |
|Х1 |1 |0,5 |0 |0 |0 |0 |0,75 |0,75 |0 |-1 |0 |2 |
|Х9 |0 |0,11 |0 |0 |0 |0 |0,17 |0,17 |1 |-0,44 |0 |2 |
|X11 |0 |-0,44 |0
|0 |0 |0 |-0,17|-0,17 |0
|-0,22 |1 |-0,89 |
Переменная, исключаемая из базиса – это X11, т.к. ее значение –0,89 -
это максимальный по модулю отрицательный элемент столбца решений. В базис
включаем переменную X2, т.к. |0,83/(-0,44)|=1,9, |1,25/(-0,17)|=7,4,
|1,67/(-0,22)|=7,6, 1,9 – минимальное по модулю отношение элемента Е-строки
к отрицательным элементам ведущей строки. Ведущий элемент равен –0,44.
После пересчетов получим
получим новую симплекс-
|БП |X1 |X2 |X3 |X4 |X5 |X6 |X7 |X8 |X9 |X10 |Х11 |БР |
|E |0 |0 |0 |0 |0 |0 |0,938 |0,94 |0 |1,25 |1,89 |35 |
|Х3 |0 |0 |1 |0 |0 |0 |0,063 |-0,938|0 |0,75 |1,125 |5 |
|X6 |0 |0 |0 |0 |0 |1 |0,125 |1,125 |0 |-0,5 |-0,75 |2 |
|X4 |0 |0 |0 |1 |0 |0 |-0,125|-0,125|0 |0,5 |-0,25 |2 |
|X5 |0 |0 |0 |0 |1 |0 |0 |0 |0 |0 |1 |4 |
|Х1 |1 |0 |0 |0 |0 |0 |0,563 |0,563 |0 |-1,25|1,125 |1 |
|Х9 |0 |0 |0 |0 |0 |0 |0,125 |0,125 |1 |-0,5 |0,25 |0 |
|X2 |0 |1
|0 |0 |0 |0 |0,375 |0,375
|0 |0,5 |-2,25 |2 |
Столбец решений не содержит отрицательных элементов, все переменные
X1, X2, X3 , X4 , X5 , X6 приняли целочисленные значения, значит,
оптимальное целочисленное решение найдено, оно равно:
(X1,X2,X3,X4,X5,X6)=(1,2,5,2,
максимальное значение:
Е=35.
После проведенных вычислений, решив задачу оптимизации, мы получили
следующие результаты: оптимальный план работы станков состоит в том, чтобы
токарный станок работал 1 час над деталями типа 1, 2 часа над деталями типа
2 и 5 часов над деталями типа 3 за смену; станок-автомат должен работать 2
часа над деталями типа 1 , 4 часа над деталями типа 2 и 2 часа над деталями
типа 3 за смену. При этом количество комплектов деталей, выпускаемых цехом,
будет максимально и равно 35.
В результате проведенного анализа на чувствительность к изменению
запаса времени работы токарного станка получили, что если запас времени
работы этого станка будет находиться в пределах от 0 до 8 часов, то базис
оптимального решения останется неизменным, т.е. будет состоять из
переменных (Х3,Х6,Х4,Х5).
СПИСОК ИСПОЛЬЗОВАННОЙ
1. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения
оптимизационных задач линейного программирования. Ч.1. – Мн.: БГУИР, 1995.
2. Смородинский С.С., Батин Н.В. Методы и алгоритмы для решения
оптимизационных задач линейного программирования. Ч.2. – Мн.: БГУИР, 1996.
3. Смородинский
С.С., Батин Н.В. Анализ и
аналитических моделей. - Мн.: БГУИР, 1997.
3. Дегтярев
Ю.И. Исследование операций. -
М.: Высшая школа, 1986.
УСЛОВНЫЕ СОКРАЩЕНИЯ
БР – базисное решение
БП –
базисная переменная
Условие
задачи.
Приложение.
+-----------------------------
¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦Вид огр.¦Значение¦
+--------+--------+--------+--
¦ -1.00¦ -1.00¦ -2.00¦ -3.00¦ -3.00¦ -2.00¦ E ¦ ¦
+--------+--------+--------+--
¦ 2.00¦ -1.00¦ 0.00¦ 6.00¦ -3.00¦ 0.00¦ == ¦ 0.00¦
¦ 2.00¦ 0.00¦ -2.00¦ 6.00¦ 0.00¦ -2.00¦ == ¦ 0.00¦
¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦ 0.00¦ 0.00¦ <= ¦ 8.00¦
¦ 0.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 1.00¦ <= ¦ 8.00¦
+-----------------------------
Вывод промежуточных
результатов оптимизации.
+-----------------------------
------------------------------
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+--------+--------+---
¦ 1¦ E ¦ -1.00¦ -1.00¦ -2.00¦ -3.00¦ -3.00¦ -2.00¦ 0.00¦
0.00¦ 0.00¦ 0.00¦ 0.00¦
¦ +----+--------+--------+------
----+--------+--------+---
¦ ¦ -W ¦ -4.00¦ 1.00¦ 2.00¦ -12.00¦ 3.00¦ 2.00¦ 0.00¦
0.00¦ 0.00¦ 0.00¦ 0.00¦
¦ +----+--------+--------+------
----+--------+--------+--
¦ ¦ X9 ¦ 2.00¦ -1.00¦ 0.00¦ 6.00¦ -3.00¦ 0.00¦ 0.00¦
0.00¦ 1.00¦ 0.00¦ 0.00¦
¦ ¦ X10¦ 2.00¦ 0.00¦ -2.00¦ 6.00¦ 0.00¦ -2.00¦ 0.00¦
0.00¦ 0.00¦ 1.00¦ 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.00¦ 0.00¦ 0.00¦ 1.00¦ 1.00¦ 1.00¦ 0.00¦
1.00¦ 0.00¦ 0.00¦ 8.00¦
+-----------------------------
------------------------------
Ведущий элемент
находится в 4 столбце и 1 строке.
Вывод промежуточных
результатов оптимизации.
+-----------------------------
------------------------------
¦ N¦ БП ¦ X1 ¦ X2 ¦ X3 ¦ X4 ¦ X5 ¦ X6 ¦ X7 ¦
X8 ¦ X9 ¦ X10 ¦Баз.Реш.¦
+--+----+--------+--------+---
----+--------+--------+--
¦ 2¦ E ¦ 0.00¦ -1.50¦ -2.00¦ 0.00¦ -4.50¦ -2.00¦ 0.00¦
0.00¦ 0.50¦ 0.00¦ 0.00¦
¦ +----+--------+--------+------
----+--------+--------+-
¦ ¦ -W ¦ 0.00¦ -1.00¦ 2.00¦ 0.00¦ -3.00¦ 2.00¦ 0.00¦
0.00¦ 2.00¦ 0.00¦ 0.00¦
¦ +----+--------+--------+------
----+--------+--------+
¦ ¦ X4 ¦ 0.33¦ -0.17¦ 0.00¦ 1.00¦ -0.50¦ 0.00¦ 0.00¦
0.00¦ 0.17¦ 0.00¦ 0.00¦
¦ ¦ X10¦ 0.00¦ 1.00¦ -2.00¦ 0.00¦ 3.00¦ -2.00¦ 0.00¦
0.00¦ -1.00¦ 1.00¦ 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.17¦ 0.00¦ 0.00¦ 1.50¦ 1.00¦ 0.00¦
1.00¦ -0.17¦ 0.00¦ 8.00¦
+-----------------------------
Информация о работе Решение оптимизационной задачи линейного программирования