Автор: Пользователь скрыл имя, 13 Сентября 2011 в 12:19, курсовая работа
Цель работы состоит в изучении различных классов задач математического программирования, а также методов их решения.
Данная работа актуально тем, что она содержит все характерные черты рассматриваемых в ней классов задач, рассматривает широкий круг методов решения этих задач и проводит их геометрическую интерпретацию. Работа является наглядным примером решения различных классов задач математического программирования.
Введение
Задание №1
-метод северо-западного угла
-метод минимального элемента
-метод двойного предпочтения
-метод потенциалов
-венгерский метод
Задание №2
-графический метод
-прямая задача
-двойственная задача
-симплекс-метод
-метод целочисленных форм
-метод ветвей и границ
Задание №3
-метод наискорейшего спуска
-метод золотого сечения
-метод Ньютона
-метод Нелдора-Мида
Задание №4
Заключение
Список литературы
Таблица 27.
| Б.п. | Св. чл. | Св. пер. | |||
| Х2 | Х1 | Y3 | Y4 | ||
| Y2 | 30|66
|
-10|66 | 12|66
|
12/66 | -10|66
|
| Y1 | 324/792 | 156/792
|
9|66 | -9/66 | 156|792 |
| W` | -81000/792
|
-2448/792
|
-324/66
|
-324/66
|
2448/792 |
Так
как в строке L в ячейках все значения
отрицательны, то достигнуто оптимальное
решение.
Y2==
Y1==
W`===102
Эти значения сходятся с полученными значениями в прямом симплекс-методе и значения х1, х2, так же сходятся.
Вывод: значения L, полученные в графическом методе прямой и двойственной задачи сходятся со значениями, полученными в результате решения прямого и двойственного симплекс-метода, во всех случаях L =
2.6. Математическая постановка ЛЦП: требуется найти максимум или минимум линейной функции n-переменных L=L(x1, x2, … ,xn) = при ограничениях следующего вида:
, где ,
, где ,
, где , .
xj
– целые числа.
2.7.
Графический метод решения
задач ЛЦП.
L=10x1+9x2→max
10x1+12x2 ≤ 120
13x1+9x2 ≤ 117
x1≥0,
x2 ≥0
Решим
задачу ЛЦП без условия
А(), L =
Рисунок 3.
Цел.ф. ………….
Снова решаем задачу линейного программирования при заданных условиях и ограничениях.
Цел.ф.
А(4;5), L=10∙4+9∙5=85
2.8.
Метод целочисленных
форм.
L=10x1+9x2→max
10x1+12x2 ≤ 120
13x1+9x2 ≤ 117
x1≥0, x2 ≥0
xj – целые.
Воспользуемся решением прямого симплекс-метода:
Таблица 28.
| Б.п. | Св. чл. | Св. пер. | |
| Y2 | Y1 | ||
| Х2 | 65|11
|
-5|33 | 13|66 |
| Х1 | 54|11
|
2|11 | -3|22 |
| L | -1125|11
|
-5|11
|
-9|22 |
x1=4 ,
x2=5,
L = 102,
L =,
так как решение не является
целочисленным вводим
дополнительное ограничение:
x1=-
у2+ у1+ у3
у3=-+
у2+ у1
Строим новую таблицу с дополнительным ограничением и проводим все те действия, которые проводятся при решении симплекс-методом.
Таблица 29.
| Б.п. | Св. чл. | Св. пер. | |
| Y2 | Y1 | ||
| Х2 | 65|11
-13/99 |
-5|33
26/99 |
13|66
26/18 |
| Х1 | 54|11
1/11 |
2|11
-2/11 |
-3|22
-1 |
| У3 |
-1\11
2\3 |
2/11
-4/3 |
-3/22
-22/3 |
| L | -1125|11
3/11 |
-5|11
-6/11 |
-9|22
-3 |
х2
=-у2-у3
у4 =-
+у2+у3
Таблица 30.
| Б.п. | Св. чл. | Св. пер. | |
| Y2 | Y3 | ||
| Х2 | 572|99 | 1|9 | 13|9 |
| Х1 | 5 | 0 | -1 |
| У1 | 2\3 | -4/3 | -22/3
|
| L | -102 | -1 | -3 |
В
строке L в ячейках все значения отрицательны,
значит, достигнуто оптимальное решение
без условия целочисленности.
х2=
х1=5
L=50+=102
Таблица 31.
| Б.п. | Св. чл. | Св. пер. | |
| Y2 | Y3 | ||
| Х2 | 572|99
2/9 |
1|9
-1 |
13|9
-13/9 |
| Х1 | 5
0 |
0
0 |
-1
0 |
| У1 | 2\3
-8/3 |
-4/3
12 |
-22/3
52/3 |
| У4 | -2/9
-2 |
1/9
9 |
13/9
13 |
| L | -102
-2 |
-1
9 |
-3
13 |
Таблица 32.
| Б.п. | Св. чл. | Св. пер. | |
| Y4 | Y3 | ||
| Х2 | 6 | -1 | 0 |
| Х1 | 5 | 0 | -1 |
| У1 | -2 | 12
|
10
|
| У2 | -2
|
9
|
13 |
| L | -104 | 9 | 10 |