MODEL:

TITLE: Transportation model, Example 5.3-1; SETS:

from/SI S2 S3/:supply; to/Dl D2 D3 D4/:demand; route (from, to) :cost, ship; ENDSETS

MIN=0SUM(route (I, J) .-cost (I, J) *ship(l,J)) ; !subject to; 0FOR (

to(J):0SUM(from(I):ship(I,J))=demand(J) ) ;

@FOR (

from (I) :@SUM(to (J) : ship (I, J) )=supply(I) ) ;

DATA:

supply=15 25 10; demand=5 15 15 15; cost=10 2 20 11 12 7 9 20 4 14 16 18; ENDDATA END

Рис. 5.7. Решение транспортной задачи в программе LINGO

Таблица 5.26

2. В транспортной модели (табл. 5.27) суммарный спрос превышает общий объем предложений. Пусть штрафы за необеспеченный единичный спрос составляют 5 долл. для первого пункта назначения, 3 - для второго и 2 - для третьего.

a) Используя начальное решение, полученное методом наименьшей стоимости, найдите оптимальное решение.

b) Решите задачу с помощью средства Excel Поиск решения.

c) Решите задачу с помощью программы LINGO.

Таблица 5.27

5 1 7

6 4 6 3 2 5 75 20 50

3. Пусть в транспортной модели из предыдущего упражнения штрафы не назначаются, но спрос третьего пункта назначения должен быть выполнен полностью. Найдите оптимальное решение в программах a) TORA, b) Excel, с) LINGO.

10 80 15

4. В несбалансированной транспортной модели (табл. 5.28) стоимость хранения единицы груза, не отправленного из первого, второго и третьего пунктов отправления, составляет соответственно 5, 4 и 3 долл. Найдите оптимальное решение, если из второго пункта отправления груз должен быть вывезен полностью. Для получения начального решения используйте метод Фогеля.

Таблица 5.28

1 2 1 3 4 5

2 3 3 30 20 20

5. Пусть в транспортной модели размерностью 3x3 через хц обозначено количество грузов, перевозимых из пункта отправления i в пункт назначения

а через ctj - стоимость перевозки. Объемы грузов в первом, втором и третьем пунктах отправления равны соответственно 15, 30 и 85 единиц. Спрос в первом, втором и третьем пунктах назначения составляет 20, 30 и 80 единиц соответственно. Предположим, что начальное решение, полученное методом северо-западного угла, оптимально со следующими значениями потенциалов: их = -2, и2 = 3, и3 = 5, и, = 2, v2 = 5 и v3 = 10.

a) Найдите оптимальную стоимость транспортных расходов.

b) Определите наименьшие значения ctj для всех небазисных переменных, сохраняющих оптимальность решения, полученного методом северозападного угла.

6. В табл. 5.29 показано вырожденное базисное решение некой транспортной задачи. Пусть этому решению соответствуют следующие значения потенциалов: и, = 1, и2 = -1, и, = 2, Dj = 2hds= 5. Стоимости перевозок для всех нулевых (базисных и небазисных) переменных хц представим в виде

с,. = / + ;9, -с < 0 < сю.

Таблица 5.29

10 20 20

20 40 30

a) Найдите значение целевой функции, если данное решение оптимально.

b) Укажите значения параметра 0, гарантирующие оптимальность данного решения. (Совет. Определите местоположение нулевых базисных переменных.)

7. Дана следующая задача.

т п

Минимизировать z = c,y*,y ;=i }-\

при выполнении ограничений

> >г> у = 1,2,..., и,

хц > 0, для всех i и у.

Логично предположить, что оптимальное решение обращает первое или второе множество неравенств в равенства (в зависимости от того, будет ли выполняться неравенство я,>6уили 2e, <fy). Контрпример, опровергающий это предположение, представлен в табл. 5.30.

Таблица 5.30

1 1 2 6 5 1

2 7 1

Покажите, что данное предположение приводит к оптимальному решению хи = 2, х12 = 3, х22 = 4, лг23 = 2, дающему 2 = 27 долл., которое хуже решения хи = 2, х12 = 7, лг23 = 6 с г = 15 долл.

5.3.4. Интерпретация метода потенциалов как симплекс-метода

Связь метода потенциалов с симплекс-методом основывается на соотношениях двойственности задач ЛП (раздел 4.2). Исходя из специальной структуры транспортной задачи (обратитесь к примеру 5.5.1, где показано, как транспортную задачу представить в виде стандартной задачи ЛП), двойственная ей задача будет записана в следующем виде.

Максимизировать z = а,и, + bJvj

при ограничениях

и. + у < cti для всех i и ui и v. - свободные переменные,

а - предложение (объем грузов) пункта отправления i, Ь - спрос (заявка на грузы) пункта назначения

с - стоимость перевозки единицы груза из пункта отправления i в пункт назначения

ut - двойственная переменная, соответствующая ограничению на предложение пункта отправления i,

vj - двойственная переменная, соответствующая ограничению на спрос пункта назначения /.

Из формулы 2 раздела 4.2.4 следует, что коэффициент при переменной х в выражении целевой функции должен быть равен разности между левой и правой частями соответствующего ограничения двойственной задачи, т.е. величине ut + v - су. Но как мы уже знаем, эта величина должна быть равной нулю для каждой базисной переменной. Другими словами, для этих переменных должно выполняться равенство ut + v = ctj. Имея т + п - 1 таких равенств и ре-