На головну

Послідовне поліпшення виробничої програми

  1. I Послідовне з'єднання конденсаторів.
  2. I. Ознайомлення з підприємством. Інструктаж з охорони праці, техніки безпеки і виробничої санітарії.
  3. II. Показники ефективності виробничої діяльності підприємства
  4. II. Вимоги до результатів освоєння основної освітньої програми початкової загальної освіти
  5. II. Вимоги до результатів освоєння основної освітньої програми основної загальної освіти
  6. III. Прийоми роботи з діловодної документацією
  7. IV. Механізм реалізації Програми

Припустимо тепер, що підприємство може випускати чотири види продукції, використовуючи для цього три види ресурсів. Відома технологічна матриця А витрат будь-якого ресурсу на одиницю кожної продукції, вектор В обсягів ресурсів і вектор З питомого прибутку

 (7)

Потрібно скласти виробничу програму, що забезпечує підприємству найбільший прибуток при наявних обмежених ресурсах

Математична модель задачі:

знайти виробничу програму

(x1, x2, x3, x4)

максимізує прибуток

z = 36x1+ 14x2 + 25x3 + 50x4  (8)

при обмеженнях по ресурсах

 (9)

де за змістом завдання

x1 ? 0, x2 ? 0, x3 ? 0, x4 ? 0. (10)

Отримали завдання на умовний екстремум. Для її вирішення систему нерівностей (9) за допомогою додаткових невід'ємних невідомих х5, х6, х7 замінимо системою лінійних алгебраїчних рівнянь

 (11)

де додаткові змінні мають сенс залишків відповідних ресурсів. Серед всіх рішень системи рівнянь (11), що задовольняють умові незаперечності

х1?0, х2?0, ..., х5?0, ..., х7?0. (12)

треба знайти те рішення, при якому функція (8) прийме найбільше значення.

Скористаємося тим, що праві частини всіх рівнянь системи (11) невід'ємні, а сама система має бажаний вид - додаткові змінні є базисними. Прирівнявши до нуля вільні змінні х1, х2, х3, х4, Отримуємо базисне невід'ємне рішення

x1= 0, x2= 0, x3= 0, x4= 0, x5= 208, x6= 107, x7= 181 (13)

перші чотири компоненти якого визначають виробничу програму

x1= 0, x2= 0, x3= 0, x4= 0 (14)

по якій ми поки нічого не виробляємо.

З виразу (8) видно, що найбільш вигідно починати виробляти продукцію четвертого виду, так як прибуток на одиницю продукції тут найбільша. Чим більше випуск в цій продукції, тим більший прибуток. З'ясуємо, до яких пір наші ресурси дозволяють збільшити випуск цієї продукції. Для цього доведеться записати для системи рівнянь (11) спільне рішення

 (15)

Ми поки зберігаємо в загальному рішенні х1= х2= х3= 0 і збільшуємо тільки х4. При цьому значення базисних змінних повинні залишатися невід'ємними, що призводить до системи нерівностей

 або  т. е. 0 ? х4 ?

дамо х4 найбільше значення х4 = 181/5, яке вона може прийняти при нульових значеннях інших вільних невідомих, і підставимо його в (15). Отримуємо для системи рівнянь (11) приватна невід'ємне рішення

х1= 0, х2= 0, х3= 0, х4=  ; x5= 27; x6=  ; x7= 0 (16)

Неважко переконатися, що це рішення є новим базисним невід'ємним рішенням системи лінійних алгебраїчних рівнянь (11), для отримання якого достатньо було взяти в системі (11) невідому х4 за роздільну і перейти до нового предпочитаемому увазі цієї системи, зберігши праві частини рівнянь невід'ємними, для чого за що дозволяє рівняння ми зобов'язані прийняти третій, так як

а що дозволяє елементом буде а34= 5. Застосувавши відомі формули виключення, отримуємо для системи рівнянь (11) новий бажаний еквівалент

x1 + 2x2 + 2x3 + x5 - x7 = 27

x1 + x2 - x3 + x6 - x7 =  (17)

x1 + x2 + x3 + x4 + x7 =

Прирівнявши до нуля вільні змінні х1, х2, х3, х7, Отримуємо базисне невід'ємне рішення, що збігається з (16), причому перші чотири компоненти його визначають нову виробничу програму

х1= 0, х2= 0, х3= 0, х4=  . (18)

 Досліджуємо, чи є ця програма найкращою, т. Е. Забезпечує вона найбільший прибуток. Для цього висловимо функцію прибутку (8) через нові вільні змінні х1, х2, х3, х7.

З останнього рівняння системи (17) висловлюємо базисну змінну х4 через вільні і підставляємо в (8). отримуємо

 (19)

Бачимо, що програма (18) не є найкращою, так як прибуток буде зростати, якщо ми почнемо виробляти або першу, або другу, або третю продукцію, але найбільш швидко функція z зростає при зростанні х1. Тому приймаємо х1 в системі (17) за роздільну невідому, знаходимо що дозволяє рівняння по

 (20)

і виключаємо х1 з усіх рівнянь системи (17), крім першого рівняння. Отримаємо наступний бажаний еквівалент системи умов, який визначить для системи (11) нове базисне невід'ємне рішення і вже третю виробничу програму, для дослідження якого нам доведеться висловити функцію (19) через нові вільні змінні, видаливши звідти змінну х1, Що стала базисною. Ми бачили вище, як це робиться (видаляли х4 з (8)).

Важливо звернути увагу на те, що ці видалення можна виконати дуже просто. Уявімо співвідношення (8) у вигляді рівняння

-36х1 - 14х2 - 25х3 - 50х4 = 0 - z (21)

і припишемо його до системи (11). Виходить допоміжна система рівнянь

 (22)

Нагадаємо, що роздільну невідому в системі (11) ми вибрали х4. Цієї змінної в останньому рівнянні системи (22) відповідає найменший негативний коефіцієнт D4= -50. Потім ми знайшли дозволяє елемент а34= 5 і виключили невідому х4 з усіх рівнянь системи (11), крім третього. Далі нам довелося х4 виключати і з функції (8). Тепер це можна зробити дуже просто, якщо подивитися на систему рівнянь (22). Очевидно, досить помножити третє рівняння системи (22) на 10 і додати до четвертого; отримаємо

-6х1 - 4х2 - 5х3 - 10х4 = 1810 - z (23)

 Таким чином, ми перетворювали допоміжну систему рівнянь (22) до виду

x1 + 2x2 + 2x3 + x5 - x7 = 27

x1 + x2 - x3 + x6 - x7 =  (24)

x1 + x2 + x3 + x4 + x7 =

-6x1 - 4x2 - 5x3 + 10x7 = 1810 - z

 Перші три рівняння цієї системи представляють деякий бажаний еквівалент (17) системи рівнянь (11) і визначають базисне невід'ємне рішення (16) і виробничу програму (18), а з останнього рівняння системи (24) виходить вираз (19) функції мети через вільні змінні . Очевидно, якщо є хоча б один негативний коефіцієнт Dj при якій-небудь змінної xj в останньому рівнянні системи (24), то виробнича програма не є найкращою і можна далі продовжувати процес її поліпшення. За допомогою (19) ми з'ясували, що слід починати виробляти продукцію першого виду, т. Е. Фактично ми знайшли в останньому рівнянні системи (24) найменший негативний коефіцієнт

min (Dj<0) = min (-6, -4, -5) = -6 = D1

і вирішили перевести вільну змінну х1 в число базисних, для чого, згідно (20) Визначили дозволяє рівняння і вказали дозволяє елемент а11= 1.

З огляду на сказане вище, тепер ми будемо перетворювати не систему (17), а всю допоміжну систему (24), за формулами виключення. Ця система перетвориться до виду

 
 


x1 + 2x2 + 2x3 + x5 - x7 = 27

3x2 - x3 - x5 + x6 + x7 = 13 (25)

- x2 - x3 + x4 - x5 + x7 = 20

8x2 + 7x3 + 6x5 + 4x7 = 1972 - z

Перші три рівняння системи (25) представляють певний бажаний еквівалент системи рівнянь (11) і визначають базисне невід'ємне рішення системи умов даної задачі

x1= 27, x2= 0, x3= 0, x4= 20, x5= 0, x6= 13, x7= 0 (26)

т. е. визначають виробничу програму

x1= 27, x2= 0, x3= 0, x4= 20 (27)

і залишки ресурсів:

першого виду х5= 0

другого виду х6= 13 (28)

третього виду х7= 0

В останньому рівнянні системи (25) серед коефіцієнтів при невідомих у лівій частині рівняння немає жодного негативного. Якщо з цього рівняння виразити функцію мети z через інші невід'ємні змінні

z = 1972 - 8х2 - 7х3 - 6х5 - 4х7 (29)

то стає абсолютно очевидним (в силу того, що всі xj?0), що прибуток буде найбільшою тоді, коли

x2= 0, x3= 0, x5= 0, x7= 0 (30)

Це означає, що виробнича програма (27) є найкращою і забезпечує підприємству найбільший прибуток

zmax = 1972 (31)

Отже, організувавши спрямований перебір базисних невід'ємних розв'язків системи умов завдання, ми прийшли до оптимальної виробничої програми і вказали залишки ресурсів, а також максимальний прибуток.

Залишається зауважити, що процес вирішення зазвичай записується у вигляді деякої таблиці 1.

 Таблиця 1

       36 14 25 50 0 0 0  пояснення
 базис Н x1 x2 x3 x4 x5 x6 x7  
0 х5  4 3 4 5 1 0 0 z0 = H
х6  2 5 0 2 0 1 0
х7  3 1 2 5 0 0 1 0
  z0 -z  0 - z  -36 -14 -25 -50 0 0 0
0 х5  1 2 2 0 1 0 -1
х6  173/5  4/5 23/5 -4/5 0 0 1 -2/5  
х4  181/5  3/5 1/5 2/5 1 0 0 1/5
  z0 -z  1810-z  -6 -4 -5 0 0 0 10
х1  1 2 2 0 1 0 -1  
х6  0 3 -12/5 0 -4/5 1 2/5  все Dj ?0
х4  0 -1/5 -4/5 1 -3/5 0 4/5  
  z0 -z  1972 z  0 8 7 0 6 0 4  

де представлені розширені матриці допоміжних систем рівнянь (22) ® (24) ® (25). Ці таблиці прийнято називати симплексними.

Слід звернути увагу на економічний сенс елементів останнього рядка останньої симплексного таблиці. Наприклад, коефіцієнт D3= 7 при змінної х3 показує, що якщо зробити одну одиницю продукції третього виду (вона не входить в оптимальну виробничу програму), то прибуток зменшиться на 7 одиниць.

На закінчення зазначимо, що в розглянутому простому прикладі лінійної виробничої завдання можлива самоперевірка результату.

Скористаємося тим, що в оптимальній виробничій програмі х2= 0, х3= 0. Припустимо, що другу і третю продукції ми не мали наміру випускати з самого початку. Розглянемо задачу з двома іншими змінними, зберігши їх нумерацію. Математична модель задачі буде виглядати наступним чином:

 Студенту не важко вирішити цю задачу графічно і переконатися, що результати збігаються.

Слід при цьому звернути увагу на те, що послідовне поліпшення виробничої програми

(x1= 0, x4= 0) ® (x1= 0, x4=  ) ® (x1= 27, x4= 20)

на графіку означає рух від однієї вершини багатогранника допустимих рішень до іншої вершини по зв'язує їх стороні багатокутника (в разі трьох змінних це буде "їзда" по ребрах многогранника допустимих рішень від однієї вершини до іншої до досягнення оптимальної вершини).

§5. двоїста задача

Раніше ми розглянули конкретну лінійну виробничу задачу по випуску чотирьох видів продукції з використанням трьох видів ресурсів за заданими технологіями.

Тепер уявімо собі, що виникла нова ситуація. Знайомий підприємець П (Петров), що займається виробництвом якихось інших видів продукції, але з використанням трьох таких же видів ресурсів, які є у нас, пропонує нам "поступитися" за певними цінами всі наявні у нас ресурси і обіцяє платити у1 рублів за кожну одиницю першого ресурсу, у2 руб - другого, у3 руб - третього. Виникає питання: при яких цінах у1, у2, у3 ми можемо погодитися з пропозицією П.

величини у1, у2, у3 прийнято називати розрахунковими, або подвійними, оцінками ресурсів. Вони прямо залежать від умов, в яких діє наше предприятие.

Нагадаємо, що в нашому завданні технологічна матриця А, вектор обсягів ресурсів В і вектор питомого прибутку З мали вигляд

Для виробництва одиниці продукції першого виду ми повинні затратити, як видно з матриці А, 4 одиниці ресурсу першого виду, 2 одиниці ресурсу другого виду і 3 одиниці третього (елементи першого стовпчика матриці). У цінах у1, у2, у3 наші витрати складуть 4у1 + 2у2 +3 у3, Т. Е. Стільки заплатить підприємець П за всі ресурси, що йдуть на виробництво одиниці першої продукції. На ринку за одиницю першої продукції ми отримали б прибуток 36 руб. Отже, ми можемо погодитися з пропозицією П тільки в тому випадку, якщо він заплатить не менш

1 + 2у2 +3 у3 ? 36.

Аналогічно, у другому стовпці матриці А вказані витрати різних ресурсів на виробництво одиниці продукції другого виду. У цінах П ці витрати складуть 3у1 + 5у2 + у3, А на ринку за одиницю продукції другого виду ми отримали б прибуток 14 рублів. Тому перед підприємцем П ми ставимо умову

1 + 5у2 + у3 ? 14

і т. д. за всіма видами продукції.

Врахуємо, що за всі наявні у нас ресурси нам повинні заплатити 208у1 + 107у2 + 181у3 рублів. При поставлених нами умовах підприємець П буде шукати такі значення величин у1, у2, у3, Щоб ця сума була якомога менше. Підкреслимо, що тут мова йде не про ціни, за якими ми колись здобували ці ресурси, а про ці ціни, які істотно залежать від застосовуваних нами технологій, обсягів ресурсів і від ситуації на ринку.

 Таким чином, проблема визначення розрахункових оцінок ресурсів приводить до задачі лінійного програмування: знайти вектор двоїстих оцінок

у1, y2, y3)

мінімізує загальну оцінку всіх ресурсів

f = 208y1 + 107y2 + 181y3 (1)

за умови, що за кожним видом продукції сумарна оцінка всіх ресурсів, що витрачаються на виробництво одиниці продукції, що не менше прибутку, одержуваної від реалізації одиниці цієї продукції

 (2)
 4y1 + 2y2 + 3y3 ? 36

3y1 + 5y2 + y3 ? 14

4y1 + 2y3 ? 25

5y1 + 2y2 + 5y3 ? 50

причому оцінки ресурсів не можуть бути негативними

y1  0, y2  0, y3  0. (3)

Рішення отриманої задачі легко знайти за допомогою другої основної теореми подвійності, згідно з якою для оптимальних рішень  (х1, х2, х3, х4) і  (y1, y2, y3) Пари двоїстих задач необхідно і достатньо виконання умов

       
   
 


x 1 (4y1 + 2y2 + 3y3 - 36) = 0 y1 (4x1 + 3x2 + 4x3 + 5x4 - 208) = 0

x 2 (3y1 + 5y2 + y3 - 14) = 0 y2 (2x1 + 5x2 + 2x4 - 107) = 0

x 3 (4y1 + 2y3 - 25) = 0 y3 (3x1 + x2 + 2x3 + 5x4 - 181) = 0.

x 4(5y1 + 2y2 + 5y3 - 50) = 0

Раніше було знайдено, що в рішенні вихідної задачі х1> 0, x4> 0. Тому

 
 


4y1 + 2y2 + 3y3 - 36 = 0

5y1 + 2y2 + 5y3 - 50 = 0

Якщо ж врахувати, що другий ресурс був надлишковим і, згідно з тією ж теоремі подвійності, її двоїста оцінка дорівнює нулю

у2= 0,

то приходимо до системи рівнянь

 4y1 + 3y3 - 36 = 0

5y1 + 5y3 - 50 = 0

звідки слід

у1= 6, у3= 4.

Таким чином, отримали двоїсті оцінки ресурсів

у1= 6; у2= 0; у3= 4, (4)

причому загальна оцінка всіх ресурсів дорівнює 1972.

 Зауважимо, що рішення (4) містилося в останньому рядку останньої симплексного таблиці вихідної задачі. Важливий економічний сенс двоїстих оцінок. Наприклад, двоїста оцінка третього ресурсу у3= 4 показує, що додавання однієї одиниці третього ресурсу забезпечить приріст прибутку в 4 одиниці.

§6. Завдання про "розшивки вузьких місць виробництва"

При виконанні оптимальної виробничої програми перший і третій ресурси використовуються повністю, т. Е. Утворюють ?узкіе місця проізводства?. Будемо їх замовляти додатково. Нехай T (t1, t2, t3) - Вектор додаткових обсягів ресурсів. Так як ми будемо використовувати знайдені двоїсті оцінки ресурсів, то повинна виконуватися умова

H + Q-1T  0.

Завдання полягає в тому, щоб знайти вектор

T (t1, 0, t3),

максимізує сумарний приріст прибутку

W = 6t1 + 4t3  (1)

за умови збереження двоїстих оцінок ресурсів (і, отже, структури виробничої програми)

 (2)

припускаючи, що можна сподіватися отримати додатково не більше 1/3 обсягу ресурсу кожного виду

 (3)

причому за змістом завдання

t1  0, t3  0. (4)

 Переписавши нерівності (2) і (3) у вигляді:

 
 

 (6)
 (5)

приходимо до задачі ЛП: максимізувати (1) за умов (5), (6) і (4).

Це завдання легко вирішити графічно: див. Рис. 1. Програма ?расшівкі? має вигляд

t1=  , t2= 0, t3=

 і приріст прибутку складе 519 .

Зведення результатів наведена в таблиці

Таблиця 1

сj b x4 + i yi ti
   46 5/12
aij
   60 1/3
 xj      519 2/3
Dj        

§7. Транспортна задача лінійного програмування

Транспортна задача формулюється наступним чином. Однорідний продукт, зосереджений в m пунктах виробництва (зберігання) в кількостях а1, а2, ..., Аm одиниць, необхідно розподілити між n пунктами споживання, яким необхідно відповідно b1, b2, ..., Bn одиниць. Вартість перевезення одиниці продукту з i-го пункту відправлення в j-ий пункт призначення дорівнює зij і відома для всіх маршрутів. Необхідно скласти план перевезень, при якому запити всіх пунктів споживання були б задоволені за рахунок наявних продуктів в пунктах виробництва і загальні транспортні витрати з доставки продуктів були мінімальними.

Позначимо через хij кількість вантажу, планованого до перевезення від i-го постачальника j-му споживачеві. При наявності балансу виробництва та споживання

 (1)

математична модель транспортної задачі буде виглядати так:

знайти план перевезень

 Х = (хij), I = 1, m; j = 1, n

мінімізує загальну вартість всіх перевезень

 (2)

за умови, що з будь-якого пункту виробництва вивозиться весь продукт

 (3)

і будь-якому споживачеві доставляється необхідну кількість вантажу

 (4)

причому за змістом завдання

х11 > 0,. . . ., Xmn > 0. (5)

 Для вирішення транспортної задачі найчастіше застосовується метод потенціалів. Нехай вихідні дані завдання мають вигляд

а (а1, а2, а3) = (54; 60; 63); в (b1, b2, b3, b4) = (41; 50; 44; 30); С =

Загальний обсяг виробництва aаi = 55 + 60 + 63 = 178 більше, потрібно всім споживачам abi = 42 + 50 + 44 + 30 = 166, т. Е. Маємо відкриту модель транспортної задачі. Для перетворення її в закриту вводимо фіктивний пункт споживання з обсягом споживання 178-166 = 12 одиниць, причому тарифи на перевезення в цей пункт домовимося вважати рівними нулю, пам'ятаючи, що змінні, що додаються до лівих частинах нерівностей для перетворення їх в рівняння, входять в функцію мети з нульовими коефіцієнтами.

Перше базисне допустиме рішення легко побудувати за правилом ?северо-західного угла?.

 споживання b1 = 41 b2 = 50 b3 = 44 b4 = 30 b5 = 12  
 виробництво            
а1 = 54       p1 = 0
a2 = 60       p2 =
a3 = 63 *   p3 =
  q1 = q2 = q3 = q4 = q5 =  

Слід мати на увазі, що з будь-якої транспортної таблиці можна відновити відповідний бажаний еквівалент системи рівнянь (3), (4), а в таблиці записані лише праві частини рівнянь, причому номер клітини показує, яка невідома у відповідному рівнянні є базисної. Так як в системі (3), (4) рівно m + n - 1 лінійно незалежних рівнянь, то в будь-який транспортний таблиці повинно бути m + n - 1 зайнятих клітин.

позначимо через

m )

 вектор симплексних множників або потенціалів. тоді

Dij = mAij - зij  i = 1, m; j = 1, n

звідки слід

Dij = pi + qj - cij i = 1, m; j = 1, n (6)

Один з потенціалів можна вибрати довільно, так як в системі (3), (4) одне рівняння лінійно залежить від інших. Покладемо, що р1 = 0. Решта потенціали знаходимо з умови, що для базисних клітин  . В даному випадку отримуємо

D11 = 0, p1 + q1 - c11 = 0, 0 + q1 -1 = 0, q1 = 1

D12 = 0, p1 + q2 - c12 = 0, 0 + q2 -4 = 0, q2 = 4

D22 = 0, p2 + q2 - c22 = 0, р2 + 4-6 = 0, р2 = 2

і т. д., отримаємо: q3= 0, p3= 6, q4= 1, q5= -6.

Потім за формулою (6) обчислюємо оцінки всіх вільних клітин:

D21 = p2 + q5 - c21 = 2 + 1-3 = 0

D31 = p3 + q1 - c31 = 6 + 1-2 = 5

D32 = 5; D13 = -3; D14 = -1; D24 = -2; D15 = -6; D25 = -4.

 Знаходимо найбільшу позитивну оцінку

max (  ) = 5 =

Для знайденої вільної клітки 31 будуємо цикл перерахунку - замкнуту ламану лінію, сусідні ланки якої взаємно перпендикулярні, самі ланки рівнобіжні рядкам і стовпцям таблиці, одна з вершин перебуває в даній вільній клітці, а всі інші - в зайнятих клітинах. Це буде 31-11-12-22-23-33. Виробляємо перерозподіл поставок вздовж циклу перерахунку

     41-r  13 + r      
     37-r  23 + r    
      r    21-r      

 = 21

Здобути другу базисне допустиме рішення:

bj b1 = 41 b2 = 50 b3 = 44 b4 = 30 b5= 12  
ai            
а1 = 54   *   p1 = 0
a2 = 60       p2 = 2
a3 = 63     p3 = 1
  q1 = 1 q2 = 4 q3 = 0 q4 = 6 q5= -1  

Знаходимо нові потенціали, нові оцінки. Найбільшу позитивну оцінку матиме вільну клітинку 14. Для неї будуємо цикл перерахунку 14-11-31-34 виробляємо перерозподіл

     20-r r    
 21  21 + r  30-r

rmax = 20

і виходить третій базисне допустиме рішення. Продовжуємо процес до ті пір, поки не прийдемо до таблиці, для якої все

       
   


Dij ? 0 i = 1, m; j = 1, n

Читачеві не важко перевірити, що буде оптимальним базисне допустиме рішення


§8. Динамічне програмування.

 Розподіл капітальних вкладень

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

Знайомство з методом динамічного програмування найпростіше почати з розгляду нелінійної задачі розподілу ресурсів між підприємствами одного виробничого об'єднання або галузі. Для визначеності можна вважати, що мова йде про розподіл капітальних вкладень.

Припустимо, що вказано n пунктів, де потрібно побудувати або реконструювати підприємства однієї галузі, для чого виділено b рублів. Позначимо через fi(xi) Приріст потужності або прибутку на j-му підприємстві, якщо воно отримає xi рублів капітальних вкладень. Потрібно знайти такий розподіл (x1, x2, ..., Xn) Капітальних вкладень між підприємствами, яке максимізує сумарний приріст потужності або прибутку

z = f1(x1) + F22) + ... + Fn(xn)

при обмеженні по загальній сумі капітальних вкладень

x1 + x2 + ... + Xn = b

причому будемо вважати, що всі змінні xj приймають тільки цілі невід'ємні значення

xj = 0, або 1, або 2, або 3, ...

функції fj(xj) Ми вважаємо заданими, помітивши, що їх визначення - досить трудомістка економічне завдання.

Скористаємося методом динамічного програмування для вирішення цього завдання.

Введемо параметр стану і визначимо функцію стану. За параметр стану x приймемо кількість рублів, що виділяються кільком підприємствам, а функцію стану Fk(X) визначимо як максимальний прибуток на перших k підприємствах, якщо вони разом отримують x рублів. Параметр x може змінюватися від 0 до b. Якщо з x рублів k-е підприємство отримає xk рублів, то яким би не було це значення, решта x - xk рублів природно розподілити між підприємствами від першого до (К-1) -го так, щоб була отримана максимальна прибуток Fk-1(X - xk). Тоді прибуток k підприємств буде дорівнює fk(xk) + Fk-1(X - xk). Треба вибрати таке значення xk між 0 і x, щоб ця сума була максимальною, і ми приходимо до рекурентному співвідношенню

Fk(X) = max {fk(xk) + Fk-1(x-xk)}

0 ? xk ? x

для k = 2, 3, 4, ..., n. Якщо ж k = 1, то

F1(X) = f1(X)

Розглянемо конкретний приклад. Нехай виробниче об'єднання складається з чотирьох підприємств (n = 4). Загальна сума капітальних вкладень дорівнює 700 тис. Рублів (b = 700), які виділяються підприємствам суми кратні 100 тис. Рублів. Значення функцій fj(xj) Наведені в таблиці 1, де, наприклад, число 88 означає, що якщо третє підприємство отримає 600 тис. Руб. капітальних вкладень, то приріст прибутку на цьому підприємстві складе 88 тис. руб.

 Таблиця I

Перш за все заповнюємо табл. 2. Значення f2(x2) Складаємо зі значеннями F1(X - x2) = F1(X- x2) І на кожній північно-східній діагоналі знаходимо найбільше число, яке відзначаємо зірочкою і вказуємо відповідне значення  . Заповнюємо таблицю 3.

Продовжуючи процес, табулируем функції F3(X),  (X) і т. Д. У табл. 6 заповнюємо тільки одну діагональ для значення x = 700. Найбільше число на цій діагоналі:

Zmax = 155 тис. Руб.,

причому четвертому підприємству має бути виділено

х*4 = 4 (700) = 300 тис. Руб.

На частку інших трьох підприємств залишається 400 тис. Руб. З табл. 5 видно, що третьому підприємству має бути виділено

x*3 = 3 (700-x*4) = 3 (400) = 200 тис. Руб.

Продовжуючи зворотний процес, знаходимо

x *2 = 2 (700 - x *4 - X *3) = 2 (200) = 100 тис. Руб.

На частку першого підприємства залишається

x *1 = 700 - x *4 - X *3 - X *2 = 100 тис. Руб.

Таким чином, найкращим є наступний розподіл капітальних вкладень по підприємствах:

x *1 = 100; x *2 = 100; x *3 = 200; x *4 = 300.

Воно забезпечує виробничому об'єднанню найбільший воможность приріст прибутку 155 тис. Руб.

Студенту рекомендується перевірити виконання рівності

f1(X *1) + F2(X *2) + F3(X *3) + F4(X *4) = Z max

Таблиця 2

   x - x2  0 100 200 300 400 500 600 700
 x2 F1(X - x2) f2(x2)  0 20 34 46 53 55 60 60
0  0 20 * 34 46 53 55 60 60
 18 38 * 52 * 64 71 73 78
 29 49 63 75 82 84
 45 65 * 79 91 98
 62 82 * 96 108
 78 98 * 112 *
 90 110
 98.
 Таблиця 3

x  0 100 200 300 400 500 600 700
F2(X)  0 20 38 52 65 82 98 112
'  (X)  0 0 100 100 300 400 500 500

 Таблиця 4

   x - x3  0 100 200 300 400 500 600 700
 x3 F2(X - x3) f3(x3)  0 20 38 52 65 82 98 112
0  0 20 38 52 65 82 98 112
 25 * 45 * 63 * 77 90 107 123
 41 61 79 * 93 106 123
 52 72 94 * 112 126
 74 94 * 112 * 126 *
 82 102 120
 88 106
 90.

Таблиця 5

x  0 100 200 300 400 500 600 700
F3(X)  0 25 45 63 79 94 112 126
 (X)  0 100 100 100 200 400 400 400

Таблиця 6

 x - x4  0 100 200 300 400 500 600 700
 x4 F3(X - x4) f4(x4)  0 25 45 63 79 94 112 126
 155 *
 125.

§9. Динамічна задача управління виробництвом

 і запасами

Підприємство виробляє партіями деякі вироби. Припустимо, що воно отримало замовлення на n місяців. Розміри замовлень значно змінюються від місяця до місяця. Тому іноді краще виконувати однією партією замовлення декількох місяців, а потім зберігати вироби, поки вони не будуть потрібні, ніж виконувати замовлення в той саме місяць, коли це замовлення повинен бути відправлений. Необхідно скласти план виробництва на зазначені n місяців з урахуванням витрат на виробництво і зберігання виробів. позначимо:

xj - Число виробів, вироблених в j -й місяць;

yj - Величина запасу на початок j го місяця (це число не містить виробів, вироблених в j -му місяці);

dj - Число виробів, які повинні бути відвантажені в j -й місяць;

fj (xj, yj + 1) - Витрати на зберігання і виробництво виробів в j -му місяці.

Будемо вважати, що величини запасів до початку першого місяця y1 і до кінця останнього yn + 1 задані.

Завдання полягає в тому, щоб знайти план виробництва

(x1, x2, ..., Xn) (1)

компоненти якого задовольняють умовам матеріального балансу

xj + yj - dj = yj + 1 j = 1, n (2)

і мінімізують сумарні витрати за весь планований період

 (3)

причому за змістом завдання

 
 


xj ? 0, yj ? 0, j = 1, n (4)

Перш ніж приступити до вирішення поставленого завдання, зауважимо, що для будь-якого місяця j величина yj + 1 запасу до кінця місяця повинна задовольняти обмеженням

0 ? yj + 1 ? dj + 1 + dj + 2 + ... + Dn (5)

т. е. обсяг виробленої продукції xj на етапі j може бути настільки великий, що запас yj + 1 задовольняє попит на всіх наступних етапах, але не

має сенсу мати yj + 1 більше сумарного попиту на всіх наступних етапах. Крім того, з співвідношень (2) і (4) безпосередньо випливає, що змінна xj повинна задовольняти обмеженням

0 ? xj ? dj + yj + 1 (6)

Слід також зауважити, що змінні xj, yj можуть приймати тільки цілі невід'ємні значення, т. е. ми отримали завдання цілочисельного нелінійного програмування.

Будемо вирішувати задачу (1) - (6) методом динамічного програмування.

Введемо параметр стану і складемо функцію стану.

 За параметр стану x приймемо готівковий запас в кінці k -го місяця

x = yk + 1 (7)

а функцію стану Fk(X) визначимо як мінімальні витрати за перші k місяців при виконанні умови (5)

 (8)

де мінімум береться по невід'ємним цілим значенням x1, ..., Xk, Що задовольняє умовам

xj + yj - dj = yj + 1 j = 1, k-1 (9)

xk + yk - dk = X (10)

Враховуючи що

 (11)

і величина запасу yk до кінця (k-1) періоду, як видно з рівняння (10), дорівнює

yk = X + dk - xk (12)

приходимо до рекурентному співвідношенню

 (13)

де мінімум береться по єдиної змінної xk, Яка, згідно з (6) може змінюватися в межах

0 ? xk ? dk + X (14)

приймаючи цілі значення, причому верхня межа залежить від значень параметра стану, що змінюється в межах

0 ? x ? dk + 1 + dk + 2 + ... + Dn (15)

а індекс k може приймати значення

k = 2, 3, 4, ..., n (16)

Якщо k = 1, то

F1(X = y2) = Min f1(x1, X) (17)

x1

де

x1 = X + d1 - y1 (18)

0 ? x ? d2 + d3 + ... + Dn (19)

 т. е. на початковому етапі при фіксованому рівні y1 вихідного запасу кожному значенню параметра x відповідає тільки одне значення змінної x1, Що трохи зменшує обсяг обчислень.

Застосувавши відому обчислювальну процедуру динамічного програмування, на останньому кроці (при k = n) знаходимо значення останньої компоненти xn* Оптимального рішення, а інші компоненти визначаємо як

 (20)

Розглянемо більш докладно функції витрат fj(xj, yj + 1) І рекурентні співвідношення. нехай

jj(xj) = Axj2 + bxj + c

jj (xj) - Витрати на виробництво (закупівлю) xj одиниць продукції на етапі j;

hj - Витрати на зберігання одиниці запасу, що переходить з етапу j в етап j + 1.

Тоді витрати на виробництво і зберігання на етапі j рівні

fj(xj, yj + 1) = Jj(xj) + Hj yj + 1 = axj2 + bxj + C + hj yj + 1. (21)

Виведені раніше рекурентні співвідношення динамічного програмування для вирішення задачі управління виробництвом і запасами в нашому випадку приймають вид:

 (22)

де

k = 2, 3, ..., n (23)

0 ? yk + 1 ? dk + 1 + dk + 1 + ... + Dn (24)

0 ? xk ? dk + yk + 1 (25)

yk = yk + 1 + dk - xk (26)

 (27)
 Якщо ж k = 1, то

 (30)
 (29)
 (28)

Залишається зауважити, що корисно позначити вираз у фігурних дужках через

Wk(xk, yk + 1) = Axj2 + bxj + C + hkyk + 1 + Fk-1(yk) (31)

і записати рекурентне співвідношення (22) у вигляді

Fk(X = yk + 1) = Min Wk(xk, yk + 1) (32)

xk

 де мінімум береться по цілочисельний змінної xk, Що задовольняє умові (25).

Приклад. Розглянемо трьохетапну систему управління запасами з дискретною продукцією і динамічним детермінованим попитом.

Нехай попит (заявки) споживачів на нашу продукцію складають: на перший етап d1= 3 одиниці, на другий - d2= 2, на третій - d3= 4 одиниці. До початку першого етапу на складі є тільки 2 одиниці продукції, т. Е. Початковий рівень запасу дорівнює y1= 2. Витрати на зберігання одиниці продукції на різних етапах різні і складають відповідно h1= 1, h2= 3, h3= 2. Витрати на виробництво xj одиниць продукції на j-му етапі визначаються функцією

jj(xj) = Xj2 + 5xj + 2  (33)

т. е. а = 1; b = 5; з = 2. Потрібно вказати, скільки одиниць продукції на окремих етапах слід проводити, щоб заявки споживачів були задоволені, а наші загальні витрати на виробництво і зберігання за всі три етапи були найменшими.

Вихідні дані завдання можна коротко записати одним рядком:

d1 d2 d3 a b c h1 h2 h3 y1

1 2 4 1 5 2 1 3 2 2

Скориставшись рекурентних співвідношеннями, послідовно обчислюємо

F1 (X = y2), F2 (X = y3), ..., Fk (X = yk + 1), ... І відповідно знаходимо 1 (X = y2), 2 (X = y3 ), ..., ' k (X = yk + 1), ...

Покладемо k = 1. Згідно (27) маємо

 (34)

Врахуємо, що згідно (28) параметр стану x = у2 може приймати цілі значення на відрізку

0 у2 d2 + d3

0 y2  2 + 4

т. е.

у2 = 0, 1, 2, 3, 4, 5, 6.

При цьому, взагалі кажучи, кожному значенню параметра стану повинна відповідати певна область зміни змінної x1, Яка характеризується умовою (29)

0 х1  3 + у2

Однак, на першому етапі обсяг виробництва х1 не може бути менше одиниці, так як попит d1 = 3, а вихідний запас у1 = 2. Більш того, з балансового рівняння

х1 + у1 - d1 = у2

безпосередньо випливає, що обсяг виробництва пов'язаний зі значенням параметра стану x = у2 співвідношенням

x1 = y2 + d1 - y1 = y2 + 3 - 2 = y2 +1 (35)

В цьому і полягає особливість першого етапу. Якщо заданий рівень запасу на початок першого етапу, то кожному значенню у2 відповідає єдине значення х1 і тому

F1(X = y2) = W1 (x1, y2)

 надаючи у2 різні цілі значення від 0 до 6 і з огляду на (35), знаходимо

Тематика контрольних робіт з дисципліни | Але що ж назвати ризиком всієї гри?
© um.co.ua - учбові матеріали та реферати