Тема: «Задачі з лінійного програмування» (ID:28860)

Задача 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.
Одним із методів відтинання розв'язати задачу цілочи¬слового програмування:

Завдання 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