XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 30
Текст из файла (страница 30)
табл. 5.9). Таблица 5.10 По- став- ки Пункт потребления Пункт произ- водства Х?4(С?4 хг?1Г27 хгбЯ226 ~0 Хбб~~ 65 Х54ГС544 Хб? Гсб? х??ГО Х72ПС?2 Спрос Перейдем к рассмотрению примеров, связанных с задачей выбора кратчайшего пути. Пример 5.6. Рассмотрим задачу, которую в литературе по исследованию операций называют задачей о замене оборуд Предположим, что некоторое транспортное агентство разрабатывает план аренды транспортного оборудования на пе- х?2Гс~г х~ Дьз хгг0 0хгз~Ггз хзз~0 х 556(1 56 *.
))Г х?6() и Х48ГС48 Х58ГС58 Х68ГС688 Х?8ГС?8 Таблица 5 11 е,е Рис. 5.4 х;,=о;, з=1,т; им! ш Е хН=Вз, !и! я! = ~~! в,. !=1 з=! (5. 15) (5.16) (5.17) 214 а ЗАДАЧИ ТРАНСПОРТНОГО ТИПА риод длительностью и — 1 лет, где и ) 1. Агентство может выполнить свои обязательства по перевозке грузов, взяв в аренду транспортную единицу в начале первого года и эксплуатируя ее до начала у'-го года, где у' < и. Если ! < и, то в начале з-го года агентство заменяет эту транспортную единицу новой и эксплуатирует ее до начала !с-го года, где и < и, и т.д.
Величина затрат с;„ на оборудование, взятое в аренду в начале е-го года и замененное в начале у'-го года, где 1 < ! < ! < и, включает арендную плату плюс ожидаемые расходы на ремонт и обслуживание. Необходимо так составить' ыавч замены оборудования, чтобы минимизировать суммарные затраты на его аренду ремонт и обслуживание в течение планового периода. 1 Сеть рассматриваемой задачи при и = 6 представлена на рис. 5,4. Каждый промежуточный пункт (узлы с номерами 2-5) соответствует году, в котором может произойти замена транспортной единицы.
Рассматриваемой задаче соответствует транспортная таблица, представленная в табл. 5.11. Можно показать, что сеть, представленная на рис. 5.4, не имеет циклов. Такие сети называют ацинличесними. Обращаем внимание на то, что все задачи исследования операций, рассмотренные в этой главе, при всем разнообразии их возможных постановок так или иначе могут быть преобразованы к классической транспортной задаче и их естественно называть задачами птранспоретаного пампа. Отметим также, что все задачи транспортного типа имеют сетевую структуру. аБ. Снмпяенсный метод решения задач транспортного типа 215 Ы.
Симплексный метод решения задач транспортного типа Решать задачу транспортного типа, которая тем или иным способом преобразуется в классическую транспортную задачу, относящуюся к задачам линейного программирования, можно с помощью симплекс-метода. Но специфические особенности классической транспортной задачи познолили разработать более эффективный метод ее решения, известный как симпленсныб меепод (или метпод попеенциалоа). Одна из особенностей классической транспортной задачи состоит в избыточности системы ограничений типа равенства, определяющих множество допустимых ре!агний. Действительно, согласно (5.2), эти ограничения имеют следующий вид: 216 5. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА Нетрудно убедиться в том, что базисная система для системы ограничений (5.15)-(5.17) типа равенства содержит и+т — 1 уравнений.
Таким образом, любое допустимое базисное ре!пение классической транспортной задачи (5.2), (5.4) будет содержать и+ т — 1 базисных переменных. Можно показать, что задача линейного программирования, двойственная классической транспортной задаче (5.1)-(5.4), состоит в максимизации целевой Функции 5.5. Симпяеяснмй метод решения задач транспортного типа 217 выполняются условия а) и в), а при выполнении условия б) вычислительный процесс прекращается. Начнем с нахождения начального базисного решения для рассматриваемой классической транспортной задачи, воспользовавшись ее транспортной таблицей (см. табл.
5.1) н так называемым правилом северо-западного угла. Следуя правилу северо-западного угла, полагаем вр(и1,...,и вп1,...вип) = ~1 9;и,+~ Рмп (5.18) в=! 1=! при ограничениях (5.19) 1=1,т, 1=1,п, и,+п, <сб, где переменные и„1= 1,т, и п1, ! = 1,п, не ограниченлв в знаке. При этом, если величины х;, и, и и (1 — "., 7' = 1, и) удовлетворяют ограничениям (5.15) — (5.17) и (5.19) соответственно и, кроме того, 1= 1, тп, ! = 1, и, (5.20) то совокупность всех значений хв, представляет собой оптимальное решение рассматриваемой классической транспортной задачи, Основная идея симплексного метода ~остоит в том, что на каждой итерации для допустимых базисных решений исходной классической транспортной задачи и двойственной ей задачи линейного программирования всегда выполняются два нз следующих трех условий: а) условия (5.15) — (5.17) существования допустимых решений классической транспортной задачи (5.2), (5.4); б) условия (5.19) существования допустимых решений двойственной ей задачи линейного программирования: в) условие (5.20).
Приступая к рассмотрению симплексного метода, заметим, что при его реализации на каждой итерации Если хы — — з1, то выделяем первую строку транспортной таблицы (возможности первого истпочника полностью исчерпаны и х1, — — О, 1= 2,п) и заменяем Р, на Р! — з1. Полученная транспортная таблица соответствует классической транспортной задаче с т — 1 источником и и стоками. Следовательно, процедуру нахождения начального базисного решения можно повторить, определив значение переменного модели хг,, расположенного в северо-западном углу новой транспортной таблицы, и т.д.
Понятно, что если х,! — — Р1, то нужно выделить первый столбец транспортной таблицы (возможностн первого стока полностью исчерпаны и хп = О, ! = 2, т) и заменить 91 на з! — В!. В этом случае полученная транспортная таблица соответствует классической транспортной задаче с т источниками и п — 1 стоками, а в ее северо-западном углу расположено переменное модели х!г. Если з! = Р1, то можно выделить либо только первую строку исходной транспортной таблицы, либо только ее первый столбец.
Так, если выделить первую строку, то Р! — з! — — 0 и на следующем шаге переменное модели хг! становится базисным и принимает нулевое значение. Поэтому на втором шаге выделяем первый столбец. Если сначала выделить первый столбец, то з! — Р! — — О, на следующем шаге переменное модели х!з становится базисным и принимает нулевое значение. Поэтому на втором шаге выделяем первую строку. Таблица 5.Ц Таблица 5.12 Таблица 5 15 Таблица 5.13 218 6. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА Пример 5,7. Пусть классическая транспортная задача, для которой необходимо найти начальное базисное решение, представлена своей транспортной таблицей (табл. 5.12). В эту таблицу включены только значения с<1, 1= 1,2,3, 1 = 1,4. В процессе нахождения начального базисного решения в транспортной таблице будем проставлять значения только базисных переменных.
Это позволит различать нулевые значения базисных переменных начального решения и значения свободных переменных, которые равны нулю всегда. В данном случае 10 = 51 > Р1 —— 5. Поэтому по правилу северо-западного угла полагаем хы — Р, = 5, в табл. 5.12 выделяем первый столбец, фиксируя тем самым, что все остальные переменные этого столбца (хш и хз1) являются свободными и, как следствие, равными нулю. Проставляя ям = 5 и заменяя 5, на 51 — Рм приходим к табл. 5.13. Л.о. Снмплексный метод решение задач транспортного типа 219 В северо-западном углу незаштрихованной части табл.
5.13 находится переменное х1з и 10 = Рз > о1 = 5. Поэтому полагаем х1з =5~ — — 5, в табл. 5.13 заштриховываем первую строку и после замены Рз на Рз — о1 — — 5 приходим к табл. 5.14. В северозападном углу незаштрихованной части табл. 5.14 находится переменное хзз и 5з = 5 = Рз. Таким образом, можно найти два начальных базисных решения, в первом из которых хзз = Рз = 5 и заштриховывается второй столбец в табл. 5.14, а во втором хзз —— 5з = 5 и в табл. 5.14 заштриховывается вторая строка.
Воспользуемся первым из возможных вариантов и, заменив 5з на оз — Рз, приходим к табл. 5.15. В северо-западном углу незаштрихованной части табл. 5.15 находится переменное модели хзз и 0 = Яз < Рз — — 8. Поэтому Таблица 5 16 Таблица 5 17 Таблица 5 18 220 о. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА полагаем хзз = Яз —— 0 и в табл. 5.15 заштриховываем вторую строку и после замены Вз на Вз — Яз = 8 приходим к табл. 5.16. Табл. 5.16 содержит единственную незаштрихованную строку н из нее непосредственно следует, что хзз 8 и хз4 — 7 ° А так как значения свободных переменных равны нулю, то найдено начальное базисное решение, определяемое следующими значениями базисных переменных: хы — — 5, х4з — — 5, хзз — — 5, хзз = О хзз=8, хз4=7.
Кроме правила северо-западного угла разработаны и другие процедуры нахождения начального базисного решения для классической транспортной задачи. Остановимся лишь на одной из них, известной в исследовании операций как метод мимимальмоб ствоимосгпи. Единственное отличие этого метода от метода северо-западного угла заключается в том, что прн его реализации используют переменное х;, которому соответствует минимальная ддедьиал стоимость с;, а не переменное модели, расположенное в северо-западном углу транспортной таблицы. Пример 5.8. Пусть классическая транспортная задача, для которой необходимо найти начальное базисное решение, представлена своей транспортной таблицей (табл, 5.17). Минимальной удельной стоимости сзз = 0 соответствует переменное модели хзз. А так как в данном случае 1 = 5з < о.о.
Снмляексный метод решения эадач транслортного тала 221 < Вз — — 5, то полагаем хзз — — 1, заменяем Вз на Вз †.эз = 4 и после штриховки второй строки приходим к табл. 5.18. В незаштрихованной части табл. 5.18 минимальной удельной стоимости сы = 2 соответствует переменное хы. В данном случае 6 = о1 < В4 — — 7. Поэтому полагаем хы — — 6, заменяем В4 на В4 — о4 = 1 и после штриховки первой строки приходим к табл. 5.19. Табл. 5.19 представляет собой транспортную таблицу с одной незаштрихованной строкой. Поэтому хз4 = 1, хзз —— 4, хзз= 3, хз4= 2 Таким образом, начальное базисное решение рассматриваемой классической транспортной задачи определяется следую- Шими значениЯми пеРеменных: х„= 6, хзз = 1, хз4 — — 1, хзз — — 4, *ЗЗ= 8, ХЗ4ее 2 4 $.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
