Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

тематичне формулювання

Работа добавлена на сайт samzan.ru: 2016-03-30


ЗАДАЧА ДРОБОВО-ЛІНІЙНОГО ПРОГРАМУВАННЯ.

1. Приклад економічної задачі та її математичне формулювання.

Нехай виробництво випускає однорідний продукт і володіє  технологічними способами (технологіями).

При роботі за цими технологіями за одиницю часу підприємство отримує продукту відповідно 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)

(коли , то знак можна віднести до чисельника).


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

Розглянемо на площині 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, знаходимо необхідну вершину многогранника поворотом прямої навколо початку координат.


При цьому можливі такі випадки:

  1.  

x2

Fmin

Fmax

x1

Многокутник  обмежений (Рис.2), максимум і мінімум є (стрілки на малюнку показують напрямок повороту прямої для збільшення F).

Рис.2

  1.  

Fmin

Fmax

x2

x1

Область необмежена, але максимум і мінімум є (Рис.3).

Рис.3

  1.  
    Область необмежена, і один із екстремумів не досягається (Рис.4).

Fmin

Fmax

x2

x1

Рис.4

  1.  

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. Симплек-метод у дробово-лінійному програмуванні.

В задачі дробово-лійнійного програмування обмеження лінійні і екстремум функціоналу досягається у вершині многогранника розв’язків.

Ця подібність із задачею лінійного програмування дозволяє розв’язувати задачі дробово-лінійного програмування звичайним симплекс-методом зі зміненим критерієм оптимальності.

РОЗГЛЯНЕМО ЗАДАЧУ.

Знайти максимум функціоналу:

  (3.1)

при обмеженнях

  (3.2)

   (3.3)

  (3.4)


РОЗВ’ЯЗУВАННЯ.

  1.  Складаємо початкову симплекс-таблицю (Табл.1).

При чому, для 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

  1.  
    План записаний в Табл. 1 не може бути опорним, так як
    F2 = 0, отже серед bі є від’ємні обов’язково.

Кроками МЖВ відшукуємо опорний план, перетворюючи коефіцієнти стрічок .

Нехай в результаті 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)

  1.  Щоб не відірватися від многогранника розв’язків, симплексне відношення повинно бути і найменшим із всіх можливих

Звідки слідує, що , так як по умові допустимості плану . Отже, завжди.

  1.  
    Q
    (i) завжди > 0, то Q(k)Q(k+1) завжди > 0, тому знак   F(k+1)  F(k) залежить від знаку ds. Коли ds > 0, то      F(k+1)  F(k) < 0. Звідки F(k+1) < F(k) або F(k) > F(k+1).

Іншими словами, коли за розв’язуючий стовпчик взяти стовпчик з
ds > 0, то після кроку МЖВ функціонал зменшується, а при виборі розв’язуючого стовпчика з ds < 0, F(k) > F(k+1) – функціонал збільшується.

При ds = 0, F(k+1)=F(k) функціонал не змінюється.

Визначник ds служить критерієм для вибору brs.


Алгоритм відшукання оптимального плану.

  1.  Після знаходження опорного плану обчислюються значення визначників:

 ,

значення яких заносяться в додатковий рядок таблиці.

В стовпчику вільних членів в цьому рядку записуємо значення функціоналу, рівне відношенню 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

  1.  
    При розв’язуванні задачі на
    максимум функціоналу за розв’язуючий стовпчик вибираємо той, в якому dj  < 0. Коли таких стовпчиків декілька, то за розв’язуючий стовпчик краще брати той, в якому dj найбільший по абсолютній величині.
  2.  Розв’язуючи елемент в стовпчику шукається по найменшому симплексному відношенню.
  3.  Із знайденим brs робимо один крок МЖВ при цьому коефіціенти стрічок F1 і F2 перетворюються за загальним правилом, а останній рядок не перетворюється і не записується.
  4.  Далі для кожного стовпчика обчислюємо визначники dj, а для плану - значення функціоналу F(k+1). Якщо серед dj є хоча б один від’ємний, то робимо новий крок МЖВ і т. д.
  5.  Оптимальний розв’язок буде досягнуто, коли після чергового кроку всі визначники dj стануть невід’ємними.
  6.  При розв’язуванні задачі на мінімум, за розв’язуючий приймається стовпчик з dj > 0. Критерієм оптимальності служить недодатність dj.


ПРИКЛАД.

Знайти максимум та мінімум функціоналу:

При виконанні обмежень:

 

 


РОЗВ’ЯЗАННЯ.

Складаємо початкову жорданову таблицю, заповнюючи коефіцієнтами функціоналу для чисельника та знаменника окремо два рядки 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


4

-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 невід’ємні. Це свідчить про те, що при значеннях невідомих функціонал досягає максимального значення . Задача розв’язана.




1. этика мораль нравственность.html
2. машиностроителями выполнена большая работа по совершенствованию производства машин самого различного назн
3. повтори меня участник называя имя выходит в круг своеобразной походкой либо делает какоенибудь смешное
4. тема Бюджетний дефіцит надлишок видатків державного бюджету над надходженнями до нього; звичайно фінанс
5. Острозька академія повне найменування вищого навчального заклад
6. тема государства- основные понятия принципы построения
7. Право собственности в Российской Федерации
8.  Общие положения1
9. темам за первый семестр около 7 тем
10. Ставропольский государственный аграрный университет ЭКОНОМИКА ОРГАНИЗАЦИИ мет
11. ЛАБОРАТОРНА РОБОТА 8 Виконав Ст
12. Тема- Однорідні члени речення Мета уроку- Розширити та поглибити знання учнів про однорідні члени речення с
13. реферат дисертації на здобуття наукового ступеня кандидата педагогічних наук Київ
14. Китай-город.html
15. Задание 1 Составить договор 365 от 17 октября между ОАО Мельничный комбинат исполнитель в лице директо
16. Искусство Древнего Египта Среднее царство
17. Стаття 1 Міжурядова організація Параграф 1
18. тема 12 Етапи формування поняття хімічна реакція Глава 2
19. коммуникация был введен в научный оборот в начале XX в.
20. КОНСПЕКТ ЛЕКЦИЙ по дисциплине