p>
Розглянемо економіко-математичну модель прикріплення пунктів відправлення до пунктів призначення. Є m пунктів відправлення вантажу і обсяги відправлення по кожному пункту a 1 , a 2 , ..., a m . Відома потреба у вантажах b 1 , b 2 , ..., b n по кожному з n пунктів призначення. Задана матриця вартостей доставки по кожному варіанту c ij ,. Необхідно розрахувати оптимальний план перевезень, тобто визначити, скільки вантажу має бути відправлено з кожного i-го пункту відправлення (від постачальника) в кожен j-ий пункт призначення (до споживача) x ij з мінімальними транспортними витратами.
У загальному вигляді вихідні дані представлені в табл. 3.1. Рядки транспортної таблиці відповідають пунктам відправлення (в останній клітині кожного рядка зазначено обсяг запасу продукту a i ), а стовпці - пунктам призначення (остання клітина кожного стовпця містить значення потреби b j ). Всі клітини таблиці (крім тих, які розташовані в нижній рядку і правому стовпчику) містять інформацію про перевезенні з i-го пункту в j-й: у правому верхньому кутку знаходиться ціна перевезення одиниці продукту, а в лівому нижньому - значення обсягу перевезеного вантажу для даних пунктів.
Таблиця 3.1
Вихідні дані
В
Транспортна задача називається закритою, якщо сумарний обсяг вантажів, що відправляються дорівнює сумарному обсягу потреби в цих вантажах по пунктах призначенняВ :
p> (3.1)
Якщо такого рівності немає (потреби вище запасів або навпаки), запасу називають відкритою, тобто:
(3.2)
Для написання модель, потрібно всі умови (обмеження) і цільову функцію представити у вигляді математичних рівнянні.
Всі вантажі з i-х пунктів повинні бути відправлені, тобто:
, (3.3)
Всі j-е пункти (споживачі) повинні бути забезпечені вантажами в плановому обсязі:
, (3.4)
Сумарні обсяги відправлення повинні рівнятися сумарним обсягами призначення (3.1). Повинно виконуватися умова невід'ємності змінних:,,. Перевезення необхідно здійснити з мінімальними транспортними витратами (функція цілі):
(3.5)
Замість матриці вартостей перевезень ( c ij ) можуть задаватися матриці відстаней. У такому випадку в якості цільової функції розглядається мінімум сумарної транспортної роботи. Як видно з виразу (3.1), рівняння балансу є обов'язковою умовою вирішення транспортної задачі. Тому, коли у вихідних умовах дана відкрита завдання, то її необхідно привести до закритій формі. У разі, якщо
- потреби по пунктах призначення перевищують запаси пунктів відправлення, то вводиться фіктивний постачальник з відсутньою об'ємом відправ...
