Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ЗАДАЧА ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ.
Нехай виробництво випускає однорідний продукт і володіє технологічними способами (технологіями).
При роботі за цими технологіями за одиницю часу підприємство отримує продукту відповідно q1, q2,…qn,. а виробничі витрати за одиницю часу складають p1, p2,…pn, одиниць.
Якщо план, по якому підприємство буде працювати за відповідними технологіями складає x1, x2,…xn – одиниць часу, то загальний випуск продукції буде рівний:
, (1.1)
а загальні витрати складають:
(1.2)
Відношення загальних витрат до загального об’єму продукту, що випускається визначає економічний показник, що називається собівартістю продукції.
(1.3)
Економічний зміст задачі: скласти такий план роботи підприємства (знайти час роботи по кожній технології), при якому собівартість продукції була б мінімальною і одночасно виконувались би деякі умови (обмеження).
При плануванні виробництва намагаються знизити цей показник, щоб випускати продукцію з найменшими витратами.
Функція виду
називається дробово-лінійною.
Собівартість є не єдиним економічним показником, що має дробово-лінійну структуру (наприклад, рентабельність).
Загальна задача Д-ЛП полягає у визначенні максимального (мінімального) значення функціоналу:
max(min) (1.4)
за умов:
(1.5)
, (1.6)
де pj, qj, ai, - деякі постійні числа, а
(1.7)
(коли , то знак можна віднести до чисельника).
Розглянемо на площині Ox1x2 цільову функцію:
(2.1)
звідки виразимо x2:
ввівши позначення: , отримаємо: x2=k x1.
x2=k x1 - пряма, яка проходить через початок координат.
F = C1
F = C2
x2
x1
Рис.1
Визначимо, як буде поводити себе кутовий коефцієнт k при монотонному зростанні функції . Для цього візьмемо похідну від k по .
(Fq2-P2)2 , а чисельник не залежить від F.
Отже, похідна має постійний знак і при зміні F кутовий коефіцієнт буде або тільки зростати, або тільки спадати і пряма буде повертатися в одну сторону. При повороті прямої в одному напрямку функціонал F також буде або зростати або спадати. Встановивши напрямок повороту для зростання F, знаходимо необхідну вершину многогранника поворотом прямої навколо початку координат.
При цьому можливі такі випадки:
x2
Fmin
Fmax
x1
Многокутник обмежений (Рис.2), максимум і мінімум є (стрілки на малюнку показують напрямок повороту прямої для збільшення F).
Рис.2
Fmin
Fmax
x2
x1
Область необмежена, але максимум і мінімум є (Рис.3).
Рис.3
Fmin
Fmax
x2
x1
Рис.4
Fmin
Fmax
x2
x1
Область необмежена, обидва екстремуми асимптотичні (Рис 5).
Рис.5
ПРИКЛАД.
Знайти максимум і мінімум функціоналу графічним методом.
при обмеженнях
РОЗВ’ЯЗАННЯ.
Fmax
Fmin
C
B
A
0
2
4
5
3
x2
x1
x1+x2=5
3x1-x2=11
-x1+3x2=7
Будуємо область допустимих розв’язків (Рис.6). Очевидно, що екстремальними будуть точки А і В.
Рис 6.
Визначимо де буде max, а де min. Виразимо з із цільової функції x2 :,
Так як при будь-якому F функція спадна, зі збільшенням F кутовий коефіцієнт k зменшується. Це відповідає повороту за годинниковою стрілкою. Отже, в тоці А(2;3) значення F буде найменшим, а у вершині В(4;1) – найбільшим. Обчислимо значення функціоналу в цих точках.
Оскільки FA < FB, то і .
В задачі дробово-лійнійного програмування обмеження лінійні і екстремум функціоналу досягається у вершині многогранника розв’язків.
Ця подібність із задачею лінійного програмування дозволяє розв’язувати задачі дробово-лінійного програмування звичайним симплекс-методом зі зміненим критерієм оптимальності.
РОЗГЛЯНЕМО ЗАДАЧУ.
Знайти максимум функціоналу:
(3.1)
при обмеженнях
(3.2)
(3.3)
(3.4)
РОЗВ’ЯЗУВАННЯ.
При чому, для F передбачаємо два рядка: у верхньому записуємо коефіцієнт чисельника pj, в нижньому – знаменника qj.
Табл.1
|
-x1 -x2 -x m |
1 |
|
|
y1= y2= - ym= |
a 11 a 12 a 1n a 21 a 22 a 2n a m1 a m2 a mn |
a 1 a 2 a m |
|
F1= F2= |
-p1 -p2 -p m -q1 -q2 -q m |
0 0 |
Кроками МЖВ відшукуємо опорний план, перетворюючи коефіцієнти стрічок .
Нехай в результаті k – кроків отримаэмо таблицю (Табл.2).
Табл.2
|
-y 1 -y 2 -y k -x s -x n |
1 |
|
|
Х1= Х2= Хk= Yr= Ym= |
b 11 b 12 b 1k b 1s b 1n b 21 b 22 b 2k b 2s b 2n b k1 b k2 b kk b ks b kn b r1 b r2 b rk b rs b rn b m1 b m2 b mk b ms b mn |
b 1 b 2 b k b r b m |
|
F1= F2= |
-p1‘ -p2‘ -pk -ps -pn -q1‘ -q2‘ -qk -qs -qn |
Тут вже всі bj невід’ємні. В рядках F1 і F2 з’явились вільні члени P(k) і Q(k), Q(k) 0, .
Fопор.п.
Fmax
Відшукання оптимального плану, тобто Fmax полягає у переміщенні від отриманої опорної вершини до сусідньої вершини по ребру, яка розміщена найближче до оптимальної вершини (Рис.7).
Рис.7.
Аналітично це означає зробити крок МЖВ з деяким brs. Задача полягає в тому, щоб встановити правило вибору brs (розв’язуючого елементу). Нехай ми вибрали brs. В новій (k+1) - ій таблиці замість P(k) буде стояти число:
(3.4)
Аналогічно замість i Q(k) буде стояти число:
(3.5)
Значення функціоналу на (k+1)- му кроці:
.
Далі знаходимо:
(3.6)
Позначимо:
(3.7)
З цими позначеннями отримаємо:
(3.8)
Дослідимо вираз (3.8)
Звідки слідує, що , так як по умові допустимості плану . Отже, завжди.
Іншими словами, коли за розв’язуючий стовпчик взяти стовпчик з
ds > 0, то після кроку МЖВ функціонал зменшується, а при виборі розв’язуючого стовпчика з ds < 0, F(k) > F(k+1) – функціонал збільшується.
При ds = 0, F(k+1)=F(k) функціонал не змінюється.
Визначник ds служить критерієм для вибору brs.
,
значення яких заносяться в додатковий рядок таблиці.
В стовпчику вільних членів в цьому рядку записуємо значення функціоналу, рівне відношенню F1 i F2
В результаті приходимо до таблиці (Табл.3):
Табл.3
|
-y 1 -y 2 -x s -x n |
1 |
|
|
х1= х2= ym= |
b 11 b 12 b 1s b 1n b 21 b 22 b 2s b 2n b m1 b m2 b ms b mn |
b 1 b 2 b m |
|
F1= F2= |
p 1 p 2 p s p n q 1 q 2 q s q rn |
0 0 |
|
dj= |
d 1 d 2 d s d n |
ПРИКЛАД.
Знайти максимум та мінімум функціоналу:
При виконанні обмежень:
РОЗВ’ЯЗАННЯ.
Складаємо початкову жорданову таблицю, заповнюючи коефіцієнтами функціоналу для чисельника та знаменника окремо два рядки F1 F2 (Табл.4).
Табл.4
|
1 |
-x 1 -х 2 -x 3 |
|
|
y1= y2= y3= |
-3 6 1 -1 7 2 -2 4 -1 |
2 12 -1 |
|
F1= F2= |
1 2 -1 3 1 5 |
0 0 |
Так як b3 = -1 < 0, то план х1 = х2 = х3 = 0 не є опорним.
Знайдемо опорний план. Відшукавши такий план, додаємо до таблиці ще один рядок, в який записуємо значення dj і функціоналу F (Табл.5) .
Табл.5
|
2 |
-x 1 -х 2 -y 3 |
|
|
y1= y2= x3= |
-5 10 1 -5 15 2 2 -4 -1 |
1 10 1 |
|
F1= F2= |
-3 2 1 7 -21 -5 |
-1 5 |
|
dj |
-8 -11 0 |
-1/5 |
Оскільки всі визначники dj недодатні, робимо висновок, що функціонал досягає мінімуму у вершині
x1 = 0, x2 = 0, x3 = 1
Для знаходження максимуму вибираємо за розв’язуючий другий стовпчик. Розв’язуючий елемент brs = 10. З цим елементом робимо крок МЖВ, перетворюючи всю таблицю, крім останнього рядка dj. В результаті отримаємо таблицю виду (Табл.6).
Табл.6
|
3 |
-x 2 -y 1 -y 3 |
|
|
x2= y2= x3= |
-1/2 1/10 1/10 5/2 -3/2 ½ 0 2/5 -3/5 |
1/10 17/2 7/5 |
|
F1= F2= |
-2 -1/5 4/5 -7/2 21/10 -29/10 |
28/5 7/5 |
|
dj= |
-92/5 11/10 11/5 |
-12/71 |
Елемент від’ємний – це означає, що максимум ще не досягнуто.
В першому стовпчику вибираємо за розв’язуючий елемент з ним робимо наступний крок МЖВ і отримаємо нову таблицю (Табл.7).
Табл.7
|
|
-y 2 -y 1 -y 3 |
|
|
x1= x2= x3= |
1/5 -1/5 1/5 2/5 -3/5 1/5 0 2/5 -3/5 |
9/5 17/5 7/5 |
|
F1= F2= |
4/5 -7/5 6/5 7/5 0 -11/5 |
28/5 19 |
|
dj= |
184/25 -133/5 878/25 |
28/15 |
Обчисливши в новій таблиці всі знову знаходимо один від’ємний, а тому робимо ще один крок МЖВ з елементом . В результаті отримали таблицю (Табл.8).
Табл.8
|
5 |
-y 2 -y 1 -x 3 |
|
|
x1= x2= y3= |
1/5 1/2 -1/10 2/5 3/2 -7/10 0 5/2 -3/2 |
5/2 11/2 7/2 |
|
F1= F2= |
4/5 -7/2 -9/10 7/5 0 -11/5 |
21/2 19 |
|
dj= |
|
В Табл.8 всі визначники dj невід’ємні. Це свідчить про те, що при значеннях невідомих функціонал досягає максимального значення . Задача розв’язана.