|
-
Задачі з математичного програмування
Задача 1.
Розв'язати графічно задачу лінійного програмування:
Задача 2.
Розв'язати симплекс-методом задачу лінійного програ¬мування:
Задача 3.
Для заданої задачі лінійного програмування побудувати двоїсту, розв'язати одну з пари двоїстих задач симплекс-методом і за її розв'язком знайти розв'язок двоїстої до неї:
Задача 4.
Розв'язати методом потенціалів транспортну задачу:
Q1 Q2 Q3 Q4 Q5 а
P1 7 3 1 5 4 30
Р2 7 5 8 3 2 25
Р3 6 4 8 3 2 45
Р4 3 1 7 6 2 20
b 10 35 15 25 35
Задача 5.
Одним із методів відтинання розв'язати задачу цілочи¬слового програмування:
-
Контрольна робота з математичного програмування. Варіант 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. Знайти розв’язок двоїстої задачі та дати економічну інтерпретацію отриманого розв’язку.
-
Канонічні форми задач лінійного програмування
Зміст
Вступ 3
1. Постановка завдання лінійного програмування 5
2. Канонічна форма завдання лінійного програмування 6
Список використаної літератури. 10
-
Задачі з матпрограмування
План
Завдання №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
Отримана таблиця свідчить про те, що ми отримали оптимальний розв’язок, про це свідчить той факт, що коефіцієнти в останньому рядочку є додатними. Отже, .
-
Контрольна робота (задачі) з математичного програмування
Завдання №1 …………………………………………………………………3
Дайте геометричне розв’язання задачі лінійного програмування.
Завдання №2 …………………………………………………………………4
Записати задачу 1 в канонічній формі і розв’язати із застосуванням симплекс-методу.
Список використаної літератури …………………………………………..6
-
Лінійне програмування
Зміст :
1. 2
2. 4
Література 5
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
Таким чином,
.
Л
-
Оптимізація використання матеріалів методом лінійного програмування
ВСТУП 3 1 СУТЬ МАТЕРІАЛЬНО-ТЕХНІЧНОГО ЗАБЕЗПЕЧЕННЯ 5 2 ОСОБЛИВОСТІ ОРГАНІЗАЦІЇ МАТЕРІАЛЬНО-ТЕХНІЧНОГО ЗАБЕЗПЕЧЕННЯ Й СКЛАДСЬКОГО ГОСПОДАРСТВА 19 3 ЗАСТОСУВАННЯ МЕТОДІВ ЛІНІЙНОГО ПРОГРАМУВАННЯ ДЛЯ РАЦІОНАЛЬНОГО ВИКОРИСТАННЯ МАТЕРІАЛЬНО-ТЕХНІЧНИХ І СИРОВИННИХ РЕСУРСІВ 27 ВИСНОВОК 34 СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 38
-
Оптимізація використання матеріалів методом лінійного програмування
ВСТУП 3
1 СУТЬ МАТЕРІАЛЬНО-ТЕХНІЧНОГО ЗАБЕЗПЕЧЕННЯ 5
2 ОСОБЛИВОСТІ ОРГАНІЗАЦІЇ МАТЕРІАЛЬНО-ТЕХНІЧНОГО ЗАБЕЗПЕЧЕННЯ Й СКЛАДСЬКОГО ГОСПОДАРСТВА 19
3 ЗАСТОСУВАННЯ МЕТОДІВ ЛІНІЙНОГО ПРОГРАМУВАННЯ ДЛЯ РАЦІОНАЛЬНОГО ВИКОРИСТАННЯ МАТЕРІАЛЬНО-ТЕХНІЧНИХ І СИРОВИННИХ РЕСУРСІВ 27
ВИСНОВОК 34
СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ 38
-
Інструментальні комплекси для розробки статичних експериментальних систем
Вступ 2
Інструментальні комплекси для розробки статичних експертних систем 4
Оболонки експертних систем 6
Мови програмування високого рівня 7
Мови об єктно-орієнтованого програмування 8
Середовище програмування що підтримує декілька парадигм 10
Додаткові модулі 12
Висновки 13
Література 14
-
Задачи по математическому программированию
Задача 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
Cгенерировано за 0.094897 секунд
|
Наша колекція рефератів містить понад 60 тис. учбових матеріалів! На сайті «Рефсмаркет» Ви можете скористатись системою пошуку готових робіт, або отримати допомогу з підготовки нового реферату практично з будь-якого предмету.
Нам вдячні мільйони студентів ВУЗів України, Росії та країн СНД. Ми не потребуємо зайвої реклами, наша репутація та популярність говорять за себе.
Від партнерів
загрузка...
|
|
|