Автор: Пользователь скрыл имя, 13 Сентября 2011 в 12:19, курсовая работа
Цель работы состоит в изучении различных классов задач математического программирования, а также методов их решения.
Данная работа актуально тем, что она содержит все характерные черты рассматриваемых в ней классов задач, рассматривает широкий круг методов решения этих задач и проводит их геометрическую интерпретацию. Работа является наглядным примером решения различных классов задач математического программирования.
Введение
Задание №1
-метод северо-западного угла
-метод минимального элемента
-метод двойного предпочтения
-метод потенциалов
-венгерский метод
Задание №2
-графический метод
-прямая задача
-двойственная задача
-симплекс-метод
-метод целочисленных форм
-метод ветвей и границ
Задание №3
-метод наискорейшего спуска
-метод золотого сечения
-метод Ньютона
-метод Нелдора-Мида
Задание №4
Заключение
Список литературы
х2=6
х1=5
L=50+54=104
Значение
целевой функции, полученное в методе
целочисленных форм, отличается от значения,
полученного в графическом методе: графически
получилось, что L = 102, а по методу целочисленных
форм вышло, что L = 104; различие связано
с тем, что графический метод менее точный.
2.9.
Метод ветвей и границ.
L=10x1+9x2→max (1)
10x1+12x2 ≤ 120 (2)
13x1+9x2 ≤ 117 (3)
x1≥0, x2 ≥0
xj – целые.
x1 є [0;9], (4)
x2
є [0;10], (5)
Каждую итерацию обозначим t, на каждой итерации имеется нижняя граница (оценка) Wt.
t = 1:
На первой итерации возьмём W1 = 0.
Основной список на первой итерации содержит 1 задачу, содержащую (1), (2), (3), (4), (5).
Выбираем задачу 1 из списка и решаем её:
x1 = ,
x2 =,
W = 10·54/11 + 9·65/11= 102 > 0.
Так как оптимальное решение не целочисленное и полученное значение целевой функции больше, чем W1, то выбираем x2 и вносим в основной список 2-ой задачи линейного программирования.
Задача 2 содержит (1), (2), (3), (4), вместо (5):
5≤x1≤9, (4)
0≤x2≤10, (6)
Задача 3 содержит (1), (2), (3), (4), вместо (5):
0≤x1≤4, (4)
0≤x1≤10, (7)
Принимаем на второй итерации W2 = W1 = 0.
Таблица 33.
| Б.п. | Св. чл. | Св. пер. | |||
| Х1 | Х2 | Х3 | Х4 | ||
| Y1 | 120
-50 |
10
-10 |
12
0 |
0
0 |
0
0 |
| Y2 | 117
-65 |
13
-13 |
9
0 |
0
0 |
0
0 |
| Y3 |
5
5 |
1
1 |
0
0 |
0
0 |
0
0 |
| Y4 | 10
0 |
0
0 |
1
0 |
0
0 |
0
0 |
| L | 0
-50 |
10
-10 |
9
0 |
0
0 |
0
0 |
Таблица 34.
| Б.п. | Св. чл. | Св. пер. | |||
| Y3 | Х2 | Х3 | Х4 | ||
| Y1 | 70
-624/9 |
-10
156/9 |
-12
-12/9 |
0
0 |
0
0 |
| Y2 |
52
52/9 |
-13
13/9 |
9
1/9 |
0
0 |
0
0 |
| Х1 | 5
0 |
1
0 |
0
0 |
0
0 |
0
0 |
| Y4 | 10
-52/9 |
0
13/9 |
1
-1/9 |
0
0 |
0
0 |
| L | -50
-52 |
-10
13 |
9
-1 |
0
0 |
0
0 |
Таблица 35.
| Б.п. | Св. чл. | Св. пер. | |||
| Y3 | Y2 | Х3 | Х4 | ||
| Y1 | 6/9 | 66/9 | -12/9 | 0
|
0
|
| Х2 | 52/9
|
-13/9 | 1/9 | 0
|
0 |
| Х1 | 5
|
1
|
0
|
0
|
0
|
| Y4 | 38/9
|
13/9 | -1/9
|
0
|
0
|
| L | -102
|
3 | -1 | 0
|
0 |
x1=5
x2=
L=102
Т.к.
оптимальное решение
Таблица 36.
| Б.п. | Св. чл. | Св. пер. | |||
| Х1 | Х2 | Х3 | Х4 | ||
| Y1 | 120
-40 |
10
-10 |
12
0 |
0
0 |
0
0 |
| Y2 | 117
-52 |
13
-13 |
9
0 |
0
0 |
0
0 |
| Y3 |
4
4 |
1
1 |
0
0 |
0
0 |
0
0 |
| Y4 | 10
0 |
0
0 |
1
0 |
0
0 |
0
0 |
| L | 0
-40 |
10
-10 |
9
0 |
0
0 |
0
0 |
Таблица 37.
| Б.п. | Св. чл. | Св. пер. | |||
| Y3 | Х2 | Х3 | Х4 | ||
| Y1 |
80
80/12 |
-10
-10/12 |
12
1/12 |
0
0 |
0
0 |
| Y2 | 65
-60 |
-13
90/12 |
9
1/9 |
0
0 |
0
0 |
| Х1 | 4
0 |
1
0 |
0
0 |
0
0 |
0
0 |
| Y4 | 10
-80/12 |
0
10/12 |
1
-1/12 |
0
0 |
0
0 |
| L | -40
-60 |
-10
90/12 |
9
-9/12 |
0
0 |
0
0 |