3848093748

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

YJai = 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 a0 = (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).

71

^2xij = ai, 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



Wyszukiwarka

Podobne podstrony:
12 Rozdział 1. Zagadnienie transportowe Tablica 1.4. Wyznaczenie rozwiązania początkowego metodą VAM
14 Rozdział 1. Zagadnienie transportowe Tablica 1.6. Rozwiązanie początkowe wyznaczone metodą
16 Rozdział 1. Zagadnienie transportowe1.2.1. Przykład Firma turystyczna dysponuje czterema autobusa
18 Rozdział 1. Zagadnienie transportowe Odczytujemy rozwiązanie optymalne nadając wartość 1 zmiennym
Spis treści Rozdział 1. Zagadnienie transportowe................... 5 1.1.
6 Rozdział 1. Zagadnienie transportowe ZAPAS ZAPOTRZEBOWANIE 1.1.2. Analiza sytuacji
10967043?591407542824166174253 n Obie zmienne dualne są dodatnie. a więc - na podstawie (I3a) • oba
Rozdział 1Zagadnienie transportowe Istnieje duża grupa wyspecjalizowanych zagadnień programowania
7 1.1. Zagadnienie transportowe Ograniczenia wynikające z dostępności nawozów u poszczególnych
WYDZIAŁ TRANSPORTU I ELEKTROTECHNIKI Zapis warunków ograniczających lA-h-Ic = 0
ZAGADNIENIE TRANSPORTOWE - PRZYKŁAD AGHMetoda minimalnego elementu macierzy (klatek
A AGH □ nieujemność przewozówOPIS ZAGADNIENIA Warunki ograniczające (brak możliwości
Zadania 8.Znależć rząd macierzy sprowadzając macierz do postaci bazowej b) B = 1 1 1 1
zadanie transport Zad. 2 Rozwiązać zagadnienie transportowe: Warunek dodatkowy: odbiorca nr 2 musi b
Zasady tworzenia zadania dualneno: Zmienne decyzyjne ++ warunki ograniczające:•    W
Rozdział 1.Zagadnienia wprowadzające 1. Polityka a zadania publiczne Administracja rządowa i
1 Modelowanie zadań programowania liniowego. Zadania dotyczące zagadnienia transportowego Zadanie 1.
DSC40 W dalszych rozwa2aniach rozpatrzymy zadanie w postaci standardowej, w której wszystkie warunk
DSC41 W dalszych rozważaniach rozpatrzymy zadanie w postaci standardowej, w której wszystkie warunk

więcej podobnych podstron