3848093748

Rozdział 1. Zagadnienie transportowe

Rząd macierzy A warunków ograniczających zadania transportowego jest równy (m + n — 1).

Ważnym wnioskiem z twierdzenia 1.1 jest fakt, że rozwiązanie bazowe zadania transportowego składa się dokładnie z (m + n — 1) zmiennych bazowych, a zatem co najwyżej (m + n — 1) zmiennych przyjmuje w rozwiązaniu optymalnym wartości niezerowe.

Definicja 1.1

Zadanie transportowe nazywamy zbilansowanym jeżeli

m n

Y_J^ai = Y,^h3 (^L6)

i=1 3=1

czyli gdy łączne zapotrzebowanie odbiorców jest równe sumie zapasów u dostawców. W przeciwnym razie zadanie jest niezbilansowane.

Zadanie niezbilansowane można łatwo sprowadzić do postaci zbilansowanej dodając dodatkowego, fikcyjnego:

— dostawcę z zapasem a₀ = (E”=i ty - ES=i ^ai), gdy E£i ^ai < E"=i ty, przyjmując ao = 0, j = 1,..., n

lub

— odbiorcę z zapotrzebowaniem bo = (EI^i ^ai ~ Ej=i bj), gdy EI^i ^ai > Ej=i ty, przyjmując Coj = 0, i = 1,..., m.

Dostawy od dodatkowego dostawcy pozwalają zrealizować zamówienia odbiorców przekraczające możliwości dostawców. W praktyce pozyskanie dodatkowego dostawcy (zwłaszcza przy zerowych kosztach transportu) jest na ogól niemożliwe i dlatego konieczne jest zbilansowanie zadania np. przez zmniejszenie zapotrzebowań poszczególnych odbiorców. Dostawy do dodatkowego odbiorcy można potraktować jako zapasy u dostawców, które nie zostaną wykorzystane. Z punktu widzenia modelu matematycznego wprowadzenie dodatkowych dostawców lub odbiorców oznacza wprowadzenie dodatkowych zmiennych. Ponieważ formalnie możemy każde zadania transportowe sprowadzić do postaci zbilansowanej, będziemy zakładać, że zadanie (1.1)-(1.4) jest zbilansowane. Ograniczenia (1.2) przyjmują wtedy postać równości (1.7).

^2^xij ^{= a}i, i = (1.7)

3=1

Kolejną ważną własnością zadania transportowego, o której mówi twierdzenie 1.2 jest istnienie rozwiązań dopuszczalnych.

Twierdzenie 1.2

Każde zbilansowane zadanie transportowe posiada skończone rozwiązanie optymalne.

Zadanie transportowe ma jeszcze jedną ważną własność, którą sformułowano w twierdzeniu 1.3, związaną z istnieniem rozwiązań całkowitoliczbo-wych.

Twierdzenie 1.3

Jeżeli wszystkie ai oraz bj w zadaniu transportowym (1.1)-(1.4) są liczbami