Linear Programming Output summary 14 страница

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

5 6

Глава 5. Транспортные модели

шая их как систему линейных уравнений (после присвоения какой-либо переменной произвольного значения, например и, = 0), находим значения потенциалов и, и i>_y. Вычислив значения потенциалов, далее определяем вводимую в базис перемен­ную среди всех небазисных как переменную, имеющую наибольшее положитель­ное значение величины и, + и - с_1}.

Присвоение одной из двойственных переменных произвольного значения (например, и₁ = 0) противоречит представлениям раздела 4.2.3, поскольку это присвоение показывает, что, возможно, решение двойственной задачи (определяется вычисленными значениями двойственных переменных (потенциа-лов)) не единст­венное. В действительности противоречия здесь нет, и решение упражне­ния 5.3.3.2 объясняет, — почему.

УПРАЖНЕНИЯ 5.3.3

1. Запишите двойственную задачу для транспортной модели из примера 5.3.5 (см. табл. 5.21). Вычислите оптимальное значение целевой функции двойст­венной задачи с помощью значений двойственных переменных, приведенных в табл. 5.25, и покажите, что найденное значение совпадает с оптимальным значением целевой функции транспортной задачи.

2. В транспортной модели одной из двойственных переменных присваивается произвольное значение. Это означает, что одному и тому же базисному реше­нию прямой задачи соответствует не единственный набор значений двойст­венных переменных. Это противоречит положениям теории линейного про­граммирования, где значения двойственных переменных вычисляются как произведение вектора коэффициентов целевой функции, стоящих при ба­зисных переменных, на обратную матрицу соответствующего базиса (см. ме­тод 1 из раздела 4.2.3). Покажите, что в транспортной модели обратная мат­рица всегда определяется однозначно, в то время как вектор коэффициентов целевой функции, стоящих при базисных переменных, можно определить не единственным образом. В частности, покажите, что если коэффициенты c_tj за­менить на с_ц + k для всех i и у, где k — произвольная константа, то оптималь­ные значения переменных х_ц не изменятся. Покажите, что присвоение одной двойственной переменной произвольного значения эквивалентно прибавлению к коэффициентам c_tj некой константы к.

5.4. ЗАДАЧА О НАЗНАЧЕНИЯХ

"Лучший работник для выполнения данной работы" — вот подходящее краткое описание задачи о назначениях. В этой задаче необходимо назначить работников на определенные работы; каждый работник может выполнять лю­бую работу, хотя и с различной степенью мастерства. Если на некоторую работу назначается работник именно той квалификации, которая необходима для ее выполнения, тогда стоимость выполнения работы будет ниже, чем при назна­чении на данную работу работника неподходящей квалификации. Цель задачи — найти оптимальное (минимальной стоимости) распределение работников по всем заявленным работам.

5.4. Задача о назначениях

Общая задача назначения п работников на п работ представлена в табл. 5.31. Таблица 5.31

			Работы
				п
		С11	С12
		С21	С22	С2п
Работники
	п	Сл1	Сл2	Спп

Коэффициент с_ц равен стоимости назначения работника i на работу j (i,j= 1, 2, n). То, что количество работников равно количеству работ, не является ограни­чением общности, поскольку всегда можно ввести в модель фиктивных работников или фиктивные работы.

Задача о назначениях является частным случаем транспортной задачи, в кото­рой работники соответствуют пунктам отправления, а работы — пунктам назначе­ния. В данном случае все величины спроса и предложения равны 1. Стоимость "транспортировки" рабочего i на работу равна c_tj. Задачу о назначениях можно эффективно решить точно так же, как и транспортную задачу. Вместе с тем тот факт, что все величины спроса и предложения равны 1, привел к разработке упро­щенного алгоритма решения, названного венгерским методом. Хотя этот метод не имеет никакого отношения к транспортной задаче, он, как и метод потенциалов, все равно основан на симплекс-методе.

5.4.1. Венгерский метод⁷

Для представления этого метода используем два примера. Интерпретация вен­герского метода как симплекс-метода будет рассмотрена в следующем разделе.

Пример 5.4.1

Трое детей Джоя Клини — Джон, Карен и Терри — желают подзаработать немного де­нег на школьную экскурсию в местный зоопарк. М-р Клини выбрал три вида работ, ко­торые дети выполнить могут за определенную плату: стрижка газона, уборка гаража и мойка семейного автомобиля. Чтобы избежать ненужных споров между детьми, он опросил каждого (конечно, по секрету), сколько за каждый вид работ они хотят по­лучить. Результаты опроса (в долл.) представлены в табл. 5.32.

Таблица 5.32

	Стрижка газона	Уборка гаража	Мойка машины
Джон
Карен
Терри

Классический венгерский метод, как и методы решения транспортной задачи, первона­чально разрабатывался для ручных вычислений и сегодня, в основном, представляет только исторический интерес. В настоящее время нет необходимости в таких "быстрых" ручных вычислительных алгоритмах, поскольку задачи этого класса эффективно решаются как обычные задачи ЛП с помощью мощной современной вычислительной техники.

Глава 5. Транспортные модели

Основываясь на этой информации, как распределить работы между детьми с мини­мальными (денежными) потерями для м-ра Клини?

Решим эту задачу о назначениях венгерским методом.

Этап 1. В исходной матрице стоимостей определим в каждой строке ми­нимальную стоимость и отнимем ее от других элементов строки.

Этап 2. В матрице, полученной на первом этапе, найдем в каждом столбце минимальную стоимость и отнимем ее от других элемен­тов столбца.

Этап 3. Оптимальным назначениям будут соответствовать нулевые эле­менты, полученные на предыдущем этапе.

Обозначим через p_t и q_t минимальные стоимости соответственно в строке / и столбце у, определенные на первом и втором этапах описанного выше алгоритма. Минималь­ные стоимости по строкам находятся по исходной матрице стоимостей, как показа­но в табл. 5.33.

Таблица 5.33

Стрижка газона Уборка гаража Мойка машины Минимумы по строкам

Джон				Pi =9
Карен				Р2 = 9
Терри				Рз = 8

Теперь вычтем минимальные стоимости из элементов соответствующих строк, и в результате получим следующую матрицу.

Таблица 5.34

	Стрижка газона	Уборка гаража	Мойка машины
Джон
Карен
Терри
Минимумы по столбцам	oi =0	<fe=1	<й = 0

На втором этапе алгоритма находим минимальные значения по столбцам и вычита­ем их из элементов соответствующих столбцов. В результате получим матрицу, представленную в виде табл. 5.35.

Таблица 5.35

	Стрижка газона	Уборка гаража	Мойка машины
Джон
Карен
Терри

В последней матрице подчеркнутые нулевые элементы определяют оптимальное решение: Джон будет убирать в гараже, Карен подстригать газон, а Терри достанет­ся мойка машины. Эти работы обойдутся м-ру Клини в 9 + 10 + 8 = 27 долл. Отме­тим, что эта сумма всегда равна (р, + р₂ + р₃) + (<?, + q₂ + q₃) = (9 + 9 + 8) + + (0 + 1 + 0) = 27 долл. (Доказательство этого приведено в следующем разделе.)

5.4. Задача о назначениях

Алгоритм венгерского метода в предыдущем примере завершен успешно, по­скольку нулевые элементы в конечной матрице соответствуют допустимому реше­нию (в том смысле, что каждому ребенку назначена в точности одна работа). В не­которых случаях нулевые элементы, полученные на первом и втором этапах венгерского метода, не позволяют непосредственно получить допустимое решение. То­гда необходимы дополнительные действия. Следующий пример демонстрирует это.

Пример 5.4.2

Предположим, что в примере 5.4.1 представлено четыре ребенка и четыре вида ра­бот. Таблица 5.36 соответствует матрице стоимостей для этой задачи (данные пред­ставлены в долл.).

Таблица 5.36

		Виды работ
Дети 2

Применение первого и второго этапов алгоритма к исходной матрице (при этом р_х =1, р_г = 7, р₃ = 4, р₄ = 5, <7, = 0, q₂ = 0, q₃ = 3 и q₄ = 0) приводит к следующей мат­рице (проверьте!).

Таблица 5.37

Виды работ 2 3

Дети

В последней матрице расположение нулевых элементов не позволяет назначить каж­дому ребенку одну работу. Например, если мы назначим первому ребенку работу 1, из дальнейшего рассмотрения исключается первый столбец, и тогда в строке третьего ребенка не окажется нулевых элементов. Подобные проблемы можно разрешить, добавив к описанной в примере 5.4.1 процедуре следующий этап.

Этап 2.1. Если после выполнения первого и второго этапов описанного ал­горитма не получено допустимое решение, выполните следую­щие действия.

i) В последней матрице проведите минимальное число горизон­тальных и вертикальных прямых по строкам и столбцам, чтобы вычеркнуть в матрице все нулевые элементы.

Глава 5. Транспортные модели

ii) Найдите наименьший невычеркнутый элемент и вычтите его из ос­тальных невычеркнутых элементов и прибавьте к элементам, стоя­щим на пересечении проведенных на предыдущем этапе прямых.

iii) Если новое распределение нулевых элементов не позволяет по­строить допустимое решение, повторите этап 2.1. В противном случае перейдите к третьему этапу алгоритма.

В задаче данного примера выполнение этапа 2.1 требует проведения трех прямых и приводит к табл. 5.38.

Таблица 5.38

Виды работ 3

Дети

Наименьший невычеркнутый элемент (он подчеркнут) равен 1. Этот элемент вычитаем из остальных невычеркнутых элементов и прибавляем к элементам, стоящим на пере­сечении прямых. В результате получим матрицу, представленную в виде табл. 5.39.

Таблица 5.39

			Виды работ
Дети 2

Оптимальное решение, показанное в таблице подчеркнутыми нулями, предлагает пер­вому ребенку работу 1, второму — работу 3, третьему — работу 2 и четвертому — рабо­ту 4. Соответствующее значение целевой функции равно 1 + 10+ 5+ 5 = 21 долл. Такое же значение можно получить путем суммирования значений /г, и ^ и значения элемента, наименьшего среди всех невычеркнутых: (1 + 7 + 4 + 5) + (0 + 0 + 3 + 0) + (1) = 21 долл.

УПРАЖНЕНИЯ 5.4

1. Решите задачи о назначениях, представленные в табл. 5.40.

Таблица 5.40

а)

б)

5.4. Задача о назначениях

a) Решите задачи венгерским методом.

b) С помощью программы TORA решите задачи как транспортные.

c) Запишите задачи как задачи ЛП и решите их с помощью программы TORA.

d) Решите задачи в Excel с помощью шаблона ch5SolverTransportation.xls.

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

2. Дана следующая задача распределения четырех рабочих по четырем видам работ. Различная квалификация рабочих обусловливает различную стои­мость выполнения работ. Стоимость работ (долл.) приведена в табл. 5.41. От­метим, что первый рабочий не может выполнять работу 3, а третий — работу 4. Найдите оптимальное решение.

Таблица 5.41

			Виды работ
			—
Рабочие 2
				—

3. Пусть в задаче из предыдущего упражнения можно ввести нового (пятого) рабочего, способного выполнить любой вид работ со стоимостью соответст­венно 60, 45, 30 и 80 долл. Будет ли экономически выгодным заменить одно­го из "работающих" рабочих новым?

4. Пусть в задаче из упражнения 2 необходимо ввести новый вид работы, кото­рый может выполнить любой из четырех рабочих, со стоимостью соответст­венно 20, 10, 20 и 80 долл. Будет ли новая работа более выгодной по сравне­нию с имеющимися?

5. Бизнесмен должен сделать четыре поездки туда и обратно из своего головного офиса в Далласе в филиал в Атланте (данные о поездках приведены в табл. 5.42). Билет туда и обратно, т.е. Даллас-Атланта-Даллас, стоит 400 долл. Скидка 25% предоставляется тогда, когда даты отправления и прибытия совпадают с выходными днями (суббота и воскресенье). Если в билете между датами прибы­тия в Атланту и отправления из нее не менее 21 дня, то скидка увеличивает­ся до 30%. Билет в одну сторону (в любом направлении) стоит 250 долл. Ка­кую минимальную сумму может потратить на билеты бизнесмен?

Таблица 5.42

Дата отправления из Далласа Дата возвращения в Даллас Понедельник, 3 июня Пятница, 7 июня

Понедельник, 10 июня Среда, 12 июня

Понедельник, 17 июня Пятница, 21 июня

Вторник, 25 июня Пятница, 28 июня

6. На рис. 5.8 схематически показан план обрабатывающего цеха с четырьмя ста­рыми станками, обозначенными квадратиками с номерами от 1 до 4. В цех будут

Глава 5. Транспортные модели

поставлены четыре новых станка, местоположение которых обозначено кружоч­ками с буквами а, Ь, с и d. Необходимо так разместить новые станки, чтобы ми­нимизировать суммарные перемещения обрабатываемых деталей между новыми и старыми станками. В табл. 5.43 показана интенсивность перемещения деталей между новыми и старыми станками. Детали перемещаются по сторонам пря­моугольника, противоположными вершинами которого будут старый и новый станки. Например, расстояние (в метрах) между станком 1 и станком, распо­ложенным в позиции Ь, равно 30 + 20 = 50 м.

О 10 20 30 40 50 60 70 80 Рис. 5.8. Расположение станков в задаче упражнения 6

Таблица 5.43

Старые станки

Новые станки 2 3

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

Задачу о назначении п работников на п видов работ можно представить в виде задачи линейного программирования следующим образом. Обозначим через с_(/ стоимость назначения работника i на работу у и определим

1, если работник / назначен на работу j, 0, в противном случае.

5.5. Транспортная модель с промежуточными пунктами

Получаем следующую задачу ЛП.

Минимизировать z = ^_d^c_jjx_ij

при выполнении условий

2>, = 1, i = l, 2,..., и.

5>„=1, У = 1,2,..., и, л:. = 0 или 1.

Оптимальное решение данной задачи ЛП останется неизменным, если ко всем элементам какой-либо строки или столбца матрицы стоимостей (с,.) прибавить кон­станту или вычесть ее из этих элементов. Для доказательства этого обозначим через р, и <7_у константы, вычитаемые из элементов строки i и столбца у" соответственно. Та­ким образом, стоимость с изменится и будет равна

c_ij=c_ij-p-q_j.

Теперь покажем, что при коэффициентах целевой функции с' получим те же оптимальные значения переменных jc., что и при коэффициентах с_ц.

ХХ<^с, - а - я,)**=ХХ^сл - X р. (х** ] ~ X?; f Х-^1= = XX^ca - X p> 0)^_ X^ (0=ХХ^сл ^{_ константа}-

Поскольку новая целевая функция отличается от исходной только на кон­станту, оптимальные значения переменных х должны быть одинаковы в обоих случаях. Таким образом показано, что этапы 1 и 2 венгерского метода, где р. вычитаются из элементов строки г, а ^— из элементов столбца у матрицы стоимостей, приводят к эквивалентной задаче о назначениях. Поэтому, если нулевые элементы в матрице стоимостей, созданные на этапе 1 и 2 венгерского метода, позволяют найти допустимое решение, то оно должно быть оптималь­ным, поскольку стоимости в измененной матрице стоимостей не могут быть меньше нуля.

Если созданные нулевые элементы не могут привести к допустимому решению (как в примере 5.4.2), необходимо выполнить описанный выше этап 2.1. Эта про­цедура опять основывается на симплекс-методе, и ее корректность можно обосно­вать, исходя из теории двойственности (глава 4) и теоремы о дополняющей нежест­кости (глава 7). Пока мы не будем углубляться в это.

То, что сумма Хр, ⁺Xj^j равна оптимальному значению целевой функции,

вытекает из того, что данная сумма представляет собой целевую функцию двойственной задачи. Это видно из представленного в разделе 5.3.4 выражения для целевой функции задачи, двойственной транспортной задаче. (Подробности см. в [1].)

5.5. ТРАНСПОРТНАЯ МОДЕЛЬ С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ

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

Глава 5. Транспортные модели

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

В этом разделе показано, как транспортную модель с промежуточными пунк­тами можно преобразовать (и решить) в обычную транспортную с помощью вве­дения буфера.

Пример 5.5.1

Два автомобильных завода Р1 и Р2 связаны с тремя дилерами Dl, D2 и D3, имеющи­ми два транзитных (перевалочных) центра Т1 и Т2, как показано на рис. 5.9. Заводы Р1 и Р2 производят 1000 и 1200 автомобилей. Заказы дилеров составляют соответст­венно 800, 900 и 500 автомобилей. Стоимость перевозок одного автомобиля (в сотнях долларов) показана на рис. 5.9 возле соответствующих дуг.

1000-

120О

Рис. 5.9. Транспортная модель с промежуточными пунктами

В данной модели перевозки транзитом могут осуществляться через любые пункты (в соответствии с направлением дуг на схеме), даже через некоторые пункты назначе­ния. Поэтому пункты, которым соответствуют как входящие, так и выходящие дуги на схеме рис. 5.9, назовем транзитными (пункты 71, 72, D1 и D2). Оставшиеся будут либо истинными пунктами отправления (пункты Р1 и Р2), либо истинными пункта­ми назначения (в данной схеме такой пункт только один — D3). Эту модель можно преобразовать в обычную транспортную модель с шестью пунктами отправления (PI, Р2, 71, Т2, Dl и D2) и пятью пунктами назначения (71, 72, Dl, D2 и D3). Объе­мы спроса и предложения, соответствующие этим пунктам отправления и назначе­ния, вычисляются следующим образом.

Объем предложения истинного пункта отправления = объем исходно­го предложения.

Объем предложения транзитного пункта — объем исходного предло­жения + объем буфера.

Объем спроса истинного пункта назначения = объем исходного спроса.

Объем спроса транзитного пункта = объем исходного спроса + + объем буфера.

Объем буфера должен быть таким, чтобы вместить объем всего предложения (или спроса). Обозначим через В объем буфера. Тогда

5.5. Транспортная модель с промежуточными пунктами

В — общий объем предложения (или спроса) = = 1000 + 1200 = (или = 800 + 900 + 500) = = 2200 автомобилей.

Построенная транспортная модель, эквивалентная исходной задаче, представлена в табл. 5.44. Решение этой транспортной модели, полученное с помощью программы TORA (файл ch5ToraTrarisshipEx5-5-l.txt), показано на рис. 5.10. Отметим "транзитный" эффект решения: дилер D2 получает 1400 автомобилей, из них 900 ос­тавляет себе (для удовлетворения своего спроса), а 500 отправляет дилеру D3.

Таблица 5.44

	Л
Р1			м	М	м
Р2			: м	М	м
Л					м	В
	М		М			в
D1	М	м			м	в
	М	м	м			в
	В	в	800 + В	900 + В

1000-

1200-

(D3)--500

Рис.6.10. Решение транспортной задачи с промежуточными пунктами

УПРАЖНЕНИЯ 5.5'

1. В транспортной сети, показанной на рис. 5.11, осуществляются перевозки из пунктов 1 и 2 в пункты 5 и 6 через транзитные пункты 3 и 4. Стоимость пере­возок показана на этом же рисунке.

a) Постройте транспортную модель с промежуточными пунктами и соответ­ствующую ей обычную транспортную модель.

b) Решите транспортную задачу и покажите на схеме маршруты доставки грузов из пунктов отправления в пункты назначения.

° Для решения задач этого набора упражнений используйте программы TORA, Excel (со средством Поиск решения) и LINGO.

Глава 5. Транспортные модели

10О

200-

Рис. 5.11. Схема маршрутов для упражнения 1

2. Пусть в предыдущей задаче пункты 1 и 2 связаны транспортной магистралью со стоимостью перевозки в 1 долл., а стоимость перевозки из пункта 1 в пункт 3 возросла до 5 долл. Найдите оптимальную схему перевозок.

3. На рис. 5.12 показана транспортная сеть перевозок автомобилей между тре­мя заводами (пункты 1, 2 и 3) и тремя дилерами (пункты 6, 7 и 8) через два распределительных центра (пункты 4 и 5). Стоимость перевозок (в сотнях долларов) представлена на рисунке возле соответствующих дуг.

1000­

-1100

-1000

-1200

Рис. 5.12. Схема маршрутов для упражнения 3

a) Сформулируйте задачу как транспортную задачу.

b) Предположим, распределительный центр (пункт 4) может продать 240 автомобилей самостоятельно. Найдите новое оптимальное решение.

4. Две фабрики" снабжают определенной продукцией три магазина. Объемы производства фабрик равны 200 и 300 единиц продукции, а потребности ма­газинов составляют 100, 200 и 50 единиц продукции. Исследуется возмож­ность перевозок продукции через промежуточные пункты. Основываясь на величинах стоимости перевозок (в долл.), приведенных в табл. 5.45, найдите оптимальный план перевозок.

Таблица 5.45

		Фабрики				Магазины
Фабрики				j
				!
Магазины				" г
				I
				I

5.5. Транспортная модель с промежуточными пунктами

5. На рис. 5.13 показана сеть нефтепроводов. Узлы этой сети соответствуют на­сосным и принимающим станциям. Расстояния (в милях) между станциями приведены на схеме сети. Стоимость транспортировки одного галлона нефти между двумя станциями пропорциональна длине нефтепровода, соединяю­щего эти станции. Сформулируйте транспортную задачу с промежуточными пунктами и найдите ее оптимальное решение для перекачки нефти из пунк­тов 1 и 3 в пункты 2 и 4.

50 ООО 60 ООО (галлоны)

Рис. 5.13. Сеть нефтепроводов для упражнения 5

6. Задача нахождения кратчайшего пути. Чтобы найти кратчайший путь между пунктами 1 и 7 транспортной сети, показанной на рис. 5.14, сфор­мулируйте транспортную задачу с промежуточными пунктами. Расстояния между промежуточными пунктами показаны на рисунке. (Совет. Пусть в пункте 1 есть предложение в одну единицу, а в пункте 7 — спрос такой же величины.)

Рис. 5.14. Транспортная сеть для упражнения 6