Метод указания к лаб работам ИСО, страница 5
Описание файла
Документ из архива "Метод указания к лаб работам ИСО", который расположен в категории "". Всё это находится в предмете "исследование операций (мт-3)" из 5 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "исследование операций" в общих файлах.
Онлайн просмотр документа "Метод указания к лаб работам ИСО"
Текст 5 страницы из документа "Метод указания к лаб работам ИСО"
Требуется составить план перевозок, т.е. указать с какого склада на какие предприятия, и какое количество сырья нужно направить, чтобы заявки были выполнены, а общие расходы на все перевозки были минимальными.
Составим для данной задачи, как это уже было показано раньше таблицу издержек:
| Сток Исток |
|
| … |
| Запасы:
|
|
|
|
| … |
|
|
|
|
|
| … |
|
|
| … | … | … | … | … | … |
|
|
|
| … |
|
|
| Заявки:
|
|
| … |
|
|
Очевидно, что не все m + n уравнений системы ограничений транспортной задачи являются независимыми. Действительно. складывая все ограничения по заявкам и все ограничения по запасам, в силу равенства заявок и запасов, получаем доказательство того, что ранг системы ограничений r = m + n – 1. Следовательно, можно разрешить эти уравнения относительно r базисных переменных, выразив их через остальные k свободные.
k = m×n – r = m×n – m – (n – 1) = m×(n – 1) – (n – 1) Þ
k = (m – 1)×(n – 1).
Мы уже останавливались на факте того, что в задаче линейного программирования оптимальное решение достигается в одной из вершин области допустимых решений, где, по крайней мере, k переменных обращаются в нуль.
Значения 
количества единиц груза, направляемых из пункта Сi в пункт Пj будем называть перевозками. Любую совокупность значений ( ) будем называть планом перевозок, или просто планом. Тогда план будем называть допустимым, если он удовлетворяет балансовым условиям: все заявки удовлетворены и, все запасы исчерпаны.
В свою очередь, допустимый план будем называть оптимальным в том случае, если он приводит к наименьшей стоимости всех перевозок.
Методы решения транспортной задачи не требуют манипуляций с симплекс-таблицами, а сводятся к операциям с таблицей, где в определенном порядке (см. примеры таблиц издержек выше) записаны все условия транспортной задачи – транспортной таблицей. Стоимость перевозок (соответствующие издержки из таблицы издержек) 
будем помещать в правом верхнем углу каждой ячейки, с тем, чтобы в самой ячейке помещать значения соответствующих перевозок ( ). Ниже приведен пример заполнения транспортной таблицы:
| Сток Исток |
|
| … |
| Запасы:
| ||||
|
|
|
| … |
|
| ||||
|
|
| … |
| ||||||||||||||
|
|
|
| … |
|
| ||||||||||||
|
|
| … |
| ||||||||||||||
| … | … | … | … | … | … | ||||||||||||
| … | … | … | … | ||||||||||||||
|
|
|
| … |
|
| ||||||||||||
|
|
| … |
|
| Заявки:
|
|
| … |
|
|
Ячейки таблицы с отличными от нуля перевозками условимся называть базисными, а остальные (пустые – в дальнейшем в транспортную таблицу мы будем заносить только отличные от нуля значения) свободными.
Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного решения или, в случае транспортной задачи, опорного плана перевозок. В отличие от общего случая задачи линейного программирования, решение транспортной задачи всегда существует. Рассмотрим один из способов построения опорного плана – так называемый метод «северо-западного угла».
Нахождение опорного плана методом «северо-западного угла»
Метод «северо-западного» угла реализует интерактивный поиск опорного решения. Идея метода состоит в следующем. На каждой итерации выбирается такое решение, которое бы с одной стороны учитывало бы результаты предыдущих итераций, а с другой стороны по возможности минимизировало бы количество оставшихся итераций.
Применительно к транспортной таблице работу метода «северо-западного угла» можно представить так. Первоначально заполняется самая левая верхняя клетка (северо-западный угол таблицы). Это означает, что мы принудительно посылаем товар со склада 1 потребителю 1. Если количество имеющегося в наличии товара на складе 1 превышает размер запроса потребителя 1, то в северо-западную клетку (1,1) следует поместить значение запроса потребителя 1. В противном случае, то есть в ситуации, при которой склад 1 не в состоянии самостоятельно удовлетворить запрос потребителя 1, в ячейку (1,1) транспортной таблицы следует поместить значение запаса склада 1.
Очевидно, что в случае неравенства (или равенства) запаса на складе 1 запросу потребителя 1 возможны два варианта:
-
Склад 1 полностью удовлетворил запрос потребителя 1, но при этом запас его товаров еще не исчерпан. Тогда на следующей итерации алгоритма мы будем рассматривать соседнюю с востока ячейку, то есть ячейку (1,2) транспортной таблицы.
-
Склад 1 не в состоянии полностью удовлетворить запрос потребителя 1, то есть запас его товаров исчерпан, а запрос потребителя еще не удовлетворен. Тогда на следующей итерации алгоритма мы будем рассматривать соседнюю с юга ячейку, то есть ячейку (2,1) транспортной таблицы.
-
Склад 1 полностью удовлетворил потребности потребителя 1, при этом запас товаров на складе был полностью исчерпан. Тогда на следующей итерации алгоритма мы будем рассматривать соседнюю с юго-востока ячейку, то есть ячейку (2,2) транспортной таблицы.
Описанная процедура обеспечивает выбор ячейки транспортной таблицы для следующей итерации алгоритма поиска опорного решения.
Очевидно, что в силу равенства суммарных заявок (запросов) суммарным запасам на последней итерации алгоритма – ячейка (i,j) – в общем случае окажется, что i-ый склад оставшимся своим запасом полностью удовлетворит оставшийся неудовлетворенным на предыдущих итерациях запрос j-того потребителя.
Рассмотрим работу данного метода на конкретном примере. Пусть задана некоторая транспортная задача и соответствующая ей транспортная таблица:
| Сток Исток |
|
|
|
|
| Запасы: | |||||
|
| 10 | 8 | 5 | 6 | 9 | 48 | |||||
|
| 6 | 7 | 8 | 6 | 5 | 30 | |||||||||||||||
|
| 8 | 7 | 10 | 8 | 7 | 27 | |||||||||||||||
|
| 7 | 5 | 4 | 6 | 8 | 20 | |||||||||||||||
| Заявки: | 18 | 27 | 42 | 12 | 26 | 125 |
Тогда в соответствии с только что описанным методом «северо-западного угла» будем заполнять таблицу перевозками, начиная с северо-западной ячейки (1,1), рассуждая так.
Удовлетворим пункт В1 за счет запаса А1, следовательно
х11= 18. После этого в пункте А1 осталось 30 единиц груза. Удовлетворим запрос пункта В2 за счет остатка А1, следовательно х12 = 27. оставшиеся 3 единицы груза направим в пункт В3 Þ х13 = 3. В составе заявки пункта В3 осталось неудовлетворенным 39 единиц груза. Из них 30 покроем за счет пункта А2, чем его запас будет исчерпан, и еще 9 единиц возьмем из пункта А3, следовательно х23 = 30 и х33 = 9 и т.д. Полученное решение будет не только допустимым, но и опорным.
В результате этих действий получим следующее опорное решение:
| Сток Исток |
|
|
|
|
| Запасы: | |||||
|
| 10 | 8 | 5 | 6 | 9 | 48 | |||||
| 18 | 27 | 3 | |||||||||||||||||||
|
| 6 | 7 | 8 | 6 | 5 | 30 | |||||||||||||||
| 30 | |||||||||||||||||||||
|
| 8 | 7 | 10 | 8 | 7 | 27 | |||||||||||||||
| 9 | 12 | 6 | |||||||||||||||||||
|
| 7 | 5 | 4 | 6 | 8 | 20 | |||||||||||||||
| 20 |
