Автор: Пользователь скрыл имя, 13 Сентября 2011 в 12:19, курсовая работа
Цель работы состоит в изучении различных классов задач математического программирования, а также методов их решения.
Данная работа актуально тем, что она содержит все характерные черты рассматриваемых в ней классов задач, рассматривает широкий круг методов решения этих задач и проводит их геометрическую интерпретацию. Работа является наглядным примером решения различных классов задач математического программирования.
Введение
Задание №1
-метод северо-западного угла
-метод минимального элемента
-метод двойного предпочтения
-метод потенциалов
-венгерский метод
Задание №2
-графический метод
-прямая задача
-двойственная задача
-симплекс-метод
-метод целочисленных форм
-метод ветвей и границ
Задание №3
-метод наискорейшего спуска
-метод золотого сечения
-метод Ньютона
-метод Нелдора-Мида
Задание №4
Заключение
Список литературы
Таблица 43.
| Б.п. | Св. чл. | Св. пер. | |||
| Х1 | Y4 | Х3 | Х4 | ||
| Y1 | 72
-40 |
-10
-10 |
12
0 |
0
0 |
0
0 |
| Y2 | 81
-52 |
-13
-13 |
9
0 |
0
0 |
0
0 |
| Y3 |
4
4 |
1
1 |
0
0 |
0
0 |
0
0 |
| Х2 | 4
0 |
0
0 |
1
0 |
0
0 |
0
0 |
| L | -36
-40 |
10
-10 |
-9
0 |
0
0 |
0
0 |
Таблица 44.
| Б.п. | Св. чл. | Св. пер. | |||
| Y3 | Y4 | Х3 | Х4 | ||
| Y1 | 32 | -10 | -12 | 0
|
0
|
| Y2 | 29
|
-13 | -9 | 0
|
0 |
| Х1 | 4
|
1
|
0
|
0
|
0
|
| Х2 | 4
|
0 | 1
|
0
|
0
|
| L | -76
|
-10 | -9 | 0
|
0 |
x1=4
x2=4
L=76
Основной список задач пуст, вычисления прекращаются.
L= 76<85<100=>L=85-оптимальное решение.
ЧЁ ЗА 100? Не пиши её!
L=
76<85=>L=85-оптимальное решение.
Рисунок
сделай так! У мя не
правильно!
Вывод:
| Метод | х1 | х2 | W |
| Решение задачи ЛП графически | |
102 | |
| Симплекс-метод | |
102 | |
| Графический метод решения задач ЛЦП | |
102 | |
| Метод целочисленных форм | 5 | 6 | 104 |
| Метод
ветвей и
границ |
4 | 5 | 85 |
Наименьшее
значение W получилось при расчёте методом
ветвей и границ=>он является оптимальным.
Задание № 3
Методы
нелинейного программирования
3.1. Задание
для предложенного варианта.
3.1. Построить конусы возможных направлений в угловых точках допустимого множества задачи ЛП.
3.2. Построить конусы, сопряженные к конусам возможных направлений в угловых точках допустимого множества задачи ЛП.
3.3. Проверить условия оптимальности Куна-Таккера в угловых точках допустимого множества задачи ЛП. Показать, что эти условия выполняются только в оптимальной точке.
3.4. Найти точку безусловного экстремума (минимума) для заданной целевой функции и начальной точки:
- методом наискорейшего спуска,
- методом золотого сечения,
- методом Ньютона.
3.5. Найти
решение задачи выпуклого программирования
методом возможных направлений или методом
Нелдора-Мида.
3.1.
F=(x1-8)2+(x2-15)2+(x1-8)∙(x2
10x1+9x2→max
10x1+12x2 ≤ 120
13x1+9x2 ≤ 117
x1≥0,
x2 ≥0
x0(0;7)
x*(8;15)
3.2.
Рисунок
4.
3.3.
Условие Куна-Таккера
F = (x12-16x1+64+x22-30x2+225) + (x1x2-15x1-8x2+120) = x12+x22+x1x2-31x1-38x2+409
F (xi;λi)
= x12+x22+x1x2-31x1-38x2+409+λ1(
=2x1+x2-31+10λ1+13λ2
=x1+2x2-38+12λ1+9λ2
=10x1+12x2-120
=13x1+9x2-117
Подставляем
координаты шести точек, не учитывая
λ.
Таблица 45.
| (0 ; 0) | (0 ; 9) | (9 ; 0) | (54/11;65/11) | (0 ; 7) | (8 ; 15) | |
| + | + | + | + | + | + | |
| + | + | + | + | + | + | |
| - | - | - | + | + | + | |
| - | - | + | + | + | + |
Из всех
угловых точек множества
F =
F (8; 15) = 0
F (0; 7) = 192
3.4.
Метод наискорейшего
спуска.
Градиент
(от лат. Gradiens — шагающий, растущий) — вектор,
показывающий направление наискорейшего
возрастания некоторой величины
, значение которой меняется от одной точки
пространства к другой. Мера возрастания или
убывания в пространстве какой-либо физической
величины при перемещении на единицу длины.
Таблица 46.
| № | З.ц.ф. | Решение |
| 1 | 192 | X(0) = (0; 7)
φ(X(0))=192 |
| 2 | 147 | h=20=1 X(1)
= X(0) + h=(0+1; 7+1) = (1; 8)
φ(X(1))=147 |
| 3 | 75 | h=21=2 X(2)
= X(1) + h=(1+2; 8+2) = (3; 10)
φ(X(2))=75 |
| 4 | 3 | h=22=4 X(3)
= X(2) + h=(3+4; 10+4) = (7; 14)
φ(X(3))=3 |
| 5 | 147 | h=23=8 X(4)
= X(3) + h=(7+8; 14+8) = (15; 22)
φ(X(4))=147 |