рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Постановка та економіко–математична модель задачі

Постановка та економіко–математична модель задачі - раздел Философия, У посібнику викладено теоретичні основи та математичний інструментарій розв’язування окремих оптимізаційних задач МП та ДО   Для Виконання Календарних Замовлень На Постачання Продукції Ф...

 

Для виконання календарних замовлень на постачання продукції фірмі потрібно визначити обсяги виробництва, враховуючи її щодобові виробничі потужності. Виготовлену впродовж робочого дня продукцію фірма може або надіслати споживачам, або залишити зберігати на власному складі до відправки споживачам, залежно від календарного плану замовлень на продукцію. У разі, якщо своєчасне виконання деякого замовлення у повному обсязі неможливе, частину продукції фірма може надіслати споживачу пізніше; але у такому разі вона несе певні збитки у зв’язку із затримкою. Потрібно знайти такий календарний план виробництва, зберігання та поставок продукції, щоб загальні витрати на виробництво та зберігання продукції, а також втрати внаслідок затримок із надсиланням продукції замовникам були якнайменшими.

 

Вихідною інформацією до задачі слугує така:

– тривалість планового періоду (в днях);

– номер окремого календарного дня планового періоду ();

– виробнича потужність фірми для -го дня планового періоду;

– очікувана собівартість виробництва одиниці продукції для -го дня планового періоду;

– розмір замовлення на продукцію фірми на -й день планового періоду.

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

1) або виробництва продукції у той же день та негайної поставки її замовнику – тоді фірма несе лише виробничі витрати;

2) або запасів виготовленої у попередні дні та не реалізованої раніше продукції – тоді на додаток до виробничих фірма несе витрати за зберігання продукції;

3) або ж виробництва та надсилання продукції замовнику із запізненням – тоді крім виробничих витрат фірма несе додаткові збитки за несвоєчасні поставки продукції.

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

 

Задачу, що розглядається, математично можна описати моделлю класичної транспортної задачі. Для цього уведемо такі невідомі:

– обсяг виробництва продукції в -й день планового періоду, призначеної для виконання замовлення, яке було сформоване на -й день ();

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

Обчислимо необхідні розрахункові величини (у транспортній задачі вони відіграють роль транспортних тарифів):

Тепер маємо можливість записати математичну модель нашої задачі:

(5.1)

Бачимо, що задача (5.1) відповідає математичній моделі класичної транспортної задачі. Умовою існування розв’язку задачі (5.1) є така:

(5.2)

– загальний попит на продукцію фірми у плановому періоді не повинен перевищувати загальні виробничі потужності фірми на весь цей період.

У разі виконання умови (5.2) задачу про оптимізацію календарного плану виробництва, зберігання та поставок продукції можна розв’язувати за методом потенціалів. Не виключено, що для використання методу потенціалів попередньо доведеться ввести фіктивного споживача. У такому разі фіктивні поставки означатимуть недовикористання фірмою виробничих потужностей у певні дні планового періоду внаслідок браку замовлень на продукцію.

 

5.2. Приклад розв’язування задачі на ПК

 

Розглянемо задачу про оптимізацію календарного плану виробництва, зберігання та поставок продукції на плановий період тривалістю 4 дні, користуючись вихідними даними з таблиці 5.1. Відомо також, що витрати на зберігання продукції на складі фірми упродовж доби дорівнюють 5 гривень, а втрати внаслідок затримки із надсиланням продукції замовникам – 10 гривень за кожний день затримки, з розрахунку на одиницю продукції.

Таблиця 5.1

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

Показник Позначення Календарні дні планового періоду
Номер доби
Виробнича потужність
Собівартість одиниці продукції
Обсяг замовлення

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

Насамперед слід переконатися у розв’язуваності задачі – перевірити виконання умови існування її розв’язку (5.2). Для цього обчислимо загальні виробничі потужності фірми у плановому періоді:

(одиниць продукції),

а також загальний попит на продукцію у цей період:

(одиниць продукції)..

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

Щоб розв’язувати поставлену задачу як транспортну, обчислимо "транспортні тарифи", які окрім питомих виробничих витрат враховують необхідні витрати на зберігання цієї продукції або втрати внаслідок затримок із її поставкою замовникам; занесемо результати у таблицю 5.2. Наприклад, якщо одиниця продукції виготовлена на третій день та одразу ж надіслана споживачу на виконання замовлення, сформованого на цей самий день, тоді фірма несе лише виробничі витрати у сумі 30 грн. Коли ж ця продукція зберігатиметься впродовж однієї доби на складі фірми та буде надіслана наступного дня (четвертий день планового періоду) на виконання замовлення на четвертий день, в додаток до виробничих витрат 30 грн. фірма нестиме ще й витрати на зберігання продукції впродовж однієї доби – 5 грн., отже сукупний "тариф" складатиме 35 грн. Навпаки, якщо виготовлена третього дня продукція надсилатиметься в рахунок виконання замовлення, сформованого на перший день планового періоду, фірма окрім виробничих витрат 30 грн. нестиме додаткові збитки за два дні затримки із виконанням замовлення, тобто загальний "тариф" становитиме: 30+2*10=50 грн., що і показано у клітинці таблиці 5.2, яка відповідає третьому дню виготовлення продукції (передостанній рядок) та першому дню, на який замовлено продукцію.

Таблиця 5.2

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

День виготовлення продукції День, на який замовлено продукцію

 

Тепер скористаємося комп’ютером. Відкриємо нову робочу книгу Excel, яку назвемо "Kalend-Pl.xls" та звернемося до її першого аркуша "Лист 1".

1. Об’єднаємо клітинки A1:D1 та внесемо туди скорочену назву задачі: “Оптимізація календарного плану”.

2. У клітинках A3:C3, які об’єднаємо, запишемо назву показника: "Тривалість планового періоду", а його значення – 4 дні – занесемо у клітинку D3.

3. Масив клітинок A5:C11 відведемо для інформаційного блоку про щодобові виробничі потужності фірми та очікувану у відповідні дні планового періоду собівартість виробництва одиниці продукції. Необхідні дані візьмемо з перших двох рядків таблиці 5.1. Для обчислення загальних виробничих потужностей фірми у клітинку B11 введемо функцію підсумовування: =СУММ(B7:B10).

4. У клітинках A13: D14 сформуємо інформаційний блок про показник витрат на зберігання одиниці продукції упродовж однієї доби (5 гривень), а у клітинках A16: D17 – інформаційний блок про показник втрат через затримку з поставкою одиниці продукції на одну добу (10 гривень).

5. У клітинках A19:F21 побудуємо інформаційний блок про календарний план замовлень продукції. Потрібні числові дані візьмемо з останнього рядка таблиці 5.1. Щоб автоматично обчислювати загальний попит на продукцію фірми, у клітинку F21 введемо функцію підсумовування: =СУММ(B21:E21).

6. Для інформації про питомі витрати на виробництво, зберігання або втрати внаслідок затримок із поставкою продукції, залежно від дня виготовлення та дня замовлення продукції, наведеної у таблиці 5.2, відведемо клітинки A23:E29; відповідну таблицю на робочому листі назвемо скорочено: "Тарифи".

7. Інформаційний блок про календарний план виробництва, зберігання та поставок продукції розташуємо в масиві клітинок A31:F38, залишаючи незадіяною лише останню клітинку цього масиву F38. У тому числі для матриці основних змінних , які показують щодобові обсяги виробництва з урахуванням календарних дат відповідних замовлень, відведемо масив B34:E37. У масиві F34:F38 введемо функції підсумовування, щоб обчислювати щодобові обсяги виробництва, у масиві B38:E38 – функції підсумовування, щоб знаходити обсяги продукції, що виготовлятиметься на рахунок кожного щоденного замовлення.

8. Нарешті, масив клітинок A40:C40 відведемо для інформаційного блоку про загальні виробничі витрати, витрати на зберігання продукції та втрати внаслідок затримок із надсиланням продукції замовникам. Для цього в клітинках A40 і B40, які об’єднаємо, впишемо назву: "Загальні витрати, гривень", а в клітинку C40, яка буде цільовою, введемо формулу:

=СУММПРОИЗВ(B26:E29; B34:E37)

9. Оберемо команду “Поиск решения” в меню “Сервис”.

10. В полі “Установить целевую ячейку” діалогового вікна “Поиск решения” вкажемо на адресу цільової клітинки: C40.

11. Перемикач вибору оптимізаційного спрямування цільової функції увімкнемо у положення “минимальному значению”.

12. У полі “Изменяя ячейки” вкажемо на адреси клітинок з основними незалежними змінними: B34:E37.

13. У поле “Ограничения” введемо обмеження задачі. Для цього натискатимемо кнопку “Добавить” та введемо обмеження щодо щодобових виробничих потужностей фірми:

$F$34:$F$37 <= $B$7:$B$10

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

$B$38:$E$38 = $B$21:$E$21

14. Введемо параметри пошуку рішення: “Линейная модель”, “Неотрицательные переменные” та дамо команду “Выполнить”.

Робочий лист файлу "Kalend-Pl.xls" з результатами розв’язування задачі про оптимізацію календарного плану виробництва, зберігання та поставок продукції наведено на рисунку 5.1. Найекономічнішому календарному плану відповідають загальні витрати у сумі 14300 грн.

  A B C D E F
Оптимізація календарного плану    
           
Тривалість планового періоду – 4 дні    
           
Вихідні виробничі показники планового періоду      
Доба Потужність Собівартість      
     
     
     
     
Разом:      
           
Витрати на зберігання одиниці продукції упродовж однієї доби – 5 грн.    
   
           
Втрати через затримку з поставкою одиниці продукції на одну добу – 10 грн.    
   
           
Календарний план замовлень
Доба Разом
Обсяг
           
"Тарифи"  
Дата виготовлення День, на який замовлено продукції  
 
 
 
 
 
           
План виробництва, зберігання та поставок продукції Виготов-лено, всього
Дата виготовлення День, на який замовлено продукції
Надіслано  
           
Загальні витрати, гривень      

 

Рис. 5.1. Робочий лист з умовами та розв’язком задачі про оптимізацію календарного плану виробництва, зберігання та поставок продукції

 

З наведених на рис. 5.1 результатів бачимо, що виробничі потужності першого дня використовуються повністю. Всі 100 одиниць виготовленої продукції надсилаються споживачам на рахунок замовлення, що існувало для першого дня. Водночас повністю виконати це замовлення (130 одиниць продукції) фірма за один день не може. Тому решту – 30 одиниць – буде виготовлено та відправлено наступного дня. Всього ж у другий день планового періоду буде виготовлено 200 одиниць продукції (тобто наявні потужності буде використано повністю), з яких 170 спрямовано на покриття замовлення, що було для другого дня. Повністю це замовлення (190 одиниць продукції) фірма виконати поки що не може, тому залишок у кількості:

190–170=20 (одиниць продукції)

буде надіслано із запізненням на одну добу.

В третій день фірмі доцільно виготовити лише 190 одиниць продукції (хоча потужності складатимуть 250 одиниць), з яких 20 надіслати в рахунок попереднього замовлення, а 170 – в рахунок замовлення на цей день. Решту 10 одиниць замовленої на третій день продукції фірмі вигідно виготовити останнього дня, разом із 140 одиницями продукції, замовленої на четвертий день, тобто виробничі потужності останнього дня буде використано повністю.

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

Таблиця 5.3

Альтернативний оптимальний календарний план виробництва, зберігання та поставок продукції (теж відповідає загальним витратам 14300 грн.)

План виробництва, зберігання та поставок продукції
День виготовлення День, на який замовлено продукцію Виготов-лено, всього
 
Надіслано  

 

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

 

5.3. Завдання для самостійного опрацювання

 

1. Знайдіть розв’язок задачі про оптимізацію календарного плану виробництва, зберігання та поставок продукції за методом потенціалів. Порівняйте з результатами обчислень на ПК.

2. Опишіть розв’язок, зазначивши в описі:

а) план виробництва, рівень використання виробничих потужностей, щодобові виробничі витрати;

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

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

3. Проаналізуйте розв’язок щодо існування альтернативних оптимальних планів. У разі існування опишіть всю множину оптимальних планів.

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

Вказівка. Спочатку внесіть потрібні зміни до економіко–математичної моделі задачі, щоб врахувати додаткові умови.

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


РОЗДІЛ 6. ОПТИМІЗАЦІЯ ПЛАНУ ПЕРЕВЕЗЕНЬ ПРОДУКЦІЇ ЗА НАЯВНОСТІ ПРОМІЖНИХ ПУНКТІВ МІЖ ПОСТАЧАЛЬНИКАМИ ТА СПОЖИВАЧАМИ (БАГАТОЕТАПНА ТРАНСПОРТНА ЗАДАЧА)

 

6.1. Загальна характеристика багатоетапних транспортних задач

6.2. Розв’язування двохетапної транспортної задачі

6.3. Розв’язування багатоетапної транспортної задачі

6.4. Завдання для самостійного опрацювання

 

6.1. Загальна характеристика багатоетапних транспортних задач

 

Класична транспортна задача, яку було опрацьовано у розділі 2, є одноетапною у тому розумінні, що в ній продукція від постачальників надходить безпосередньо до споживачів. Навпаки, в багатоетапних транспортних задачах продукція від постачальників спочатку надходить на проміжні пункті (вузли транспортної мережі, розподільчі центри, склади), де, у разі потреби, вона перевантажується або ж розвантажується та певний час зберігається. Тобто до кінцевих споживачів продукція надходить не від постачальників, а з зазначених проміжних пунктів транспортних мереж.

Розрізняють двохетапні транспортні задачі, коли перевезення продукції здійснюється у два етапи: спочатку від постачальника на проміжний пункт, далі – з цього проміжного пункту до споживача (рис. 6.1), та багатоетапні – коли на шляху від постачальника до споживача проміжних пунктів є декілька (рис. 6.2).

 

  Перший етап перевезень   Другий етап перевезень  
Постачальник   Проміжний пункт   Споживач
   

 

Рис. 6.1. Рух продукції у двохетапній транспортній задачі

 

 

  Перший етап перевезень Другий етап перевезень Третій етап перевезень  
Постачальник Перший проміжний пункт Другий проміжний пункт   Споживач
     
                     

 

Рис. 6.2. Рух продукції у багатоетапній (зараз – трьохетапній)
транспортній задачі

 

Продукція, що перевозитиметься, вважається однорідною.

Постачальників, проміжних пунктів та споживачів є декілька.

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

 

6.2. Розв’язування двохетапної транспортної задачі

 

Постановка та економіко–математична модель задачі. Позначимо кількість постачальників через , а обсяг наявної у кожного з них продукції через (). Кількість споживачів позначимо через , попит кожного споживача – через (). Припускається, що перевезення продукції від постачальників до споживачів здійснюватимуться у два етапи. Спочатку продукція від постачальників надходитиме на проміжні пункти, а вже з проміжних пунктів – до споживачів (рис. 6.3). Кількість проміжних пунктів позначимо через , а пропускну спроможність окремого -го проміжного пункту – через ().

 

  Постачальники   Проміжні пункти     Споживачі  
         
  1        
           
         
           
         
             
                       

Рис. 6.3. Транспортна мережа двохетапної транспортної задачі
(, , )

 

Витрати на перевезення одиниці продукції від -го постачальника на -й проміжний пункт позначимо через (;), а витрати на перевезення одиниці продукції з -го проміжного пункту до -го споживача – через (;). Пропускні спроможності кожного з маршрутів вважатимемо необмеженими.

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

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

(6.1)

(6.2)

(6.3)

(6.4)

(6.5)

(6.6)

Цільова функція (6.1) задачі (6.1) – (6.6) відбиває вимогу пошуку найекономічнішого плану перевезень продукції. Інші умови задачі означають, відповідно, що:

(6.2) – обсяг продукції, що вивозитиметься від кожного постачальника, не повинен перевищувати наявного у нього запасу;

(6.3) – обсяг продукції, що завозитиметься кожному споживачу, має відповідати його попиту;

(6.4) – вся продукція, що завозитиметься на кожний проміжний пункт від постачальників, має бути потім надісланою до споживачів, причому слід враховувати пропускні спроможності кожного проміжного пункту;

(6.5), (6.6) – обсяги перевезень за кожним із маршрутів мають бути невід’ємними.

Математично задача (6.1) – (6.6) є задачею лінійного програмування з неперервними невід’ємними змінними. Її можна розв’язувати симплекс–методом або ж звести до класичної одноетапної транспортної задачі та розв’язувати за методом потенціалів.

Умовами існування розв’язку задачі є такі:

1) загальний запас продукції у всіх постачальників дозволяє задовольнити сукупний попит усіх споживачів:

(6.7)

2) пропускні спроможності усіх проміжних пунктів достатні для опрацювання сукупного потоку продукції у транспортній мережі:

(6.8)

Опрацюємо методику розв’язування двохетапної транспортної задачі на комп’ютері у припущенні, що умови (6.7) – (6.8) існування розв’язку справджуються.

Вихідні дані до задачі та підготовка робочого аркушу Excel. Розглянемо задачу про оптимізацію плану перевезень пального з трьох сховищ С1, С2 і С3 через два розподільчих пункти Р1 і Р2 на чотири автозаправні станції (АЗС) А1, А2, А3 та А4. Запас пального у сховищах дорівнює, відповідно, 50, 60 і 120 тон. Через розподільчий пункт Р1 можна перевезти не більше 120 т пального, через пункт Р2 – не більше 150 т. Потреби АЗС складають відповідно, 30, 50, 70 і 80 тон. З сховищ до розподільчих пунктів пальне перевозиться десятитонними цистернами, а з розподільчих пунктів до АЗС – п’ятитонними. Витрати (у гривнях) на перевезення однієї цистерни з сховищ до розподільчих пунктів наведено у таблиці 6.1, а з розподільчих пунктів до АЗС – у таблиці 6.2.

 

Таблиця 6.1   Таблиця 6.2
Сховище Розподільчий пункт Розподільчий пункт Автозаправна станція
Р1 Р2 А1 А2 А3 А4
С1 Р1
С2 Р2
С3  

 

Потрібно за критерієм мінімізації загальних транспортних витрат визначити оптимальний план перевезень пального зі сховищ до АЗС. З’ясувати, яка частина загальних транспортних витрат припадає на перший етап перевезень (зі сховищ до розподільчих пунктів), а яка на другий (з розподільчих пунктів до АЗС)?

 

Відкриємо нову робочу книгу "Palne.xls", об'єднаємо клітинки A1:H1 та запишемо назву задачі: "Оптимізація плану перевезень пального".

Далі в клітинках A3:B7 побудуємо таблицю з інформацією про запаси пального на сховищах, у тому числі у клітинку B7 введемо формулу підсумовування (=СУММ(B4:B6)), щоб автоматично знаходити загальний запас пального на усіх трьох сховищах (230 т).

У клітинках D3:E6 побудуємо таблицю з інформацією про пропускні спроможності розподільчих пунктів, причому в клітинку E6 вставимо формулу підсумовування (=СУММ(E4:E5)) для визначення загальної пропускної спроможності усіх розподільчих пунктів (270 т).

В клітинках G3:H8 побудуємо таблицю з інформацією про потреби автозаправних станцій, у тому числі для заходження загальних потреб усіх АЗС в клітинку H8 вставимо формулу підсумовування (=СУММ(E4:E5)), результатом використання якої буде число 230 (тон пального).

Пересвідчуємося у тому, що умови (6.7) – (6.8) існування розв’язку для нашої задачі про оптимізацію плану перевезень пального справджуються.

Продовжимо підготовку робочого аркушу для подальшого пошуку цього розв'язку.

У масиві клітинок A10:C15 побудуємо таблицю з інформацією про витрати на перевезення однієї тони пального за кожним з маршрутів від сховищ до розподільчих пунктів. Для цього кожний з показників таблиці 6.1 розділимо на 10, оскільки на даному етапі перевезення здійснюватимуться 10-тонними цистернами.

У масиві клітинок E10:I14 побудуємо таблицю з інформацією про витрати на перевезення однієї тони пального за кожним з маршрутів від розподільчих пунктів до автозаправних станцій. На цих маршрутах використовуватимуться 5-тонні цистерни, тому кожний з показників таблиці 6.2 слід розділити на 5.

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

В клітинках A17:C22 побудуємо таблицю, призначену для інформації про обсяги перевезень пального за кожним з маршрутів від сховищ до розподільчих пунктів, а в клітинках E17:I21 – таблицю для інформації про обсяги перевезень пального за кожним з маршрутів від розподільчих пунктів до автозаправних станцій. Причому для основних змінних задачі про обсяги перевезень відведемо у цих таблицях масиви клітинок B20:C22 та F20:I21.

Проміжні результати про обсяги вивезеного із кожного сховища пального розміщатимемо в клітинках D20:D22; про обсяги ввезеного на кожний розподільчий пункт пального – в клітинках B23:C23, про обсяги вивезеного з кожного розподільчого пункту пального – в клітинках J20:J21, а про обсяги пального, ввезеного на кожну АЗС, – у клітинках F22:I22. Для цього у зазначені клітинки введемо потрібні формули підсумовування.

Таблицю з інформацією про транспортні витрати (на кожному з етапів перевезень та загальні) побудуємо у масиві клітинок A24:C27. Для цього занесемо формули:

у клітинку C24: =СУММПРОИЗВ(B13:C15;B20:C22)

у клітинку C25: =СУММПРОИЗВ(F13:I14;F20:I21)

у клітинку C26: =СУММ(C25:C26)

Нарешті, зробимо таблиці для допоміжної інформації про кількість цистерн, які слід буде перевезти за кожним із маршрутів: на першому етапі перевезень, з використанням 10-тонних цистерн, – у клітинках A29:C24; на другому етапі, з використанням 5-тонних цистерн, – у клітинках E29:I33. Щоб обчислити відповідні показники, слід для клітинок B32:C34 значення відповідних клітинок B20:C22 розділити на 10, а для клітинок F32:I33 – значення відповідних клітинок F20:I21 розділити на 5. Підготовку робочого аркушу закінчено.


 

 

  A B C D E F G H I J
Оптимізація плану перевезень пального    
                   
Сховище Запас   Розподільчий пункт Пропускна спроможність   АЗС Потреба    
С-1   Р-1   А-1    
С-2   Р-2   А-2    
С-3   Разом:   А-3    
Разом:         А-4    
            Разом:    
                   
Витрати на перевезення 1т пального   Витрати на перевезення 1т пального  
Сховище Розподільчий пункт   Розподільчий пункт АЗС  
Р-1 Р-2   А-1 А-2 А-3 А-4  
С-1   Р-1  
С-2   Р-2  
С-3              
                   

 

Рис. 6.4. Робочий аркуш книги "Palne.xls" з результатами розв’язування задачі
про оптимізацію плану перевезень пального (початок)

 

  A B C D E F G H I J
Обсяг перевезень пального, тон   Обсяг перевезень пального, тон  
Сховище Розподільчий пункт   Розподільчий пункт АЗС  
Р-1 Р-2 Всього А-1 А-2 А-3 А-4 Всього
С-1 50 Р-1 100
С-2 60 Р-2 130
С-3 120 Всього 30 50 70 80  
Всього 100 130              
Витрати на перевезення              
На першому етапі              
На другому етапі              
Загальні              
                   
Обсяг перевезень пального, цистерн 10т   Обсяг перевезень пального, цистерн 5т  
Сховище Розподільчий пункт   Розподільчий пункт АЗС  
Р-1 Р-2   А-1 А-2 А-3 А-4  
С-1   Р-1  
С-2   Р-2  
С-3              

 

 

Рис. 6.5. Робочий аркуш книги "Palne.xls" з результатами розв’язування задачі
про оптимізацію плану перевезень пального (закінчення)

 

 


Розв’язування задачі з використанням інструменту пошуку рішення Excel. Оберемо команду “Поиск решения” в меню “Сервис”.

У діалоговому вікні “Поиск решения” в полі “Установить целевую ячейку” вкажемо на адресу цільової клітинки: C27.

Перемикач вибору оптимізаційного спрямування цільової функції ввімкнемо у положення “минимальному значению”.

У полі “Изменяя ячейки” вкажемо на адреси клітинок з основними незалежними змінними, які відповідають обсягам перевезень пального за кожним з маршрутів: $B$20:$C$22;$F$20:$I$21.

Далі введемо обмеження задачі. Для цього, натискаючи кнопку “Добавить”, послідовно введемо обмеження:

 

1) щодо запасів пального на сховищах:

$D$20:$D$22 <= $B$4:$B$6

 

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

$B$23:$C$23 = $J$20:$J$21
$J$20:$J$21 <= $E$4:$E$5

 

3) щодо обсягів пального, яке слід завезти на кожну АЗС:

$F$22:$I$22 = $H$4:$H$7

 

Вкажемо потрібні параметри пошуку рішення: “Линейная модель” та “Неотрицательные переменные”, після чого натиснемо відповідні кнопки: "OK", “Выполнить”.

У вікні “Результаты поиска решения” увімкнемо перемикач “Сохранить найденное решение” та натиснемо ОК.

Знайдений розв’язок показано на рисунку 6.5. Оптимальному плану перевезень відповідають мінімальні загальні транспортні витрати у розмірі 2070 гривень, у тому числі на першому етапі перевезень (зі сховищ до розподільчих пунктів) – 860 гривень, а на другому етапі (з розподільчих пунктів до АЗС) – 1210 гривень.

При розв’язуванні задачі нам трошки поталанило – усі показники щодо кількості цистерн в оптимальному плані перевезень виявилися цілими. У супротивному випадку довелося б за основні змінні моделі обрати не обсяги перевезень пального в тонах, а кількості цистерн (відповідно, десятитонних або п’ятитонних) для перевезення пального за наявними маршрутами від сховищ до розподільчих пунктів і з розподільчих пунктів до автозаправних станцій, та вводити додаткові обмеження щодо цілочисловості таких змінних. Зрозуміло, що зазначені зміни викличуть також певні зміни в моделі, при оформленні робочого аркушу та у процесі налагодження інструменту пошуку рішення для розв’язування задачі.

 

6.3. Розв’язування багатоетапної транспортної задачі

 

Граф транспортної системи маршрутів. При розв’язуванні багатоетапних транспортних задач транспортну систему маршрутів зручно подати у вигляді орієнтованого графа. Такий граф містить вершини та дуги. Вершини відповідають окремим пунктам транспортної мережі: початковим, проміжним та кінцевим. У початкових пунктах розташовані постачальники продукції, у кінцевих – споживачі. Проміжні пункти є транзитними – в них продукція, у разі необхідності, може перевантажуватися та перевозитися далі. Функції транзитних можуть також виконувати й певні початкові та кінцеві пункти, якщо відповідна вершина має одночасно як вхідні так і вихідні дуги.

Усі вершини графа занумеруємо натуральними числами: 1, 2, …, . Тоді кожна наявна у графі дуга означає, що від пункту до пункту існує безпосереднє транспортне сполучення. Вважатимемо, що з вершини до вершини може бути проведена максимум одна дуга. Це означає, що коли безпосередніх транспортних сполучень від пункту до пункту є декілька, для графа потрібно обрати лише одне з них (скажімо, або найкоротше, або найекономічніше – залежно від умов задачі, яка розв’язуватиметься).

Якщо між вершинами та проведено дві дуги – дугу та дугу , – це свідчить про можливість перевезень продукції як з пункту до пункту , так і у зворотному напрямі – від пункту до пункту . Зверніть увагу, що в орієнтованому графі такі дві дуги вважаються різними.

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

На графі будуть відсутні петлі – дуги, які починаються та закінчуються в одній і тій самій вершині.

Приклад графа транспортної системи маршрутів наведено на рис. 6.6.

 

                     
                         
                     
                         
                       
                         
                     
                       
                         
                       

 

Рис. 6.6. Граф транспортної системи маршрутів

 

Цей граф має 7 вершин та 14 дуг: (1, 2), (1, 3), (2, 4), (2, 5), (3, 1), (3, 4), (3, 7), (4, 6), (4, 7), (5, 2), (5, 4), (5, 6), (6, 4), та (6, 7).

 

Постановка задачі оптимізації плану перевезень продукції на транспортній мережі. Припустимо, що деяка однорідна продукція зосереджена у сховищах, розміщених у пунктах 1, 3 і 5 (дивись рис. 6.6), у кількості, відповідно, , і одиниць. Покладемо запаси цієї продукції в інших пунктах (пункти 2, 4, 6 і 7) такими, що дорівнюють нулю:

.

Наявною продукцією потрібно забезпечити підприємства, розташовані у пунктах 6 і 7. Потреби цих пунктів дорівнюють, відповідно, і одиниць продукції. Потреби інших пунктів (пункти 1, 2, 3, 4 і 5) вважатимемо нульовими:

.

Відомі також транспортні тарифи на перевезення одиниці продукції за кожним із наявних транспортних сполучень:

 

Дуга (1, 2) (1, 3) (2, 4) (2, 5) (3, 1) (3, 4) (3, 7) (4, 6) (4, 7) (5, 2) (5, 4) (5, 6) (6, 4) (6, 7)
Тариф

 

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

Необхідна умова існування розв’язку задачі є очевидною: сукупний запас продукції у постачальників має бути достатнім для забезпечення усіх потреб споживачів:

(6.9)

Але ця умова не є достатньою – існування розв’язку залежить також від топології транспортної мережі. Тому вирішуватимемо питання про існування розв’язку одночасно з пошуком цього розв’язку на персональному комп’ютері.

Економіко–математична модель. Щоб формалізувати умови задачі про оптимізацію плану перевезень продукції на транспортній мережі, позначимо множину дуг графа транспортної системи маршрутів через .

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

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

(6.10)

Обмеження задачі відбивають наступні вимоги:

1) з кожного -го пункту можна вивезти продукції не більше, аніж у цей пункт завезено, з урахуванням наявних запасів та власного споживання :

(6.11)

2) обсяги перевезень можуть набирати лише невід’ємні значення:

для всіх (6.12)

Задача (6.10) – (6.12) є задачею лінійного програмування. Інструмент “Поиск решения” Excel дозволяє розв’язувати такі багатоетапні транспортні задачі оптимізації плану перевезень продукції, якщо кількість дуг графа транспортної системи маршрутів не перевищує 200. Це обмеження є цілком прийнятним для більшості відповідних практичних задач оптимізації.

Конкретизуємо загальну економіко–математичну модель (6.10) – (6.12) задачі оптимізації плану перевезень продукції на транспортній мережі для прикладу, наведеного у попередньому пункті та проілюстрованого рисунком 6.6:

У випадку, якщо кількість вершин графа транспортної системи маршрутів не перевищує 14, підготовку робочого аркушу Excel та налагодження інструменту “Поиск решения” можна значно спростити. Спрощення полягає у поданні плану перевезень повною квадратною матрицею , з подальшою забороною перевезень за тими маршрутами , які відсутні на графі транспортної системи. Щоб врахувати цю заборону, за зазначеними фіктивними маршрутами питомі вартості перевезень слід покласти надзвичайно великими – скажімо, обрати для них число, яке в 1000 раз перевищує максимальний з тарифів за реальними маршрутами:

, де .

Якщо розв’язок такої задачі не міститиме перевезень за фіктивними маршрутами, це свідчитиме про те, що знайдено оптимальний план перевезень на реальній транспортній мережі. Коли ж оптимальний план міститиме перевезення за фіктивними маршрутами, це засвідчує, що необхідної умови (6.9) недостатньо для існування розв’язку задачі (6.10) – (6.12) – топологія транспортної мережі відповідної задачі не дозволяє побудувати жодний з допустимих планів забезпечення споживачів необхідними обсягами продукції.

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

– Конец работы –

Эта тема принадлежит разделу:

У посібнику викладено теоретичні основи та математичний інструментарій розв’язування окремих оптимізаційних задач МП та ДО

Університет економіки та права КРОК... В Р Кігель ВИКОРИСТАННЯ Excel...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Постановка та економіко–математична модель задачі

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Якщо процедура пошуку рішення не знаходить розв’язку задачі
Можливе повідомлення Пояснення Поиск не может улучшить текущее решение. Все ограничения выполнены. Виявилося неможливим п

Або Восстановить исходные значения – для відновлення первісних значень усіх змінних, значення яких містяться у клітинках “изменяемые”.
Крім цього, у полі “Тип отчета” можна вказати на тип звіту, який буде виведено на окремий аркуш поточної робочої книги Excel. Передбачено наступні три типи звітності:

Спробуйте активізувати пакет "Поиск решения" на Вашому комп’ютері.
РОЗДІЛ 2. ОПТИМІЗАЦІЯ ПЛАНУ ПЕРЕВЕЗЕНЬ ПРОДУКЦІЇ (КЛАСИЧНА ТРАНСПОРТНА ЗАДАЧА)   2.1. Загальна постановка класичної транспортної задачі 2.2. Економіко–

Транспортні тарифи
Цегельний завод Будівельний майданчик Б1 Б2 Б3 Б4

Транспортні тарифи, гривень з розрахунку на 1 тис. цеглин
Цегельний завод Будівельний майданчик М-1 М-2 М-3 М-4 М-5 М-6

З-1 ® П-2, З-2 ® П-1, З-3 ® П-3
та проаналізуємо його на оптимальність, порівнюючи суму потенціалів з тарифами за небазисними “маршрутами”.    

З-1 ® П-3, З-2 ® П-1, З-3 ® П-2 .
Загальна вартість виконання робіт за цим планом складає 39 грошових одиниць і є найменшою у порівнянні з усіма іншими допустимими планами розподілу. /Скажімо, попередній план, знайдений за методом

Таблиця 4.2
Очікувана тривалість виконання замовлень на перевезення різними виконавцями, годин Замовлення Перевізник П-1

Таблиця 4.3
Тарифи на виконання замовлень різними перевізниками, гривень Замовлення Перевізник П-1 П-2 П-3

Таблиця 4.4
Очікувана тривалість виконання замовлень на перевезення різними виконавцями, годин Замовлення Перевізник П-1

Гривень
Звідки Куди 2 3 4 5 6 7

Таблиця 7.2
Звідки Куди 2 3 4 5 6 7

Таблиця 8.1
Вихідна інформація про автозаправні станції Номер АЗС

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги