Меню

Реклама

TOP реферати

Від партнерів

Цікаве

загрузка...

Тема: «Задачи по математическому программированию» (ID:19942)

| Размер: 64 кб. | Объем: 30 стр. | Стоимость: бесплатно | Добавлена: 07.12.2007 | Код продавца: 1 |
СодержаниеЗадача 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
ЛитератураНет литературы.
Просмотр
ПросмотрПросмотреть с сайта...
Скачивание
СкачатьСкачать работу в архиве..
Рекомендуємо також переглянути наступні реферати та курсові роботи:
  • Управление системой доставки продукции
  • Сущность, цели и задачи маркетинга.
  • "Учет поставляемой продукции
  • "Учет поставляемой продукции
  • Сущность маркетинга и его роль в экономике
  • Уголовный закон
  • Рынок и его задачи. Маркетинг
  • "Проектирование и создание прикладных программ в среде приложений пакета Microsoft Office"
  • Финансовый менеджмент как система управления финансами
  • Предмет задачи, система показателей статистики рынка
  • Понятие, содержание и источники уголовно-исполнительного законодательства
Cгенерировано за 0.028542 секунд

Наша колекція рефератів містить понад 60 тис. учбових матеріалів! На сайті «Рефсмаркет» Ви можете скористатись системою пошуку готових робіт, або отримати допомогу з підготовки нового реферату практично з будь-якого предмету.

Нам вдячні мільйони студентів ВУЗів України, Росії та країн СНД. Ми не потребуємо зайвої реклами, наша репутація та популярність говорять за себе.

Замовити реферат

Оновлення

Реклама

Від партнерів

загрузка...