Задачі з математичного програмування

Задача 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

Cмотрите также:

Контрольна робота з математичного програмування. Варіант 4

Завдання 1 2 1. Побудувати математичну модель задачі лінійного програмування. 2. Звести дану задачу до канонічного вигляду. Два вироби В1 і В2 обробляються послідовно на трьох верстатах. Ко-жен виріб типу В1 потребує 1 год. для обробки на I-му верстаті, 2 год. – на II-му верстаті і A = 2,45 год. на III-му. Кожен виріб типу В2 потребує для обро-бки 2 год., A = 2,45 год. і 3 год. відповідно на I-му, II-му і III-му верстатах. Час роботи на I-му верстаті не повинен перевищувати 10N = 60 год., на II-му – 15N = 90 год., на III-му – 50 год. Скласти план виробництва при максима-льному прибутку, якщо відомо, що продаж одного виробу типу В1 приносить прибуток 5 грн., а типу В2 – 3 грн. Завдання 2 4 Завдання 2 Розв’язати задачу лінійного програмування графічним методом. Завдання 3 6 Завдання 3 Розв’язати систему лінійних рівнянь методом повного виключення змінних (методом Гаусса) за допомогою розрахункових таблиць. Завдання 4 8 Завдання 4 1. Розв’язати симплекс-методом задачу лінійного програмування. 2. Побудувати двоїсту задачу до даної задачі лінійного програмуван-ня. 3. Знайти розв’язок двоїстої задачі та дати економічну інтерпретацію отриманого розв’язку.

Задачі з лінійного програмування

1. Дайте геометричне розв’язання задачі лінійного програмування. Розв’язок : Систему рівнянь перетворимо наступним чином : Побудуємо графіки відповідних лінійних функцій : 1 2 3 3 0 3 0 0 3 0 3 4 6 1 4 Таким чином (див Рис.1.), досліджувана площина є закритою і обмежується ABCD. Максим функції досягається в точці C – перетин прямих Ох і 2 : , тоді . Рис.1. 2. Записати задачу 1 в канонічній формі і розв’язати із застосуванням симплекс-методу. Розв’язок : Канонічна форма матиме вигляд : Розв’яжемо за допомогою симплексної таблиці № Сіб Базис План 2 2 0 0 0 А1 А2 А3 А4 А5 1. 0 А3 -3 -1 -1 1 0 0 2. 0 А4 18 2 3 0 1 0 3. 0 А5 1 -1 1 0 0 1 4. Zi-Cj 0 -2 -2 0 0 0 1. 0 А3 -2 -2 0 1 0 1 2. 0 А4 15 5 0 0 1 -3 3. 2 А2 1 -1 1 0 0 1 4. Zi-Cj 2 -4 0 0 0 2 1. 2 А1 1 1 0 -1/2 0 -1/2 2. 0 А4 10 0 0 5/2 1 -1/2 3. 2 А2 2 0 1 -1/2 0 ½ 4. Zi-Cj 6 0 0 -2 0 0 1. 2 А1 3 1 0 0 1/5 -3/5 2. 0 А3 4 0 0 1 2/5 -1/5 3. 2 А2 4 0 1 0 1/5 2/5 4. Zi-Cj 14 0 0 0 4/5 -2/5 1. 2 А1 9 1 3/2 0 ½ 0 2. 0 А3 6 0 ½ 1 ½ 0 3. 0 А5 10 0 5/2 0 ½ 1 4. Zi-Cj 18 0 1 0 1 0 Таким чином, .

Задачі з матпрограмування

План Завдання №1 …………………………………………………………………3 Завдання №2 …………………………………………………………………4 Список використаної літератури …………………………………………..6 Завдання №1 Дайте геометричне розв’язання задачі лінійного програмування. Розв’язання На координатній площині зобразимо всі задані нерівності і визначимо область, в якій знаходиться розв’язок задачі: Замальована область, є областю в якій знаходиться розв’язок задачі. На цьому ж малюнку зобразимо пунктирною лінією графік функції: Шуканим розв’язком заданої задачі буде та точка замальованою області, яку останньою перетне лінія графіку функції (пунктирна) рухаючись по напрямку . З малюнка видно, що такою точкою буде точка з координатами (9;0). Отже, Завдання №2 Записати задачу 1 в канонічній формі і розв’язати із застосуванням симплекс-методу. Розв’язання Запишемо канонічну форму задачі лінійного програмування, тобто всі знаки нерівностей замінюємо на знаки рівності: Початковим буде наступний розв’язок: Для отримання шуканого розв’язку застосуємо симплекс-метод розв’язання задачі лінійного програмування. Для цього на основі системи рівнянь складемо допоміжну першу симплекс таблицю: 2 2 0 0 0 Бз Сб Ро 1 0,00 3,00 1,00 1,00 -1,00 0,00 0,00 2 0,00 18,00 2,00 3,00 0,00 1,00 0,00 3 0,00 -1,00 1,00 -1,00 0,00 0,00 -1,00 F 0,00 -2,00 -2,00 0,00 0,00 0,00 Використовуючи метод Жордана-Гауса проводимо ітерацію відносно визначеного нами елемента. Після проведення ітерації ми отримаємо наступну другу симплекс таблицю: 2 2 0 0 0 Бз Сб Ро 1 0,00 -6,00 0,00 -0,50 -1,00 -0,50 0,00 2 2,00 9,00 1,00 1,50 0,00 0,50 0,00 3 0,00 -10,00 0,00 -2,50 0,00 -0,50 -1,00 F 18,00 0,00 1,00 0,00 1,00 0,00 Отримана таблиця свідчить про те, що ми отримали оптимальний розв’язок, про це свідчить той факт, що коефіцієнти в останньому рядочку є додатними. Отже, .

Тема: Задачі з математичного програмування

Каталог пособий и учебных материалов | Математическое программирование | Задача | Страниц: 9 | Год: 2007 | Размер: 91 кб. | Стоимость: 100 грн. | Смотреть | Купить

Задачі з математичного програмування

Cмотрите также: