Розробка автоматизованого робочого місця управління замовленнями у малому бізнесі (ПП "Сігма") (стр. 6 из 13)
– ОЗУ не менше 1 Гб;
– вінчестер не менше 100 Гб.
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.8 – Вид транспортної задачі
 |  | … |  | |||||
| x11 | x12 | … | x1n |  | ||||
 |  | … |  | |||||
| x21 | x22 | … | x2n |  | ||||
| … | … | … | … | |||||
 |  | … |  | |||||
 |  | … |  |  | ||||
 |  | … |  |  | ||||
Вартості перевезень одиниці продукції задані в лівих верхніх кутках відповідних кліток і задані в гривнях. Об'єми виробництва і величини попиту представлені в кількостях виробів.
Кількість рядків таблиці дорівнює числу виробників, а кількість стовпців - числу споживачів. Кожна клітина цієї таблиці відповідає певній парі виробник i - споживач j. Кожному маршруту i, j відповідають вартість
перевезення одиниці продукції і об'єм перевезень (кількість продукції) 
.У даній задачі умова балансу виконується, тому вводити фіктивні пункти немає необхідності..
Розв'язання ЗЛП симплекс-методом починається з деякого допустимого базисного рішення (ДБР). У методі потенціалів використовуються наступні способи знаходження початкового ДБР:
– метод північно-західного кута;
– метод найменшої вартості;
– метод Фогеля.
1.4.3.2 Метод північно-західного кута
Схема алгоритму така.
Надаємо змінній
(розташованій у північно-західному кутку транспортної таблиці) максимальне значення, що допускається обмеженнями на попит і обсяг виробництва: 
Якщо
, то виробник 1 повністю використав свої можливості і далі його можна не враховувати, а потреба 1-го споживача тепер буде рівна: 
;Якщо
, то 1-й споживач повністю задовольнив свою потребу в продукції і його можна далі не враховувати, а виробник 1 тепер має в своєму розпорядженні лише 
одиниці продукції;Якщо
, то із розгляду можна виключити і споживача і виробника. В цьому випадку виключається ("вибуває з|із| гри") тільки один з них: або виробник, або споживач, а споживачеві (виробникові), що залишився, приписується нульовий попит (об'єм виробництва).Після встановлення об'єму перевезень по маршруту (1,1) ми маємо справу з новою задачею, у якій сумарне число виробників і споживачів на 1 менше, ніж у вихідній задачі. У північно-західну клітину таблиці нової задачі, отриманої уявним викреслюванням першого стовпця або першого рядка старої таблиці, знову поміщаємо максимально можливий об'єм перевезень (він може опинитися і нульовим). Продовжуючи цей процес, прийдемо до рішення задачі, оскільки
1.4.3.3 Метод найменшої вартості
Метод північно-західного кута не обов'язково дає "добре" початкове рішення для транспортної задачі. Розглянемо метод найменшої вартості, що забезпечує отримання початкового рішення шляхом вибору "дешевих" маршрутів.
Схема алгоритму така.
Вибирається змінна, якій відповідає найменша вартість у всій таблиці, і їй надається, як можно більше значення. (Якщо таких змінних декілька, то береться будь-яка з них.). Викреслюється відповідний стовпець або рядок (оскільки дане обмеження задачі виконане). Якщо обмеження по стовпцю і рядку виконуються одночасно, то, як і в методі північно-західного кута, викреслюється або стовпець, або рядок. Обчислюється нове значення попиту або об'єму виробництва для невикресленого рядка або стовпця.