Рішення з математичного забезпечення

1.4 Рішення з математичного забезпечення

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

–   скільки замовлень може доставити один транспорт;

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

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

–   встановити такі об'єми перевезень до кожного споживача, щоб сумарні витрати на перевезення були мінімальними;

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

Вирішити ці задачі можна за допомогою рішення транспортних задач. Розглянемо докладніше такі задачі, - що вони є, і як їх розв'язувати.

1.4.1 Змістовна постановка транспортні задачі

Є m пунктів виробництва однорідної або взаємозамінної продукції. Кожний з пунктів виробництва позначимо через,  де i= 1...,m. Через  позначатимемо обсяг продукції, вироблюваної в пункті . І нехай є n пунктів споживання (призначення) даної продукції, кожний з яких позначатимемо, де j=1...,n, а через  позначатимемо|значити| об'єм|обсяг| споживання|вжиток| (попиту) продукції в пункті . Вартість перевезення одиниці продукції від i-го виробника до j-го споживача складає (i=1...,m, j=1...,n). Передбачається, що транспортні витрати на перевезення між будь-якою парою пунктів пропорційні об'єму продукту, що перевозиться.

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

1.4.2 Формальна модель транспортної задачі

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

Z з| (1) є сумарними транспортними витратами.

Задача (1) - (4) є задачею лінійного програмування і називається транспортною задачею лінійного програмування (ТЗЛП). До моделі вигляду (1) -(4) може привести завдання, за своїм змістом ніяк не пов'язана з транспортом і плануванням перевезень. У таких випадках говорять, що дана задача може бути сформульована в термінах транспортнї задачі.

1.4.3 Метод потенціалів

Один з методів рішення транспортних задач є метод потенціалів. Метод потенціалів - один з найчастіше використовуваних методів рішення ТЗЛП. Цей метод являється реалізацією модифікованого симплекс-метода в умовах транспортної задачі.

1.4.3.1 Схема алгоритму

Схема алгоритму методу потенціалів така:

–   знайти початкове допустиме розв'язування;.

–   виділити з числа небазисних змінних що вводяться в базис. Якщо всі небазисні змінні задовольняють умові оптимальності (симплекс - методу), закінчити обчислення|; інакше перейти до наступного пункту.

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

Далі транспортну задача задаватимемо таблицею:

Таблица 1.8 – Вид транспортної задачі

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

Кількість рядків таблиці дорівнює числу виробників, а кількість стовпців - числу споживачів. Кожна клітина цієї таблиці відповідає певній парі виробник i - споживач j. Кожному маршруту i, j відповідають вартість  перевезення одиниці продукції і об'єм перевезень (кількість продукції) .

У даній задачі умова балансу виконується, тому вводити фіктивні пункти немає необхідності..

Розв'язання ЗЛП симплекс-методом починається з деякого допустимого базисного рішення (ДБР). У методі потенціалів використовуються наступні способи знаходження початкового ДБР:

–   метод північно-західного кута;

–   метод найменшої вартості;

–   метод Фогеля.