2.2. Типові задачі планування в інтегрованому виробництві та методи їх розв’язання

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

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

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

Сфера застосування моделей та методів такого роду у даний час охоплює широкий спектр функцій організаційного управління [10].

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

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

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

1) витрати виробника на виготовлення вітчизняних товарів встановленої номенклатури, враховуючи ліцензію на вивіз – ;

2) ціни на вітчизняні товари при продажу оптом за валюту у Європі – ;

3) максимально доступні розміри партій вітчизняних товарів – ;

4) фрахтові ставки при перевезенні вітчизняних товарів – ;

5) ціни на товари закордонного виробництва встановленої номенклатури при купівлі оптом за валюту у Європі – ;

6) фрахтові ставки при перевезенні іноземних товарів – ;

7) ціни на європейські товари при продажу за гривні в роздріб – ;

8) коефіцієнт перерахунку оптової ціни в роздрібну при продажу – ;

9) ставка податків на продаж – ;

10) валютний курс гривні – ;

11) коефіцієнти загальних втрат при роботі з вітчизняними товарами – ;

12) коефіцієнти загальних втрат при роботі з іноземними товарами при продажу їх оптом та в роздріб ;

13) максимальні розміри партій іноземних товарів, які можна реалізувати у рамках зазначених втрат – ;

14) сума грошових коштів, які має виробник – ;

15) сума одержаного кредиту – ;

16) процентна ставка з кредиту – ;

17) обмеження на вивезення валюти з Європи – ;

18) обмеження на вивезення валюти з України – .

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

В результаті математичний запис задачі має наступний вигляд:

за умов

– обмеження коштів на виробництво, перевезення і компенсації втрат;

– обмеження коштів на придбання іноземних товарів

– обмеження на вивезення валюти з Європи;

– обмеження на вивезення валюти з України;

– обмеження на максимальний обсяг партій вітчизняних товарів;

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

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

1) виробництво продукції утворюється на базі різних технологічних процесів;

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

3) витрати ресурсів системи, які пов’язані з кожним із технологічних процесів, визначаються трудовитратами (виміряними в людино-тижнях), а також кількістю матеріалів (в одиницях ваги), які витрачаються за встановлений час планового періоду;

4) загальні трудовитрати виробництва повинні не перевищувати , а матеріальні запаси - .

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

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

за умов

;

.

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

1) B_і – пропускна здатність і - ої групи устаткування ( );

2) A_іj – трудомісткість j - го виробу ( ), виготовленого на обладнанні і - ої групи;

3) S_j – собівартість виробів;

4) C_j – вартість виробів;

5) X_j – шукана програма випуску;

6) обмеження з пропускної здатності устаткування:

.

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

1) найменший сумарний розмір простоїв:

,

де ;

2) максимізація випуску у вартісному вираженні:

;

3) максимізація прибутку:

.

Метод розв’язання задачі. Розглянуті задачі відносяться до єдиного математичного класу задач – лінійного програмування (ЛП).

Симплекс-метод є найбільш поширеним та універсальним обчислювальним методом, який використовується для розв’язання будь-яких задач ЛП за допомогою ЕОМ. Ідея методу полягає у послідовному проходженні по базисних рішеннях опорних планів задачі доти, доки не буде одержане оптимальне рішення (іншими словами, у послідовному покращенні планів задачі за визначеним критерієм).

Розглянемо процес підготовки початкових даних і алгоритм розв’язання задачі ЛП табличним симплекс-методом.

Математична модель задачі ЛП має одну із наступних лінійних форм:

(2.1)

за умов:

; (2.2)

X_j  0, (2.3)

або

(2.4)

за умов:

(2.5)

X_j  0, . (2.6)

Перед розв’язанням задачі необхідно попередньо виконати такі процедури:

1) привести математичну модель до канонічного вигляду, тобто обмеження (2.2), (2.5) перетворити на рівняння за допомогою додаткових змінних;

2) визначити початковий прийнятний (невід’ємний) базисний розв’язок задачі (у випадку обмежень (2.5) ввести штучні змінні);

3) ввести в початкову симплекс-таблицю такі параметри, які відповідають початковому базисному розв’язку (рис.2.2):

– вагові коефіцієнти при змінних X_j в ЦФ (рядок C_j);

– змінні X_j, які входять до наявного базису;

– значення базисних змінних X_і = B_і = A₀ (стовпець A₀);

– елементи , матриці умов задачі A[m  n] (стовпці A₁, A₂, ..., A_n);

– оцінки , що відповідають стовпцям A₁, A₂, ..., A_n і визначаються за формулою:

. (2.7)

Рис. 2.2. Структура початкової симплекс-таблиці

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

Алгоритм симплекс-методу (для (2.1)) має вигляд [5]:

1. Заповнити початкову симплекс-таблицю.

2. Якщо D_j  0 для всіх , то отриманий план оптимальний.

3. Якщо є D_j < 0 і в стовпці A_j всі елементи A_іj  0, то ЦФ необмежена зверху умовами задачі і знайти оптимальний план неможливо.

4. Якщо у стовпцях A_j, що відповідають від’ємним оцінкам D_j, існує хоча б один A_іj > 0, то можливий перехід до нового, кращого плану.

5. Стовпець A_k, який необхідно ввести до базису для покращення плану, визначається за найменшим D_j < 0. Стовпець, в якому міститься ця оцінка, називається напрямним.

6. Стовпець A_r, який необхідно вивести з базису, визначається за відношенням r: , (A_іk  0). Рядок r називається напрямним. Елемент A_rk, який стоїть на перехресті напрямного рядка і стовпця, називається напрямним елементом.

7. Заповнюється нова симплекс-таблиця, яка відповідатиме новому базисному розв’язку:

при ; (2.8)

при ; ; ,

де l – номер ітерації.

Значення D_j визначається одним з двох способів:

а) як кожний елемент таблиці за виразом (2.8);

б) за формулою (2.7).

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

Особливості застосування методу:

1. Якщо за початковий базис беруть базис із вільних змінних, для яких C_і = 0, то оцінки для всіх небазисних змінних дорівнюють D_j = A_0j = -C_j, а відповідні значення .

2. При розв’язанні задачі з математичною моделлю у формі на мінімум в базис вводиться стовпець з найбільшою додатною оцінкою.

3. Відсутність стовпців з D_j < 0 (при розв’язанні задачі з математичною моделлю у формі на максимум) або з D_j > 0 (при розв’язанні задачі з математичною моделлю у формі на мінімум) є ознакою оптимальності відповідного базисного рішення.

4. Якщо є хоча б одна від’ємна (задача максимуму) або додатна (задача мінімуму) оцінка для небазисного вектора, а його стовпець містить лише від’ємні елементи, то в області прийнятних рішень ЦФ необмежена.

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

Нехай в задачі ЛП B = [B_i] – обмеження значень ресурсів, а dB = [dB_i] – прийнятні варіації цих ресурсів. Дослідимо їх вплив на зміну оптимального значення ЦФ L(X_oпт(B)) = L(B). Якщо прийняти, що B = B + dB, то нове оптимальне значення ЦФ буде рівним L(B + dB). Обчисливши приріст dL(B + dB) = L(B + dB) – L(B), знайдемо границю співвідношення:

– частинна похідна ЦФ по змінній B_i.

За теоремою подвійності одержимо:

C•X_oпт = L(X_oпт) = L_подв(Y_опт) = B•Y_опт,

де Y_опт – оптимальний розв‘язок подвійної задачі ЛП;

L_подв – ЦФ подвійної задачі.

Звідси dL(B)/dB_i = Y_i опт, що визначає максимальне значення приросту ЦФ прямої задачі при зміні і-го ресурсу B_i на 1 одиницю, а саме: чим більше Y_i опт, тим більша чутливість ЦФ прямої задачі до зміни вільних членів B_i в оптимальному розв‘язку X_опт. Якщо Y_i опт = 0, то це означає, що відповідний ресурс B_i не є суттєвим для моделі, тобто зміна його значення на 1 одиницю не призведе до зміни оптимального значення ЦФ і отриманого розв‘язку X_опт. Це обумовлює перетворення і-го обмеження прямої задачі у строгу нерівність , оскільки ресурс B_i знаходиться у надлишку на величину:

.

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

1) якщо оптимальне рішення задачі подвійності Y_i опт = 0, то відповідний ресурс прямої задачі B_i використовується частково і його значення може бути зменшене до величини ;

2) якщо оптимальне рішення задачі подвійності Y_i опт  0, то при зміні відповідного ресурсу B_i на 1 одиницю ЦФ прямої задачі одержить приріст на величину Y_{i опт}.

Слід зазначити, що знаходження значення Y_{i опт} можливе через значення D_j оцінок симплекс-таблиці оптимального розв‘язку прямої задачі, тобто Y_i опт = D_n+i.