Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Применяя метод потенциалов, можно говорить не о знаке алгебраических сумм тарифов, а о сравнении косвенных тарифов с истинными. Требование неотрицательности алгебраических сумм тарифов заменяется условием, что косвенные тарифы не превосхо­дят истинных.

Следует иметь в виду, что потенциалы (так же как и циклы) для каждого нового базисного плана определяются заново.

Выше рассматривалась закрытая модель транспортной задачи, с правильным балансом, когда выполняется условие (1.3). В случае выполнения (1.4) (открытая модель) баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок (транспортная задача с избытком запасов):

а_i > b_j ( где i=1,...,m ; j=1,...,n );

2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок):

а_i < b_j ( где i=1,...,m ; j=1,...,n );

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов.

Сведем её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения В₁, B₂, ... , B_n, введём ещё один, фиктивный, пункт назначения B_n+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

b_n+1 = а_i - b_j ( где i=1,...,m ; j=1,...,n ) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b_n+1 будем считать равной нулю. Введением фиктивного пункта назначения B _n+1 с его заявкой b _n+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок.

Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления A_m+1 с запасом a_m+1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.

1. Задача, двойственная к транспортной.

Построим задачу, двойственную к транспортной. С этой целью вспомним, что каждому пункту отправления и назначения отвечает определенное огра­ничение

(6.1)

В то же время каждому ограничению из (6.1) сопоставляется определенная неизвестная в двойствен­ной задаче. Тем самым устанавливается соответствие между всеми пунктами и и всеми неиз­вестными двойственной задачи.

Обозначим неизвестную в двойственной задаче, отвечаю­щую пункту отправления , через , а пункту назначения – через .

Каждому неизвестному в транспортной задаче соответ­ствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное входит ровно в два ограничения системы (6.1): одно из них отвечает пункту , а другое – пункту . В обоих этих уравнениях коэффициент при равен 1. Поэтому соответствующее ограничение в двой­ственной задаче имеет вид

(6.2)

.

Правая часть неравенства (6.2) равна , потому что именно с этим коэффициентом неизвестная входит в миними­зируемую формулу (2.4).

Оптимизируемая форма двойственной задачи имеет вид

(6.3)

Таким образом, задача двойственная к транспортной форму­лируется следующим образом. При ограничениях (6.2) макси­мизировать формулу (6.3). Подчеркнем, что знак значений неиз­вестных и может быть произвольным.

Предположим, что нам известно некоторое допустимое базисное решение транспортной задачи, в котором все базис­ные неизвестные строго положительны. Это решение оптимально лишь в том случае, когда соответствующая ей система оказывается совместной. Эта система возникает из системы (6.2), если в ней все неравенства, отвечающие базисным неизвестным заменить точными равенствами.

В итоге приходим к соотношению:

(6.4)

(для всех свободных неизвестных )

Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточ­ным условием оптимальности.

7.Пример решения транспортной задачи.

В городе N имеется 4 склада А_i, на которых хранится ткань (в рулонах) и 5 магазинов B_j, занимающихся продажей ткани. Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из А_i в B_j. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок.

В данном случае Σa_i=225 >Σb_j=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного магазина B₆ с потребностью b₅=225-220=5 и стоимостью перевозок с_i6=0.Имеем таблицу:

Математическая модель: обозначим x_ij – количество товара, перевозимого из А_i в B_j. Тогда

x₁₁ x₁₂ x₁₃ x₁₄ x₁₅ x₁₆

x₂₁ x₂₂ x₂₃ x₂₄ x₂₅ x₂₆

X = x₃₁ x₃₂ x₃₃ x₃₄ x₃₅ x₃₆ - матрица перевозок.

x₄₁ x₄₂ x₄₃ x₄₄ x₄₅ x₄₆

min(x₁₁+2x₁₂+3x₁₃+2,5x₁₄+3,5x₁₅+0,4x₂₁+3x₂₂+x₂₃+2x₂₄+3x₂₅+0,7x₃₁+x₃₂+x₃₃+0,8x₃₄+1,5x₃₅++1,2x₄₁+2x₄₂+2x₄₃+1,5x₄₄+2,5x₄₅) (1)

x ₁₁+x₁₂+x₁₃+x₁₄+x₁₅+x₁₆=50

x₂₁+x₂₂+x₂₃+x₂₄+x₂₅+x₂₆=20

x₃₁+x₃₂+x₃₃+x₃₄+x₃₅+x₃₆=75

x₄₁+x₄₂+x₄₃+x₄₄+x₄₅+x₄₆=80

x₁₁+x₂₁+x₃₁+x₄₁=40 (2)

x₁₂+x₂₂+x₃₂+x₄₂=50

x₁₃+x₂₃+x₃₃+x₄₃=15

x₁₄+x₂₄+x₃₄+x₄₄=75

x₁₅+x₂₅+x₃₅+x₄₅=40

x₁₆+x₂₆+x₃₆+x₄₆=5

x_ij≥0 (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3)

Двойственная ЗЛП:

max(50u₁+20u₂+75u₃+80u₄+40v₁+50v₂+15v₃+75v₄+40v₅+5v₆) (1*)

u₂+v₁≤0,4

u₂+v₂≤3

u₂+v₃≤1

u₂+v₄≤2

u₂+v₅≤3

u₂+v₆≤0

u₃+v₁≤0,7

u₃+v₂≤1

u₃+v₃≤1

u₃+v₄≤0,8

u₃+v₅≤1,5

u₃+v₆≤0

u₄+v₁≤1,2

u₄+v₂≤2

u₄+v₃≤2

u₄+v₄≤1,5

u₄+v₅≤2,5

u₄+v₆≤0

u ₁+v₁≤1

u₁+v₂≤2

u₁+v₃≤3 (2*)

u₁+v₄≤2,5

u₁+v₅≤3,5

u₁+v₆≤0

u_i,v_j – произвольные (i=1,2,3,4 ; j=1,2,3,4,5,6 ) (3*)

Будем искать первоначальный план по методу наименьшей стоимости:

1) x₂₁=20 и 2-ую строку исключаем.2) x₃₁=20 и 1-ый столбец исключаем.

3) x₃₄=55 и 3-ю строку исключаем.4) x₄₄=20 и 4-ый столбец исключаем.

5) x₁₂=50 и 1-ю строку и 2-ой столбец исключаем и x₃₂=0. 6) x₄₃=150 и 3-ий столбец исключаем.7) x₄₅=40 и 5-ый столбец исключаем.x₄₆=5.Составим таблицу. Здесь и далее в нижнем правом углу записываем значение перевозки.

Стоимость 1-ого плана:

D₁=2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.

Характеристики

Список файлов курсовой работы