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

6. Спрос на специализированные малые двигатели в следующие пять кварталов составляет 200, 150, 300, 250 и 400 единиц. Мощность производства двига­телей в тот же период времени оценивается в 180, 230, 430, 300 и 300 еди­ниц. Невыполнение заказов не допускается, при необходимости можно орга­низовать сверхурочные работы для выпуска дополнительной продукции. Стоимость единицы продукции в каждый из следующих пяти кварталов со­ставляет 100, 96, 116, 102 и 106 долл. соответственно. Стоимость дополни­тельно произведенной продукции увеличивается на 50% по сравнению со "стандартной" стоимостью в соответствующий период. Если двигатели, про­изведенные в одном квартале, реализуются в последующих, за хранение од­ного двигателя в течение квартала необходимо заплатить 4 долл. Сформули­руйте транспортную задачу. С помощью программы TORA определите оптимальный план производства двигателей.

7. Периодически проводится профилактика самолетных двигателей с заменой важной детали А. В следующие 6 месяцев будут выполнены регламентные рабо­ты (с разбивкой по месяцам) на 200,180, 300,198, 230 и 290 двигателях. Все рег­ламентные работы, запланированные на месяц, проводятся в течение первых двух дней месяца, когда отработанная деталь заменяется А на новую или отре­монтированную. Снятую деталь можно отремонтировать в местной мастерской, и она будет готова к началу следующего месяца, или отправить в центральные мас­терские, откуда она вернется через 3 месяца (считая месяц, в котором выполнены

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

профилактические работы). Стоимость ремонта одной детали А в местной мас­терской составляет 120 долл., а в центральной — только 35 долл. Если отремон­тированная деталь будет использована в последующие месяцы, стоимость ее хра­нения составит 1,50 долл. в месяц. Новые детали можно купить по цене 200 долл. В первом месяце с возрастанием цены на 5% каждые 2 месяца. Представьте опи­санную ситуацию в виде транспортной модели и с помощью программы TORA найдите ее оптимальное решение.

8. Управление национальными парками получило четыре заявки от подрядчи­ков на лесозаготовки в трех сосновых лесных массивах Арканзаса. Эти мас­сивы имеют площадь 10 000, 20 000 и 30 000 акров. Каждый подрядчик мо­жет получить для разработки не более половины всех отводимых для лесозаготовки площадей. Предлагаемые подрядчиками цены за разрешение на лесозаготовки (долл.) показаны в табл. 5.15.

Таблица 5.15

		Лесной массив
Подрядчик 2	—
		—

a) В описанной ситуации необходимо максимизировать общую прибыль, получаемую управлением национальными парками. Покажите, как эту проблему можно представить в виде транспортной задачи.

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

5.3. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

В данном разделе* будет детально описан алгоритм решения транспортной зада­чи. Этот алгоритм повторяет основные шаги симплекс-метода (глава 3). Однако для представления данных, вместо обычных симплекс-таблиц, используются транс­портные таблицы со специальной структурой.

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

Алгоритм решения транспортной задачи будет проиллюстрирован на следую­щем примере.

5.3. Решение транспортной задачи

Пример 5.3.1

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

В данной задаче требуется определить структуру перевозок между элеваторами и мельницами с минимальной стоимостью. Для этого необходимо вычислить объе­мы перевозок х_ц между;-м элеватором иу'-й мельницей.

Таблица 5.16

Мельницы

12 3 4 Предложение

	Х11		Х12		Х13		Х,4
Элеваторы 2
	Х21		Х22		Х23		Х24
	Х31		Х32		хзз		Х34

Спрос 5 15 15 15

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

Шаг 1. Определяем начальное базисное допустимое решение, затем пере­ходим к выполнению второго этапа.

Шаг 2. На основании условия оптимальности симплекс-метода среди всех небазисных переменных определяем вводимую в базис. Если все небазисные переменные удовлетворяют условию оптималь­ности, вычисления заканчиваются; в противном случае перехо­дим к третьему этапу.

ШагЗ. С помощью условия допустимости симплекс-метода среди теку­щих базисных переменных определяем исключаемую. Затем нахо­дим новое базисное решение. Возвращаемся ко второму этапу.

Рассмотрим каждый описанный этап в отдельности. 5.3.1. Определение начального решения

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

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

(сумма предложений равна сумме спроса), одно из этих равенств должно быть из­быточным. Таким образом, транспортная модель имеет т + п - 1 независимых ог­раничений, отсюда следует, что начальное базисное решение состоит из т + п - 1 базисных переменных. Например, начальное решение в примере 5.3.1 содержит 3 + 4-1 = 6 базисных переменных.

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

1. Метод северо-западного угла.

2. Метод наименьшей стоимости.

3. Метод Фогеля.

Различие этих методов заключается в "качестве" начального решения, т.е. "удаленности" начального решения от оптимального. В общем случае метод Фоге­ля дает наилучшее решение, а метод северо-западного угла — наихудшее. Однако метод северо-западного угла требует меньшего объема вычислений.

Метод северо-западного угла. Выполнение начинается с верхней левой ячейки (северо-западного угла) транспортной таблицы, т.е. с переменной х_п.

Шаг 1. Переменной х_п присваивается максимальное значение, допускае­мое ограничениями на спрос и предложение.

Шаг 2. Вычеркивается строка (или столбец) с полностью реализованным предложением (с удовлетворенным спросом). Это означает, что в вычеркнутой строке (столбце) мы не будем присваивать значения остальным переменным (кроме переменной, определенной на пер­вом этапе). Если одновременно удовлетворяются спрос и предло­жение, вычеркивается только строка или только столбец.

Шаг 3. Если не вычеркнута только одна строка или только один столбец, процесс останавливается. В противном случае переходим к ячейке справа, если вычеркнут столбец, или к нижележащей ячейке, если вычеркнута строка. Затем возвращаемся к первому этапу.

Пример 5.3.2

Если применить описанную процедуру к задаче из примера 5.3.1, получим началь­ное базисное решение, представленное в табл. 5.17. В этой таблице стрелками пока­зана последовательность определения базисных переменных.

Получено следующее начальное базисное решение: х„ = 5,х₁₂=10, х,₂ = 5, х._а — 15, х₂₄ = 5, х_м=10.

Соответствующая суммарная стоимость перевозок равна z = 5xl0+10x2 + 5x7+15x9 + 5x20+10xl8 = 520 ^долл-

5.3. Решение транспортной задачи 209 Таблица 5.17

1 2 3 4 Предложение

10 5.....|	-1.0
	: 7 Y 5.....■	-15.....>	- 5
			: 18 Y

Спрос 5 15 15 15

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

Пример 5.3.3

Применим метод наименьшей стоимости к задаче из примера 5.3.1.

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

2. Следующей ячейкой с наименьшей стоимостью в незачеркнутой части табли­цы будет (3, 1). Присвоим переменной х₃₁ значение 5 и вычеркнем первый столбец. Ограничение по предложению, соответствующее третьей строке, ста­нет равным 10 - 5 = 5.

3. Продолжая процедуру, последовательно присваиваем переменной х₂₃ значение 15, переменной х_и — значение 0; далее находим х₃₄ = 5 их₂₄ = 10 (проверьте!).

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

Этот метод в русской математической литературе часто называют методом минималь­ного элемента. — Прим. ред.

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

.г₁₂ = 15,х₁₄ = 0,.r₂₃ = 15,x₂₄ = 10, ^А'з1 ⁼ •>> л"₃₄ ⁼ 5.

Соответствующее значение целевой функции равно

z=15x2 + 0xll + 15x9 + 10x 20 + 5x4 + 5x 18 = 475 долл. Отсюда следует, что полученное методом наименьшей стоимости начальное ре­шение лучше, чем начальное решение, представленное методом северо-западного угла (сравните данное значение целевой функции с аналогичным значением из примера 5.3.2).

Таблица 5.18

1 2 3 4 Предложение

			, о.
	/12		/9 г 15	10 4	.20
		.--''14		! 1	Л8

Спрос 5 15 15 15

Метод Фогеля. Данный метод является вариацией метода наименьшей стоимо­сти и в общем случае находит лучшее начальное решение. Алгоритм этого метода состоит из следующих шагов.

Шаг 1. Для^каждой строки (столбца), которой соответствует строго поло­жительное предложение (спрос), вычисляется штраф путем вычи­тания наименьшей стоимости из следующей по величине стоимо­сти в данной строке (столбце).

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

5.3. Решение транспортной задачи

ШагЗ.

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

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

в) Если всем невычеркнутым строкам и столбцам соответствуют нулевые объемы предложения и спроса, методом наименьшей стоимости находятся нулевые базисные переменные, и вычис­ления заканчиваются.

г) Во всех остальных случаях необходимо перейти к п. 1.

Пример 5.3.4

Применим метод Фогеля к задаче из примера 5.3.1. В табл. 5.19 показан первый набор вычисленных штрафов.

Поскольку третья строка имеет наибольший штраф (10) и в этой строке наимень­шая стоимость содержится в ячейке (3, 1), присваиваем переменной х₃₁ значение 5. В этом случае полностью выполняется ограничение первого столбца, его вычерки­ваем. Новый набор пересчитанных штрафов показан в табл. 5.20.

Теперь первая строка имеет наибольший штраф 9. Поэтому мы присваиваем значе­ние 15 переменной х₁₂, которой соответствует минимальная стоимость в первой строке. В этом случае одновременно выполняются ограничения и для первой стро­ки, и для второго столбца. Вычеркнем второй столбец, положив объем предложе­ний, соответствующий первой строке, равным нулю.

Таблица 5.19

									Штрафы для строк
									10-2 = 8
									9-7 = 2
									14-4 = 10
Штрафы для столбцов	10-4	= 6	7-2 = 5	16-9	= 7	18-11	= 7

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

Таблица 5.20

1 2 3 4 Штрафы для строк

\							11-2 = 9
							9-7 = 2
							16-14 = 2

0 15 15 15

Штрафы для столбцов — 5 7 7

Продолжая этот процесс, находим, что на следующем шаге вторая строка будет иметь наибольший штраф (20 -9 = 11). Поэтому переменной х₂₃ присваиваем зна­чение 15. В результате будет вычеркнут третий столбец, во второй строке останется нереализованным предложение объемом в 10 единиц. Остается невычеркнутым только четвертый столбец с положительным неудовлетворенным спросом объемом в 15 единиц. Применяя метод наименьшей стоимости к этому столбцу, последова­тельно получаем л₁₄ = 0, jc₃₄ = 5 и л\,₄ = 10 (проверьте!). Соответствующее значение целевой функции равно

z = 15 х2 + 0х 11 + 15x9 + 10 х 20 + 5x4 + 5x 18 = 475 долл.

В данном случае значение целевой функции такое же, как и при методе наимень­шей стоимости. Но обычно метод Фогеля дает наилучшее начальное решение для транспортной задачи.

УПРАЖНЕНИЕ 5.3.1

?*

1. Найдите начальные решения методами северо-западного угла, наименьшей стоимости и Фогеля для следующих транспортных задач.

	а)				Ь)				с)

5.3.2. Итерационный алгоритм решения транспортной задачи

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

5.3. Решение транспортной задачи

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

Шаг 2. С помощью симплексного условия допустимости определяется исключаемая из базиса переменная. Происходит изменение базиса и возврат к первому этапу.

При изменении базиса в данном случае не используются вычисления, выпол­няемые при реализации симплекс-метода, — специальная структура транспортной таблицы позволяет значительно упростить вычисления.

Пример 5.3.5

Решим транспортную задачу из примера 5.3.1, используя начальное решение (табл. 5.21), полученное методом северо-западного угла в примере 5.3.2.

Таблица 5.21

12 3 4 Предложение

Спрос 5 15 15 15

Определение вводимой переменной среди текущих небазисных (т.е. среди тех пе­ременных, которые не входят в начальное базисное решение) основано на вычисле­нии коэффициентов z-строки, соответствующих небазисным переменным, с использованием метода потенциалов (который, как будет показано в разделе 5.4, основан на соотношениях двойственности задачи ЛП).

В методе потенциалов каждой строке i и каждому столбцу j транспортной таблицы ставятся в соответствие числа (потенциалы) u_t и v_y. Для каждой базисной перемен­ной дг, потенциалы u_t и v_y (как показано в разделе 5.4) удовлетворяют уравнению

В рассматриваемой задаче имеем 7 неизвестных переменных (потенциалов) и 6 уравне­ний, соответствующих шести базисным переменным. Чтобы найти значения по­тенциалов из этой системы уравнений, нужно присвоить одному из них произволь­ное значение (обычно полагают и, = 0) и затем последовательно вычислять значения остальных потенциалов.

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

Базисные переменные	Уравнения относительно потенциалов	Решение
хи	и: + vi = 10	ui = 0 -> vi = 10
	щ + v2 = 2	i/i = 0 -> i/2 = 2
*22	t/2 + f2 = 7	l/2 = 2-^t/2 = 5
*23	1/2+1/3 = 9	1/2 = 5 -> 1/3 = 4
*24	u2 + Va = 20	1/2 = 5 -> l/4 = 1 5
*34	1/3+1/4 = 18	i/4 = 15 -> i/3 = 3

Итак, имеем

Wj = 0, u₂ = 5, w₃ - 3,

v, = 10, v₂ = 2, v₃ = 4, v₄= 15.

Далее, используя найденные значения потенциалов, для каждой небазисной пере­менной вычисляются величины u_l + v_t - с,. Результаты вычисления этих величин приведены в следующей таблице.

Небазисные переменные

Значения и, + i/y - с,у

Х13 Х14 *21 *31 Х32

Щ + 1/з - с₁₃ = 0 + 4 - 20 = -16 Ul + 1/4 - С14 = 0 + 15- 11 = 4 и₂ + 1/1 - с₂1 = 5 + 10- 12 = 3 и₃ + 1/1 - с₃1 = 3 + 10 -4 = 9 и₃ + 1/2 - с₃₂ = 3 + 2 - 14 = -9 и₃ + 1/₃ - Сзз = 3 + 4 - 16 = -9

Вычисленные значения совместно с нулевыми значениями для базисных перемен­ных (поскольку u_t + v - c_tj = 0 для любой базисной переменной x_tj) фактически яв­ляются коэффициентами z-строки симплекс-таблицы.

Базис

*12

Х13

*14

Х21

Х22

Х23

*24

Х31

Х32

*зз

хм

z

-16

-9

-9

Поскольку в транспортной задаче ведется поиск минимума стоимости перевозок, вводимой в базис будет переменная, имеющая наибольший положительный коэф­фициент в z-строке. В данном случае вводимой переменной будет jc₃₁.

Описанные вычисления обычно выполняются непосредственно в транспортной таблице, как показано в табл. 5.22. В этом случае нет необходимости в явном ви­де выписывать уравнения для потенциалов. Вычисления в транспортной таблице начинаются с присвоения потенциалу и_х нулевого значения: и,= 0. Затем вычис­ляются v-потенциалы для всех столбцов, имеющих базисные переменные в пер­вой строке. Далее на основании уравнения для потенциалов, соответствующего переменной jc₂₂, определяется величина потенциала и₂. Зная значение потенциала и₂, вычисляем потенциалы v₃ и v₄, что позволяет найти потенциал и₃. Поскольку все потенциалы определены, далее вычисляются величины u_t + v_s - c_tj для каждой небазисной переменной x_:j. Эти величины показаны в табл. 5.22 в левом нижнем углу ячеек транспортной таблицы.

5.3. Решение транспортной задачи Таблица 5.22

V! = 10

1/2 = 2

1/з = 4

i/4 = 15 Предложение

и: = 0

и₂ = 5

из = 3 Спрос

-16

Определив вводимую в базис переменную х₃₁, далее следует найти исключаемую из базиса переменную. Напомним, если какая-либо переменная вводится в базис, одна из текущих базисных переменных должна стать небазисной (и равной нулю), чтобы количество базисных переменных оставалось постоянным (в данном примере коли­чество базисных переменных равняется 3 + 4-1 = 6).

Исключаемая из базиса переменная определяется следующим образом. Выбрав в качестве вводимой переменную х₃₁, мы хотим, чтобы перевозки по маршруту, со­ответствующему этой переменной, уменьшили общую стоимость перевозок. Какой объем груза можно перевезти по этому маршруту? Обозначим через 0 количество груза, перевозимого по маршруту (3, 1) (т.е. х₃₁ = 0). Максимально возможное зна­чение 9 определяем из следующих условий.

1. Должны выполняться ограничения на спрос и предложение.

2. Ни по какому маршруту не должны выполняться перевозки с отрицательным объемом грузов.

Эти условия позволяют найти значение 0 и определить исключаемую переменную. Сначала построим замкнутый цикл, который начинается и заканчивается в ячей­ке, соответствующей вводимой переменной (в данном примере — это ячейка (3, 1)). Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным пе­ременным, и ячейку, соответствующую вводимой переменной. В табл. 5.23 показан цикл для вводимой переменной х₃₁. Для любой вводимой переменной можно по­строить только один замкнутый цикл.

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

х_п = 5-0>0, х₂₂ = 5-0>0, х, = 10-0>0.

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

Таблица 5.23

■2 v₃ = 4 v₄ = 15 Предложение

и₂ - 5

5-еч

t 4 в -■•

-10 + в

: 7

5-вН

-16

■15­

16 ^9

•5 + <

: 18

■К ю-е

Спрос

Отсюда следует, что наибольшее значение, которое может принять 0, равно 5, при этом переменные л_п и х._п обращаются в нуль. Поскольку только одна переменная исключается из базиса, в качестве исключаемой можно выбрать как х_и, так и х₂₂. Остановим свой выбор нал^-,,.

Определив значение для вводимой переменной (л₃₁ = 5) и выбрав исключаемую переменную, далее следует откорректировать значения базисных переменных, соответствующих угловым ячейкам замкнутого цикла, как показано в табл. 5.24. Поскольку перевозка единицы груза по маршруту (3, 1) уменьшает общую стои­мость перевозок на 9 долл. (= и_ъ + v, - с₃₁), суммарная стоимость перевозок будет на 9x5 = 45 долл. меньше, чем в предыдущем решении. Таким образом, новая сум­марная стоимость перевозок будет равна 520 - 45 = 475 долл.

Имея новое базисное решение, следует повторить вычисления потенциалов, как показано в табл. 5.24. Новой вводимой в базис переменной будет лг₁₄. Замкнутый цикл, соответствующий этой переменной, позволяет найти ее значение (л_]4 = 10) и исключаемую переменную л₂₄.

Новое решение, показанное в табл. 5.25, на 4 х 10 = 40 долл. уменьшает значение целевой функции. Таким образом, новая суммарная стоимость перевозок составля­ет 475 - 40 = 435 долл. Теперь новые значения величин и, + v_f - с_ц для всех небазис­ных переменных х_ц отрицательные. Поэтому решение, представленное в табл. 5.25, оптимально.