Поиск работ


Заказать реферат





Информация о работе (ID:3505)












загрузка...
Название Задачи по математическому программированию
Раздел Математическое программирование
Тип работы Контрольная
Объем 30 стр.
Цена бесплатно
Размер 64 kb
Добавлена 07.12.2007
Переходов 548
Скачать Скачать работу в архиве..
NEW!
Просмотр с сайта!
Просмотреть с сайта...
Содержание Задача 1. Розв'язати графічно задачу лінійного програмування:






Задача2. Розв'язати симплекс-методом задачу лінійного програмування:



Розв’яжемо задачу симплекс-методом

x1 x2
x3 15 -1 3
x4 7 1 1
x5 -10 -2 -5
Lmin 0 1 3







Вибрали генеральнeу строку, оскільки -10<0.
5/10>2/10, тому генеральна стовпчик береться по х1
Перерахуємо таблицю
x5 x2
x3 20 -1/2 11/2
х4 2 ½ -3/2
х1 5 -1/2 5/2
Lmin -5 ½ 1/2







Вибрали генеральний стовпчик, оскільки 1/2>0.
1/2>0, тому генеральна строка береться по х4
Перерахуємо таблицю


x4 x2
x3 22 1 4
х5 4 2 -3
х1 7 1 1
Lmin -7 -1 2







Вибрали генеральний стовпчик, оскільки 2>0.
7/1>22/4, тому генеральна строка береться по х3
Перерахуємо таблицю
x5 x3
x2 11/2 ¼ ¼
х4 41/2 11/4 ¾
х1 3/2 ¾ -1/4
Lmin -18 -3/2 -1/2






Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-18
a Lmax=18
x4=41/2
x2=11/2
x1=3/2
x3=x5=0
Задача З. Для заданої задачі лінійного програмування побудува¬ти двоїсту, розв'язати одну з пари двоїстих задач симплекс-методом і за її розв'язком знайти розв'язок двоїстої до неї:

Двоїста задача матиме вигляд

Розв’яжемо двоїсту задачу симплекс-методом



y1 y2 y3
y4 1 -1 1 -1
y5 3 3 1 2
Zmin 0 15 7 2






Вибрали генеральний стовпчик, оскільки 15>0.
3>0, тому генеральна строка береться по y5
Перерахуємо таблицю
y5 y2 y3
y4 2 1/3 4/3 -1/3
y1 1 1/3 1/3 2/3
Zmin -15 -5 2 -8







Вибрали генеральний стовпчик, оскільки 2>0.
6/4<3, тому генеральна строка береться по y4
Перерахуємо таблицю
y5 y4 y3
y2 3/2 ¼ ¾ -1/4
y1 ½ ¼ -1/4 ¾
Zmin -18 -11/2 -3/2 -15/2





Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто zmin=-18
a Zmax=18
y1=1/2
y2=3/2
y5=y4=y3=0

х1 х2 х3 х4 х5
у4 у5 у1 у2 у3


x1=3/2
x5=15/2
x2=11/2
x3=x4=0
L=18
Задача 4. Розв'язати методом потенціалів транспортну задачу:

Q1 Q2 Q3 Q4 Q5 a
P1 2 8 4 6 3 95
P2 3 2 5 2 6 55
P3 6 5 8 7 4 40
P4 3 4 4 2 1 60
b 30 90 80 20 30

Знайдемо опорний план методом найменшої вартості

Q1 Q2 Q3 Q4 Q5 a
P1 2 (12) 8 (18) 4 (17) 6 (8) 3 (4) 95
P2 3 (10) 2 (9) 5 (11) 2 (7) 6 (3) 55
P3 6 (13) 5 (19) 8 (20) 7 (6) 4 (2) 40
P4 3 (14) 4 (15) 4 (16) 2 (5) 1 (1) 60
b 30 90 80 20 30

Цифри в дужках вказують порядок заповнення елементів в матриці Х0

Х0





30 0 65 0 0 30 65 0
0 55 0 0 0 55 0
0 25 15 0 0 25 15
0 10 0 20 30 30 20 10 0

30 55 65 20 30

0 10 15 0 0

25 0

0

Заповнено 8 клітинок(5+4-1), отже план невироджений
Відповідне значення цільової функції дорівнює
L=30*2+65*4+55*2+25*5+15*8+10*4+20*2+30*1=785
Знайдемо потенціали:
Нехай u1=0
u1+v1=2=>v1=2
u1+v3=4=>v3=4
u3+v3=8=>u3=4
v2+u3=5=>v2=1
v2+u2=2=>u2=1
v2+u4=4=>u3=3
u3+v4=2=>v4=-1
u3+v5=1=>v5=-2
Перевіримо на оптимальність знайдене рішення
Q1 Q2 Q3 Q4 Q5 a ui
P1 2 30 2 1 8 4 65 4 -1 6 -2 3 95 0
P2 3 3 2 55 2
5 5 0 2 -1 6 55 1
P3 6 6 5 25 5
8 15 8
3 7 2 4 40 4
P4 5 3 4 10 4
7 4
2 20 2 1 30 1 60 3
b 30 90 80 20 30
vj 2 1 4 -1 -2
Умова оптимальності(Сij≥ ui+ vj) не виконується в двох клітинках, які виділені, тому план не оптимальний
Перерахуємо план і потенціали і перевіримо план на оптимальність
Q1 Q2 Q3 Q4 Q5 a ui
P1 2 30 2 1 8 4 65 4 2 6 1 3 95 0
P2 3 3 2 55 2 5 5 3 2 2 6 55 1
P3 6 6 5 35 5 8 5 8
6 7 5 4
40 4
P4 2 3 1 4 4 10 4
2 20 2 1 30 1
60 0
b 30 90 80 20 30
vj 2 1 4 2 1
4-8+5-4=-3
∆L=-3*10=-30
L=785-30=755
Заповнено 8 клітинок(5+4-1), отже план невироджений
Умова оптимальності(Сij≥ ui+ vj) не виконується в двох клітинках, які виділені, тому план не оптимальний
Перерахуємо план і потенціали і перевіримо план на оптимальність



Q1 Q2 Q3 Q4 Q5 a ui
P1 2 30 2 2 8 4 65 4 2 6 1 3 95 0
P2 2 3 2 55 2 4 5 2 2 1 6 55 0
P3 5 6 5 35 5 7 8 5 7 4 5 4 40 3
P4 2 3 2 4 4 15 4 2 20 2 1 25 1 60 0
b 30 90 80 20 30
vj 2 2 4 2 1
Заповнено 8 клітинок(5+4-1), отже план невироджений
Умова оптимальності(Сij≥ ui+ vj) виконується для всіх клітинок, тому план оптимальний
L=750


Задача 5. Одним із методів відтинання розв'язати задачу цілочи¬слового програмування:


Розв’яжемо задачу симплекс-методом

x1 x2
x3 5 -1 1
x4 8 1 1
x5 -2 1 -2
Lmin 0 -2 3







Вибрали генеральну строку, оскільки -2<0.
-2<0, тому генеральний стовпчик береться по х2
Перерахуємо таблицю

x1 x5
x3 4 -1/2 ½
x4 7 3/2 ½
x2 1 -1/2 -1/2
Lmin -3 -1/2 3/2







Вибрали генеральний стовпчик, оскільки 3/2>0.
8<14, тому генеральна строка береться по х3
Перерахуємо таблицю

x1 x3
x5 8 -1 2
x4 3 2 -1
x2 5 -1 1
Lmin -15 1 -3







Вибрали генеральний стовпчик, оскільки 1>0.
2>0, тому генеральна строка береться по х4
Перерахуємо таблицю

x4 x3
x5 19/2 ½ 3/2
x1 3/2 ½ -1/2
x2 13/2 ½ ½
Lmin -33/2 -1/2 -5/2







Знайдене рішення оптимальне, але розв'язки мають бути цілими числами, тому використаємо алгоритм перший
x1=3/2-(1/2х4-1/2х3)
Побудуємо пряму відсікання
хвід=
х6=
Знайдемо оптимальне рішення, використовуючи пряму відсікання
Перерахуємо таблицю

x4 x3
x5 19/2 ½ 3/2
x1 3/2 ½ -1/2
x2 13/2 ½ ½
x6 -1/2 -1/2 -1/2
Lmin -33/2 -1/2 -5/2








Вибрали генеральну строку, оскільки -1/2<0.
генеральний стовпчик береться по х4
Перерахуємо таблицю
x6 x3
x5 9 1 1
x1 1 1 -1
x2 6 1 0
х4 1 -2 1
Lmin -16 -1 -2







Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-16
x4=1
x2=6
x1=1 x3=0 x5=9
Список литературы Литература к работе...

©: 2011-2017 infoworks.ru | Статьи партнёров |