Транспортна задача. Математична постановка задачі

Загальна постановка транспортної задачі полягає у визначенні оптимального плану перевезень деякого однорідного товару із M — пунктів відправлення (tz11) в N — пунктів призначення (tz-2). При цьому в якості критерію оптимальності беруть мінімальну вартість на перевезення всього товару обо мінімальний час його доставки.

Розглянемо транспортну задачу в якості критерію оптимальності якої взято мінімальну вартість перевезення. Позначимо через tz-3 — тарифи на перевезення одиниці товару з i-го пункту відправлення в j-й пункт призначення. Через tz-4 — запаси товару в i-му пункиі відправлення; tz-5 — потреби в товарі у j-му пункті призначення. Через tz-6 — кількістьі товару, який потрібно перевезти з i-го пункту відправлення в j-й пункт призначення. Тоді математична постановка задачі полягає у визначенні мінімального значення функції:

tz-7

при умовах:

tz-8

Оскільки змінні tz-61 — задовільняють систему лінійних рівнянь (2) і (3) і умову (4), то ми можемо забезпечити доставку необхідної кількості товару в кожний із пунктів призначення.

Означення 1: будь-який невід'ємний розв'язок системи лінійних рівнянь (2) і (3), який записується у вигляді матриці tz-9 — називається планом транспортної задачі.

Означення 2: план tz-10, при якому функція (1) приймає своє мінімальне значення називається оптимальним планом транспортної задачі.

Початкові дані транспортної задачі записуються у вигляді таблиці:

tz-11

Очевидно, що загальна кількість товару поставщиків дорівнює tz-12;

Загальні потреби в товарі у пункті призначення рівні tz-13.

Якщо загальна потреба в товарі у пунктах призначення рівна запасам товару у пунктах відправлення, тобто   tz-14,то   модель    такої транспортної задачі називається    закритою.   Якщо   ж

вказана умова не виконується, то задача називається відкритою.

Теорема 1: Для того, щоб транспортна задача мала розв'язок, необхідно і достатньо, щоб запаси товару в пунктах відправлення дорівнювали потребам в товарі у пунктах призначення, тобто щоб виконувалась умова (5).

У випадку коли запаси більші від потреб, тобто tz-15, вводиться фіктивний (n+1)-й пункт призначення з потребами tz-16. І tz-17.

Аналогічно, при tz-18 вводиться фіктивний (m+1)-й пуект відправлення з запасами товару tz-19 і тарифи рівні нулю (tz-20).

Число змінних tz-21 в транспортній задачі з M пунктами відправлення і N пунктами призначення дорівнює M*N, а число рівнянь M+N.

Опорний план транспорної задачі може мати не більше (n+m-1) відмінних від нуля невідомих. Якщо в опорному плані число відмінних від нуля компонент рівна точно (n+m-1), то план називається невиродженим, а якщо менше, то виродженим. Для визначення опорного плану існує декілька методів, серед яких виділяють метод північно-західного кута та метод мінімального елемента.

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар