Меню

Реклама

TOP реферати

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

Цікаве

загрузка...

Тема: «Задачі з математичного програмування» (ID:20105)

| Размер: 91 кб. | Объем: 9 стр. | Стоимость: бесплатно | Добавлена: 11.12.2007 | Код продавца: 1 |
СодержаниеЗадача 1.Розв’язати задачу лінійного програмування графічним методом



Знайдемо точку мінімума

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


x1 x2
x3 3 -1 1

x4 10 -1 2
x5 36 4 1
Lmin 0 -2 3




Вибрали генеральний стовпчик, оскільки 3>0.
генеральну строку берем по х3, оскільки(3/1)<(10/2)<(36/1)
Перерахуємо таблицю
x1 x3
x2 3 -1 1
x4 4 1 -2

x5 33 5 -1
Lmin -9 1 -3





Вибрали генеральний стовпчик, оскільки 1>0.
генеральну строку берем по х4, оскільки(4/1)<(33/5)
Перерахуємо таблицю
x4 x3
x2 7 1 -1
x1 4 1 -2
x5 13 -5 9
Lmin -13 -1 -1



Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-13
x2=7 x1=4 x5=13 x4=x3=0
Задача 3. Для даної задачі лінійного програмування побудувати двоїсту, розв’язати одну з пари двоїстих задач симплекс-методом і за її розв’язком знайти розв’язок двоїстої до неї

Запишемо двоїсту задачу

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

x1 x2
x3 3 -1 1
x4 10 -1 2
x5 36 6 1

Lmin 0 1 -9




Вибрали генеральний стовпчик, оскільки 1>0.
генеральну строку берем по х5, оскільки 6>0
Перерахуємо таблицю
x5 x2
x3 9 1/6 7/6
x4 46 1/6 13/6
x1 6 1/6 1/6
Lmin -6 -1/6 -55/6




Оскільки коефіцієнти при цільовій функції <0, то знайдене рішення оптимальне, тобто Lmin=-6, а Lmax=6
x2=0 x1=6 x5=0 x4=46 x3=9
х1 х2 х3 х4 х5
у4 у5 у1 у2 у3


y1=0 y3=1/6 y2=0 y5=55/6 y4=0 F=6
Задача 4. Розв’язати методом потенціалів транспортну задачу
Q1 Q2 Q3 Q4 Q5 a
P1 8 6 7 3 4 50
P2 7 4 9 3 4 50
P3 6 1 4 5 2 55
P4 7 8 3 4 2 50
b 35 30 50 25 65
Знайдемо опорний план методом найменшої вартості
Q1 Q2 Q3 Q4 Q5 a
P1 8(19) 6 (2) 7 (17) 3 (15) 4 (10) 50
P2 7 (20) 9 (3) 9 (18) 3 (16) 4 (11) 50
P3 6 (6) 1 (1) 4 (7) 5 (8) 2 (5) 55
P4 7 (13) 8 (4) 3 (12) 4 (14) 2 (9) 50
b 35 30 50 25 65
Цифри в дужках вказують порядок заповнення елементів в матриці Х0
Х0




0 0 25 25 0 25 25 0
35 0 15 0 0 15 35 0
0 30 0 0 25 30 25 0
0 0 10 0 40 40 10 0

35 30 10 25 25

0 0 25 0 40

15 0

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


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


Розв’яжемо задачу симплекс-методом
x1 x2
x3 -3 1 -1
x4 10 -1 2
x5 -24 -5 -6
Lmin 0 1 -2




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




Вибрали генеральний стовпчик, оскільки 8/3>0.
генеральну строку берем по х1, оскільки 1/(11/6)<4/(5/6)
Перерахуємо таблицю
x3 x5
x1 6/11 6/11 -1/11
x4 38/11 16/11 1/11
x2 39/11 -5/11 -1/11
Lmin 72/11 -16/11 -1/11




Знайдене рішення оптимальне, але розв'язки мають бути цілими числами, тому використаємо перший алгоритм Гоморі
x1=6/11-(6/11х3-1/11х5)
Побудуємо пряму відсікання
хвід= х6=
Знайдемо оптимальне рішення, використовуючи пряму відсікання
Перерахуємо таблицю
x3 x5
x1 6/11 6/11 -1/11
x4 38/11 16/11 1/11
x2 39/11 -5/11 -1/11
x6 -6/11 -6/11 -10/11

Lmin 72/11 -16/11 -1/11





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



x3 x6
x1 3/5 3/5 -1/10
x4 17/5 7/5 1/10
x2 18/5 -2/5 -1/10
x5 3/5 3/5 -11/10
Lmin 33/5 -7/5 -1/10





Знайдене рішення оптимальне, але розв'язки мають бути цілими числами, тому використаємо другий алгоритм Гоморі
x2=18/5-(-2/5х3-1/10х6)
Побудуємо пряму відсікання
хвід= х7=
Знайдемо оптимальне рішення, використовуючи пряму відсікання
Перерахуємо таблицю
x3 x6
x1 3/5 3/5 -1/10
x4 17/5 7/5 1/10
x2 18/5 -2/5 -1/10
x5 3/5 3/5 -11/10
х7 -3/5 -3/5 -3/20
Lmin 33/5 -7/5 -1/10






Вибрали генеральну строку, оскільки -3/5<0.
генеральний стовпчик берем по х6. Перерахуємо таблицю
x3 x7
x1 1 1 -2/3
x4 3 1 2/3
x2 4 0 -2/3
x5 5 5 -22/3
х6 4 4 -20/3
Lmin 7 -1 -2/3





Оскільки коефіцієнти при цільовій функції <0 і х1 та х2 - цілі, то знайдене рішення оптимальне, тобто Lmin=7, a Lmax=-7
x4=3 x2=4 x1=1 x3=0 x5=5 x6=4 x7=0
ЛитератураНет литературы
Просмотр
ПросмотрПросмотреть с сайта...
Скачивание
СкачатьСкачать работу в архиве..
Рекомендуємо також переглянути наступні реферати та курсові роботи:
  • Контрольна робота з математичного програмування. Варіант 4
  • Задачі з математичного програмування
  • Інструментальні комплекси для розробки статичних експериментальних систем
  • Задачі з матпрограмування
  • Моделювання в економічному аналізі
  • Економіко-математичні моделі в інформаційних системах
  • Канонічні форми задач лінійного програмування
  • Задачі динамічного програмування
  • Контрольна робота (задачі) з математичного програмування
  • Визначення прискорення тіла вільного падіння за допомогою математичного маятника (лабораторна робота)
  • Формування пізнавальної активності у дітей старшого дошкільного віку засобами дидактичних ігор математичного змісту
Cгенерировано за 0.070887 секунд

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

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

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

Оновлення

Реклама

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

загрузка...