ожники потрібні для того, щоб знайти вільну комірку (i, j), яка при заміні базису переходить в базисну (це відповідає відшукання дозволяє стовпця в симплекс - методі).
Для визначення симплекс - множників ми вносимо на вільні місця в таблиці значення p? ij=p ij - ui - vj (коефіцієнти цільової функції, перелічені для вільних змінних). Якщо все p? ij 0, то базисне рішення оптимально. В іншому випадку ми вибираємо довільне p? ab lt; 0, найчастіше найменше. Індексом ab позначено вільний змінне х ab, яке повинне увійти в базис. Відповідну комірку транспортної таблиці ми відзначимо знаком +.
Крім комірки (a, b) транспортної таблиці, ми пометим значками - і + інші зайняті числами осередку таким чином, щоб в кожному рядку і в кожному стовпці транспортної таблиці число знаків + було дорівнює числу знаків -. Це завжди можна зробити єдиним чином, причому в кожному рядку і в кожному стовпці буде міститися максимум по одному знаку=і по одному знаку -.
Потім ми визначаємо мінімум М з усіх елементів, помічених знаком -, і вибираємо клітинку (g, d), де цей мінімум досягається.
У нашому прикладі з М=5 можна вибрати (g, d)=(2, 3); при цьому (g, d) визначає базисне змінне, яке має стати вільним, тобто базисне змінне, відповідне індексом роздільної рядка симплекс - методу.
Таблиця 9. Транспортна таблиця
20510105151515555- + 205 + 105 -
Таблиця 10. Транспортна таблиця
155-55 ++ 10100 -
Таблиця 11. Транспортна таблиця
15- 5550 + 10-10
Таблиця 12. Транспортна таблиця
5105-5 + 510 + 10 -
Таблиця 13. Транспортна таблиця
510555155
До опт=150
Перехід до нової транспортної таблиці (заміна базису) відбувається наступним чином:
а). У осередок (a, b) нової таблиці записується число М.
б). Осередок (g, d) залишається порожньою.
в). В інших осередках помічених знаками - або +, число М віднімається з стоїть у клітинці числа (-) або складається з ним (+). Результат вноситься до відповідної осередок нової таблиці.
г). Непомічені числа переносяться в нову таблицю без змін. Решта осередків нової таблиці залишаються порожніми [5].
. 5 Методика рішення задачі
. 5.1 Пропонована математична модель
АТ «ШимкентМай» і ТОВ «Шимкентскій Заводу рослинних олій»
випускають соняшникова олія і відвантажують його 5 оптовим споживачам, транспортуванням якого займається ПП «ШимОйл».
У таблиці наведено обсяги поставок виробників і обсяги споживання.
Таблиця 14. Обсяги поставок і споживання соняшникової олії
ПроізводітельОб'ём поставок «ШимкентМай» 20 тис. б. «Шимкентскій Заводу рослинних олій» 25 тис. б.ПотребітельОб'ём потребленіяОптовий магазин 17 тис. б.Оптовий магазин 28 тис. б.Оптовий магазин 310 тис. б.Оптовий магазин 49 тис. б.Оптовий магазин 511 тис. б.
Є три різних маршруту для доставки від постачальників до споживачів. Вартість транспортних витрат змінюється залежно від обраного маршруту. Визначити оптимальний маршрут транспортування масла.
1.5.2 Рішення завдання
Прийнято наступні допущення:
рахувати вартість перевезень пропорційною кількості вантажу та відстані, на яке цей вантаж перевозиться, тобто для вирішення завдання досить мінімізувати загальний обсяг плану, виражений в пляшка-кілометрах.
для вирішення завдання використовувати методи північно-західного кута і потенціалів.
Складемо математичну модель задачі.
Позначимо - кількість вантажу, перевезеного від постачальника i до споживача j.
Стають очевидними такі обмеження (тому весь вантаж повинен бути вивезений, і всі потреби задоволені повністю):
При цьому повинні бути мінімізовані цільові функції:
Маршрут 1
Маршрут 2
Маршрут 3
Рассмотрім маршрут 1.
Побудуємо опорний план для цільової функції F1 (маршрут 1) методом північно-західного кута.
Таблиця 15. Опорний план для цільової функції F 1
Постачальники Потребітелі1234578109111202 74 85 568 225 357 59 95 11
Вартість перевезень за даним планом становить:
тис. тенге
Вирішимо за...
