Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
Пример 6.1. Фирма производит пирожки в трех пекарных цехах, находящих- ся в разных районах города: Центральный, ЖБИ и Парк-Хаус. Помимо продажи своей продукции непосредственно в магазинах при цехах, часть пирожков пла- нируется развозить на современных байках по четырем супермаркетам: «Ву- зовский», «Шарташский», «Академический» и «Московский». Расстояния (в км) от каждого пекарного цеха до определенной торговой точки приведены в табл. 6.2. Таблица 6.2 Район «Вузовский» «Шарташский» «Академический» «Московский» Центральный 4 8 10 2 ЖБИ 4 6 18 8 Парк-Хаус 6 8 40 10 Услуги транспортной компании по перевозке одного килограмма про- дукции составляют 50 коп. за километр. Суточный объем продукции, кото- рый готов произвести для супермаркетов центральный цех, равен 60 кг, цех на ЖБИ — 70 кг, цех на Парк-Хаусе — 20 кг. При этом каждый супермаркет также готов принять лишь определенное количество пирожков, а именно: «Вузовский» — 40 кг, «Шарташский» — 30, «Академический» — 30, «Москов- ский» — 50. Определить оптимальное количество перевозимых пирожков, минимизирующее суммарные транспортные расходы и удовлетворяющее огра- ничениям, накладываемым на объемы груза. Требуется составить экономико- математическую модель данной задачи. Решение. Для составления модели нам необходимо знать матрицу цен, т. е. таблицу со стоимостью перевозки единицы продукции. Например, расстояние от центрального цеха до супермаркета «Вузовский» составляет 4 км, чтобы узнать, сколько мы заплатим за перевозку одного килограмма продукции, умножим километраж на цену перевозки за километр, т. е. 4 · 50 = 200 коп., или 2 руб. Аналогично поступаем с другими данными из таблицы расстояний, по- лучаем следующую матрицу цен: 2 4 5 1 2 3 9 4 . 3 4 20 5 Для того, чтобы нам было проще формализовать данную задачу, перейдем от наименований к номерам, т. е. цеха занумеруем от 1 до 3: Центральный — 1, ЖБИ — 2, Парк-Хаус — 3. Аналогично поступим с супермаркетами. 163 Обозначим: x ij — количество перевезенных пирожков из i-го пекарного цеха в j-й супермаркет, 1, 3; i = 1, 4. j = Нашей целью является минимизация транспортных расходов, то есть: 11 12 13 14 21 22 23 24 31 32 33 34 2 4 5 2 3 9 4 3 4 20 5 min. x x x x x x x x x x x x + + + + + + + + + + + + → При этом нужно учесть ограничения по имеющемуся предложению от пе- карных цехов, т. е. все, что произведено в определенном цехе, должно быть развезено по супермаркетам: x 11 + x 12 + x 13 + x 14 = 60, x 21 + x 22 + x 23 + x 24 = 70, x 31 + x 32 + x 33 + x 34 = 20. Аналогичные ограничения по спросу: x 11 + x 21 + x 31 = 40, x 12 + x 22 + x 32 = 30, x 13 + x 23 + x 33 = 30, x 14 + x 24 + x 34 = 50. Таким образом, учитывая неотрицательность количества, имеем следую- щую модель данной транспортной задачи: 11 12 13 14 21 22 23 24 31 32 33 34 2 4 5 2 3 9 4 3 4 20 5 min, Z x x x x x x x x x x x x = + + + + + + + + + + + + → 11 12 13 14 21 22 23 24 31 32 33 34 11 21 31 12 22 32 13 23 33 14 24 34 60, 70, 20, 40, 30, 30, 50, 0, 1,3, 1,4. ij 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 i j + + + = + + + = + + + = + + = + = + + = + + = ≥ = = + Транспортная задача как задача линейного программирования может быть решена симплексным методом, однако наличие большого числа переменных и ограничений делает вычисления громоздкими, поэтому для решения этого типа задач используется более простой метод, использующий распределитель- ную таблицу. 164 Пример 6.2. Для примера 6.1 составим распределительную таблицу (табл. 6.3). Таблица 6.3 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 4 5 1 60 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 30 50 6.2. Методы нахождения первоначального базисного решения транспортной задачи закрытого типа Решение транспортной задачи начинают с нахождения первоначального плана поставок. Из общей модели транспортной задачи имеем m + n ограни- чений в виде равенств. В данном параграфе мы будем рассматривать задачу закрытого типа, а это означает, что одно из этих равенств должно быть избыточ- ным. Следовательно, задача имеет m + n − 1 независимых ограничений, откуда вытекает, что начальное базисное решение (план поставок) состоит из m + n − 1 базисных переменных. Наиболее часто применяют методы «северо-западного угла» и «минимальной стоимости». Рассмотрим суть метода «северо-западного угла», используя распредели- тельную таблицу транспортной задачи в общем виде. Распределение поставок начинается с верхней левой клетки (северо-западного угла) таблицы. В эту клет- ку помещаются наибольшие возможные необходимые поставки, т. е. максимум из предложения и спроса. Далее вычеркивается строка или столбец с полностью реализованным предложением или с удовлетворенным спросом, т. е. в даль- нейшем в вычеркнутой строке или столбце не помещаются поставки. Если одновременно удовлетворяются спрос и предложение, вычеркивается только строка или только столбец. Если остается невычеркнутой только одна строка или только один столбец, процесс останавливается, иначе переходим к клетке справа, если вычеркнут столбец, или к нижележащей клетке, если вычеркнута строка, и повторяем вышеописанную процедуру. Пример 6.3. Рассмотрим распределительную таблицу (табл. 6.3) из при- мера 6.2. Найдем с помощью этой таблицы начальное базисное решение методом «северо-западного угла» (табл. 6.4). Для удобства цены перевозок запишем в верхний левый угол каждой клетки (табл. 6.5). 165 Таблица 6.4 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 4 5 1 60 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 30 50 Таблица 6.5 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 4 5 1 60 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 30 50 Выполнение начинаем с верхней левой клетки, т. е. груз поставляется от пер- вого пункта отправления в первый пункт назначения, при этом предложение составляет 60 ед. груза, а принять готовы только 40. Следовательно, возможно перевезти только 40 ед., значит, в верхней левой клетке записываем 40 и вычер- киваем первый пункт назначения, так как в него отправлен весь запрошенный им груз, при этом объемы поставок первого пункта отправления сокращаются до 20, что также отмечаем в распределительной таблице (табл. 6.6). Таблица 6.6 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 40 4 5 1 60 20 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 30 50 Далее берем следующую невычеркнутую верхнюю левую клетку, т. е. груз поставляется от первого пункта отправления во второй пункт назначения, при этом предложение составляет 20 ед., а спрос — 30. Следовательно, возможно перевезти только 20 ед., значит, в невычеркнутую верхнюю левую клетку с ценой перевозки, равной 4, записываем 20 и вычеркиваем первый пункт отправления, так как весь имеющийся в нем груз отправлен, при этом объемы потребления 166 второго пункта назначения сокращаются до 10, что отмечаем в распредели- тельной таблице (табл. 6.7). Таблица 6.7 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 40 4 20 5 1 60 20 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 10 30 50 Продолжаем нашу процедуру, берем следующую невычеркнутую верхнюю левую клетку, т. е. груз поставляется от второго пункта отправления во второй пункт назначения, при этом предложение составляет 70 ед., а спрос — 10. Следо- вательно, возможно перевезти только 10 ед., значит, в невычеркнутую верхнюю левую клетку с ценой перевозки, равной трем, записываем 10 и вычеркиваем второй пункт назначения, так как в него отправлен весь запрошенный им груз. При этом объемы поставок первого пункта отправления сокращаются до 60, что также отмечаем в распределительной таблице (табл. 6.8). Таблица 6.8 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 40 4 20 5 1 60 20 2 2 3 10 9 4 70 60 3 3 4 20 5 20 Объемы потребления 40 30 10 30 50 Аналогично переходим в следующую невычеркнутую верхнюю левую клетку, т. е. груз поставляется от второго пункта отправления в третий пункт назначе- ния. Рассуждая таким же образом, как на предыдущем шаге, получаем табл. 6.9. Таблица 6.9 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 40 4 20 5 1 60 20 2 2 3 10 9 30 4 70 60 30 3 3 4 20 5 20 Объемы потребления 40 30 10 30 50 167 И вновь переходим в следующую невычеркнутую верхнюю левую клетку и с помощью подобных рассуждений получаем табл. 6.10. Таблица 6.10 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 40 4 20 5 1 60 20 2 2 3 10 9 30 4 30 70 60 30 3 3 4 20 5 20 Объемы потребления 40 30 10 30 50 20 Остается последняя клетка, т. е. груз поставляется из третьего пункта от- правления в четвертый пункт назначения. Здесь предложение и спрос равны 20, что естественно, так как задача закрытого типа. Следовательно, записываем в оставшуюся клетку 20, тогда итоговая таблица будет иметь вид (табл. 6.11). Таблица 6.11 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 40 4 20 5 1 60 20 2 2 3 10 9 30 4 30 70 60 30 3 3 4 20 5 20 20 Объемы потребления 40 30 10 30 50 20 Начальное базисное решение найдено, проинтерпретировать его можно следующим образом. Исходя из заполненных клеток, имеем: 40 ед. груза необ- ходимо перевезти из первого пункта отправления во второй пункт назначения, 20 из первого во второй, 10 из второго пункта отправления во второй пункт назначения, 30 из второго в третий, еще 30 из второго только уже в четвертый и 20 из третьего в четвертый. Для того, чтобы найти стоимость перевозки, нужно количество перевезенного груза из каждого пункта назначения в пункт отправления умножить на соответствующую стоимость перевозки. Опираясь на последнюю распределительную таблицу, получаем, что стоимость перевозки: Z = 2 · 40 + 4 · 20 + 3 · 10 + 9 · 30 + 4 · 30 + 5 · 20 = 680. Стоит отметить, что метод «северо-западного угла» прост в применении, однако решение, полученное с помощью него, далеко не всегда оптимальное. Более выгодная стоимость перевозки чаще получается при использовании метода «минимальной стоимости», но в примере 6.4 будет показано, что это не всегда. 168 Рассмотрим суть метода «минимальной стоимости», используя распреде- лительную таблицу транспортной задачи в общем виде. Распределение поставок начинается с клеток, в которых цена перевозок c ij наименьшая. Если таких клеток несколько, выбрать можно любую, договоримся выбирать первую встретившуюся при просмотре по строкам сверху вниз. В эти клетки помещаются наибольшие возможные необходимые поставки. Далее поставки распределяются по возрастанию тарифов по свободным клеткам с учетом запасов производителей и нужд потребителей. Более подробно рас- смотрим работу этого метода на транспортной задаче из примера 6.3. Пример 6.4. Выполнение начинаем с той клетки, где наименьшая цена пере- возки (табл. 6.12), т. е. с клетки с ценой 1, при которой груз поставляется из пер- вого пункта отправления в четвертый пункт назначения, при этом предложение составляет 60 ед. груза, а принять готовы только 50. Следовательно, возможно перевезти только 50 ед., значит, в выбранной клетке записываем 50 и вычерки- ваем четвертый пункт назначения, так как в него отправлен весь запрошенный им груз, при этом объемы поставок первого пункта отправления сокращаются до 10, что также отмечаем в распределительной таблице (табл. 6.13). Таблица 6.12 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 4 5 1 60 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 30 50 Таблица 6.13 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 4 5 1 50 60 10 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 30 50 Далее выбираем следующую невычеркнутую клетку с минимальной ценой перевозки. Таких клеток две: единица груза из первого пункта отправления в первый пункт назначения и из второго пункта отправления в первый пункт назначения поставляется за 2 ден. ед. Как договорились ранее, выбираем в этом случае ту клетку, которая встретилась первой при просмотре таблицы по стро- 169 кам сверху вниз, т. е. ту, которая отвечает за перевозку груза из первого пункта отправления в первый пункт назначения. Предложение в данном случае состав- ляет 10, спрос — 40. Следовательно, возможно перевезти только 10 ед., значит, в выбранную клетку с ценой перевозки, равной 2, записываем 10 и вычеркиваем первый пункт отправления, так как весь имеющийся в нем груз отправлен, при этом объемы потребления второго пункта назначения сокращаются до 30, что отмечаем в распределительной таблице (табл. 6.14). Таблица 6.14 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 10 4 5 1 50 60 10 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 30 30 50 Продолжаем нашу процедуру, берем следующую невычеркнутую клет- ку с наименьшей ценой перевозки, т. е. груз поставляется от второго пункта отправления в первый пункт назначения, при этом предложение составляет 70 ед., а спрос — 30. Следовательно, возможно перевезти только 30 ед., значит, в выбранную клетку с ценой перевозки, равной двум, записываем 30 и вычер- киваем первый пункт назначения, так как в него отправлен весь запрошенный им груз. При этом объемы поставок первого пункта отправления сокращаются до 40, что отмечаем в распределительной таблице (табл. 6.15). Таблица 6.15 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 10 4 5 1 50 60 10 2 2 30 3 9 4 70 40 3 3 4 20 5 20 Объемы потребления 40 30 30 30 50 Аналогично переходим в следующую клетку с минимальной ценой, т. е. груз поставляется от второго пункта отправления во второй пункт назначения. Рассуждая таким же образом, как на предыдущем шаге, получаем табл. 6.16. И вновь переходим в клетку с минимальной ценой и с помощью подобных рассуждений получаем табл. 6.17. 170 Таблица 6.16 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 10 4 5 1 50 60 10 2 2 30 3 30 9 4 70 40 10 3 3 4 20 5 20 Объемы потребления 40 30 30 30 50 Таблица 6.17 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 10 4 5 1 50 60 10 2 2 30 3 30 9 10 4 70 40 10 3 3 4 20 5 20 Объемы потребления 40 30 30 30 20 50 Остается последняя клетка, т. е. груз поставляется из третьего пункта от- правления в третий пункт назначения. Здесь предложение и спрос равны 20, что естественно, так как задача закрытого типа. Следовательно, записываем в оставшуюся клетку 20, тогда итоговая таблица будет иметь вид (табл. 6.18). Таблица 6.18 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 10 4 5 1 50 60 10 2 2 30 3 30 9 10 4 70 40 10 3 3 4 20 20 5 20 Объемы потребления 40 30 30 30 20 50 Начальное базисное решение найдено. Опираясь на последнюю распредели- тельную таблицу, получаем стоимость перевозки: Z = 2 · 10 + 1 · 50 + 2 · 30 + 3 · 30 + + 9 · 10 + 20 · 20 = 710. Заметим, что решая эту же задачу методом «северо-запад- ного угла», мы находим план перевозки, стоимость которой составит 680 ден. ед. Таким образом, этот пример показывает, что не всегда метод «минимальной стоимости» дает лучшее решение. Более того, нет уверенности, что не суще- ствует еще более оптимального решения, при котором стоимость перевозки будет еще меньше, нежели получившаяся в данном методе. 171 6.3. Критерий оптимальности базисного решения транспортной задачи и метод потенциалов Как уже было сказано выше, начальное базисное решение не всегда может являться оптимальным в транспортной задаче, поэтому для нахождения оп- тимального плана перевозок был разработан метод потенциалов. Принцип работы этого метода аналогичен симплекс-методу: сначала находят начальный базисный план, а затем последовательно его улучшают до получения опти- мального. Начальный базисный план будем находить методом «северо-западного угла» или «минимальной стоимости». Теорема (критерий оптимальности). Если для некоторого базисного плана X = (x 11 , x 12 , …, x 1j , …, x 1n , x 21 , x 22 , …, x 2j , …, x 2n , …, x i1 , x i2, …, x ij , …, x in , …, x m1 , x m2 , …, x mj , …, x mn ) существуют такие числа u 1 , u 2 , …, u i , …, u m , v 1 , v 2 , …, v j , …, v n , что выражение, называемое оценками элементов (клеток распределительной таблицы), ∆ ij = u i + v j − c ij ≤ 0 для любых 1, i m = и , , 1 j n = то данный базисный план X является оптимальным в транспортной задаче. Числа u 1 , u 2 , …, u i , …, u m , v 1 , v 2 , …, v j , …, v n из сформулированной теоремы называются потенциалами соответственно пунктам отправления и пунктам назначения. Кроме того, заметим, что можно расширить формулировку критерия оп- тимальности следующим образом. Если для некоторого базисного плана X = (x 11 , x 12 , …, x 1j , …, x 1n , x 21 , x 22 , …, x 2j , …, x 2n , …, x i1 , x i2 , …, x ij , …, x in , …, x m1 , x m2 , …, x mj , …, x mn ) существуют такие числа u 1 , u 2 , …, u i , …, u m , v 1 , v 2 , …, v j ,…, v n , что при и при 0 0 i j ij ij i j ij ij u v c x u v c x + = > + ≤ = для всех 1, i m = и , , 1 j n = то данный базисный план X является оптимальным в транспортной задаче. Такая запись критерия оптимальности позволяет понять, что потенциалы можно найти из условия u i + v j = c ij при x ij > 0, а значит, возможно построить алгоритм нахождения оптимального решения транспортной задачи. А л г о р и т м решения транспортной задачи закрытого типа: 1. Найти первоначальное базисное решение (распределение поставок) ме- тодами «северо-западного угла» или «минимальной стоимости». 2. Проверить решение на оптимальность методом потенциалов. Для этого найти потенциалы для каждой строки и столбца из условия u i − ν j = c ij , справед- ливого для всех занятых клеток распределительной таблицы. Первоначально положить u 1 = 0. 172 3. Для всех свободных клеток рассчитать оценки ∆ ij = u i + v j − c ij . Если все ∆ ij ≤ 0, то найденное решение оптимально. Если среди оценок есть хотя бы одно положительное число, то найденное решение не является оптимальным. 4. Если решение неоптимально, необходимо перейти к новому базисному решению (новому плану поставок), которое ближе к оптимальному, чем пре- дыдущее. Необходимо ввести в базис свободную переменную θ, имеющую наи- большую положительную оценку, т. е. в клетку с наибольшей оценкой ставим θ. В случае, если наибольших положительных оценок несколько, то выбираем ту, у которой в клетке цена наименьшая. Далее проводим цикл для соответству- ющей этой переменной клетки. Цикл строится по занятым клеткам, начиная от θ, и имеет прямоугольную конфигурацию. Вершинам цикла приписывается определенный знак, причем клетке со свободной переменной θ — знак «плюс», а всем остальным клеткам поочередно знаки «минус» и «плюс» (будем называть эти клетки минусовыми и плюсовыми). Среди минусовых клеток находится наименьший объем поставок, и θ присваивается его значение, далее идет пе- рераспределение по циклу: в плюсовых клетках его надо прибавить к поставке, в минусовых клетках вычесть. После вычитания получится, по крайней мере, один нулевой элемент (так как θ определяется как наименьший элемент плана, стоящий в минусовых клетках), этот ноль мы не пишем, и именно этот элемент выводится из базиса. Далее остается выписать новое решение и значение целе- вой функции и перейти в пункт 2 данного алгоритма. Приведенный алгоритм решения транспортной задачи в некоторой лите- ратуре называют методом потенциалов. Поясним некоторые моменты в приведенном алгоритме. Потенциалы на- ходятся из условия u i − ν j = c ij , где 1, i m = и , , 1 j n = т. е. потенциалы являются решением системы (именуемой системой потенциалов) из n + m неизвестных с n + m − 1 неизвестными (так как именно столько будет занятых клеток (эле- ментов) в базисном решении). Таким образом, число неизвестных превышает число переменных, именно поэтому одно из неизвестных необходимо взять за произвольную константу, для определенности всегда договоримся поло- жить u 1 = 0. Здесь стоит отметить очень важный случай. Если в процессе решения транспортной задачи получено решение, в котором количество занятых кле- ток меньше m + n − 1, то это решение называется вырожденным. Расчет потен- циалов выполнить невозможно. В этом случае недостающее число занятых клеток выполняется путем введения нулевых поставок в некоторые клетки. Их выбор определяется возможностью расстановки потенциалов, а именно: если, согласно четвертому пункту алгоритма, после вычитания из минусовых клеток значения θ мы получим несколько нулей, то нельзя их отбрасывать все, так как из базисного решения выводится только один элемент. В этом случае 173 выводят из базиса какой-нибудь один элемент, остальные нули оставляют. Таким образом, далее такие клетки считаются занятыми, и решение продол- жается обычным образом. Циклом в распределительной таблице называется ломаная линия, вершины которой расположены в занятых клетках, а звенья — вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое — в столбце. Если ломаная линия, образующая цикл пересекается, то точки самопересечения не являются вершинами. При- меры некоторых циклов показаны на рисунке. Примеры циклов распределения груза Теперь рассмотрим работу приведенного алгоритма на числовом примере. |