Vj *- объём потребления в пункте j.«Чистый» объём производства Qj и потребления Vj выражаются через Qj* и Vj* следующим образом: Qj = Qj* - min (Qj*, Vj*); Vj = Vj* - min (Vj*, Vj*). 1) Xs ≥ 0 (s = 1, …, r); 2) ∑sj Xs - ∑si Xs = | Qi | (s = 1, …, r); По каждому i –му пункту, отправляющему данный груз, разность между суммой пустот на всех выходах из него и суммой пустот на всех подходах к нему равна ресурсам груза, подлежащим отправлению из пункта i. Транспортная задача в сетевой форме впервые была поставлена советскими экономистами в 1929 – 30 гг., но точной математической формулировки она тогда ещё не получила.
Условия допустимости плана: 1) Xs ≥ 0 (перевозки не отрицательны); 2) ∑I ≠ j Xij - Xjj = Vj (общее количество направляемого в пункт j груза минус объём транзитного груза равно «чистому» потреблению); 3) ∑k ≠ j Xjk - Xjj = Qj (общее количество вывезенного из j груза минус объём транзитного груза равно «чистому» производству). R Допустимый план является оптимальным, если ∑ s = i Cs Xs - минимальна (т.е. суммарные затраты минимальны). § 2. Критерий оптимальности плана Для оптимальности допустимого плана необходимо и достаточно, чтобы существовали оценочные числа (потенциалы) а1, а2, …, а n ,удовлетворяющие условиям: а) аjs – аis = Cs (s = 1, …, r) – для Хs > 0, т.е. для участков, где существует перевозка; б) аjs – аis ≤ Cs - для Хs = 0, т.е. для участков, где перевозка не осуществляется (разность потенциалов не превосходит затрат по перемещению единицы груза на данном участке). Любая транспортная задача в сетевой постановке может быть преобразована в матричную. Однако при большом количестве m и n получается очень громоздкая матрица. Практически транспортные задачи чаще решаются в сетевой постановке.
|
