XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 32
Текст из файла (страница 32)
Схема проведенных рассуждений представлена в табл. 5.20, в которой опущены значения с;„1= 1, 2, 3, у = 1,4. Таблица 5.20 С ростом х|г = о~ > 0 базисные переменные хы = 6 — ш и хзг = 4 — о~ будут уменьшаться. Следовательно, максимально возможное значение ш равно 4, так как при этом значении м базисное переменное хзг принимает нулевое значение. При дальнейшем увеличении значений ш базисное переменное ззг становится отрицательным, что противоречит требованию неотрицательности переменных в (5.2).
Следовательно, значение нового базисного переменного хгг равно 4, а переменное хзг должно быть выведено из базиса. Необходимость введения нового базисного переменного со значением ы > 0 приводит к построению так называемого цикла гтграисгаортпиот1 тпаблицм. В табл. 5.20 цикл представлен направленными звеньями замкнутой ломаной х,г -+ хы — ~ -+ хзг -+ хзг -+ х|г, начало и конец которой находятся в клетке, соответствующей вводимому в базис переменному модели хгг.
Эта ломаная имеет горизонтальные и вертикальные звенья, стыки которых обязательно находятся в клетках транспортной таблицы, соответствующих базисным переменным (за исключением стыка „начало — конец"). Понятно, что ориентация цикла может быть любой. Перемещаясь в любом направлении от клетки транспортной таблицы, соответствующей вводимому в базис переменному, в первой вершине ломаной (стык звеньев) вычитаем о~ иэ соответствующего базисного переменного, в следующей вершине прибавляем ш к соответствующему базисному переменному, затем опять вычитаем и т.д., пока не вернемся в исходную клетку. Можно доказать, что такой цикл транспортной таблицы существует и определяется однозначно для любого переменного, вводимого в базис.
В общем случае цикл транспортной таблицы, представляемый в виде замкнутой ломаной, может иметь сложную ступенчатую конфигурацию с самопересечениями (зти самопересечения не могут быть в клетках базисных переменных). Для нас цикл транспортной таблицы интересен лишь в одном отношении: он позволяет определять те базисные переменные, нэ которых мы вычитаем ы. Выбрав из этих переменных то, которое имеет наименьшее значение, мы получим выводимое из базиса переменное. Пример 5.10. Вернемся к рассмотрению классической транспортной задачи, начатому в примерах 5.8, 5.9. Новое допустимое базисное решение характеризуется значениями хы — — 2, х~г = 4, хгг = 1, хзг = 5, ззз = 3, хз4 — 2 базисных переменных модели (см.
пример 5.9 и табл. 5.20) и значением целевой функции У= 2.2+3 4+0 1+5 5+15 3+9 2= 104 (см. табл. 5.17). На этом первая итерация снмплексного метода завершена. На второй итерации система линейных алгебраических уравнений ~5.о ( .24) для нахождения симплекс-множителей имеет следующий вид (см. табл. 5.17): иг+ог — — 2, и1+ ог =3, иг+ог =О, из+ о1 — — 5, из+из =15, из+од =9, иг=-6, из=О, иг — — — 3, пз = 15, п4 = 9. пг — — 6, п1 —— 5, Аз=6+6 — 15= — 3, А4=1+6 — 9=-2, <~зг=8 — 0 — 6=2.
Аз=11+3 — 15=-1, 44 = 7+3 — 9= 1, иг1=1+6 †5, Из этой системы находим и1 = — 3, иг=-9, из=О, пг = 5, иг = 6, пз = 15, пл — — 9. й4з = 11+ 3 — 15 = — 1, Ыгг=О+9 — 6=3 а'14 — — 7+3 — 9= 1, Иг| =1+9 — 5= 5, Иг4= 1+9 — 9= 1, 4(эг=8 †0 †. Таблица 5.9! 230 а 3АдАЧи ТРАнспОРТНОГО ТИПА а ее решением являются значения Используя полученные значения симплекс-множителей и извест- ные удельные стоимости с; иэ табл. 5.17, вычисляем коэффи- циенты для небазисных переменных согласно (5.25): В новое допустимое базисное решение целесообразно ввести свободное переменное хгз так как (агз)=шахЦИгз(, р(гз), )дг4О Для определения базисного переменного, которое необходимо вывести из базиса, воспользуемся циклом транспортной таблицы хгз — ~ хгг -+ хгг -+ хп -4 хз1-4 хзз -+ хгз (табл.
5.21). Сравнив базисные переменные, из которых вычитается оз> находим наименьшее иэ них: хгг = 1 — оз. Таким образом, ш = 1, переменное хгг должно быть выведено иэ базиса, а новое допустимое базисное решение характеризуется значениями базисных переменных х„= 1, хгг = 5, хгз — — 1, хз| — — 6, хзз = 2, хз4 — 2 и значением целевой функции 1 = 2 1+3 5+6 1+5 6+15 2+9 2 = = 101 (см. табл. 5.17). Вторая итерация симплексного метода завершена. 5.а Симпяеисиый метод решения задач транспортного типа 231 На третьей итерации система линейных алгебраических уравнений (5.24) для нахождения симплекс-множителей имеет следующий вид (см. табл.
5.17): и1 + п| = 2, иг+пг=3, из+из =6, из+пг = 5, из+ пз = 15, из+ п4 = 9. Используя полученные значения симплекс-множителей и известные удельные стоимости с; (см. табл. 5.17), вычисляем коэффициенты для свободных переменных согласно (5.25): На а третьей итерации отрицательную оценку имеет единственное свободное переменное хгз, которое и вводим в базис. Для определения базисного переменного, которое необходимо вывести иэ базиса, воспользуемся циклом транспортной таблицы хгэ -+ х11 -+ хз1 -+ хзэ, представленным в табл. 5.22. Сравнив базисные переменные, из которых вычитается оз, находим наименьшее из них: хы — — 1 — ш.
Таким образом, из=1 переменное хы должно быть выведено иэ базиса, а новое допустимое базисное решение характеризуется значениями базисных переменных хгг = 5, хгз = 1, хгз= 1, хэ1 = 7, хэз = 1, хз4 = 2 и значением 233 Вопросы и задачи 232 Таблица 5.л9 Вопросы и задачи и1+иг = 3, и1+ из = 11, из+из = 6, из+ и1 — — 5, из+ из = 15 из+ иа — — 9. Иэ нее находим иг=-9, из=О, и1 — — — 4, иг — 7, из= 15, на=9.
сч — — 5, Игг=О+9 — 7=2, Ига=1+9 †9, Изг = 8 — 0 — 7 = 1. 4~=2+4 †5, Н1а=7+4 †9 Иг| — — 1+9 — 5= 5, 5. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА целевой функции 7 = 3 5+11 1+6 1+ 5 7+15.1+9.2 = 100. На этом третья итерация симплексного метода завершена. На четвертой итерации система линейных алгебраических уравнений (5.24) для нахождения симплекс-множителей имеет следующий вид (см.
табл. 5.17): Используя полученные значения симплекс-множителей и извест- ные удельные стоимости с;, вычисляем коэффициенты для не- базисных переменных согласно (5.25): А так как все найденные коэффициенты неотрицательны, то решение рассматриваемой задачи завершено и оптимальным является допустимое базисное решение, полученное на преды- дущей (третьей) итерации симплексного метода. 5.1. В каком случае транспортную задачу называют классической транспортной задачей? 5.2. Мажет ли множество допустимых решений транспортной задачи (5.2), (5.3): а) быть пустым; б) содержать допустимые решения, которые не удовлетворяют требованию целочисленности; в) содержать оптимальные решения, которые не удовлетворяют требованию целочисленности? 5.3.
В чем заключается принципиальное отличие транспортной задачи с промежуточными пунктами от классической транспортной задачи? Чем отличаются транспортные таблицы этих задач? 5.4. Как связаны между собой задача о назначениях и классическая транспортная задача? В чем заключается специфика задачи о назначениях? 5.5. В 5.3 обоснована процедура перехода от задачи о назначениях с критерием минимизации суммарных затрат к задаче о назначениях с критерием максимизации суммарной эффективности. Возможен ли обратный переход? Если такой переход возможен, то как его реализовать? 5.6.
Существует ли связь между классической транспортной задачей и задачей выбора кратчайшего пути? Если такая связь существует, то в чем она заключается? 234 з. ЗАДА ЧИ ТРАНСПОРТНОГО ТИПА Вопроси и задачи 235 5.7. Можно ли утверждать, что для задач транспортного типа циклы могут содержать лишь сети задачи выбора кратчайшего пути? Ответ аргументируйте.
5.8. Почему симплекс-метод не является эффективным средством решения для задач транспортного типа? 5.9. В чем заключается основная идея симплексного метода решения классической транспортной задачи? 5.10. Докажите, что коэффициенты при свободных переменных, определяемые по формуле (5.25), не зависят от значения свободного переменного при решении системы линейных алгебраических уравнений (5.24) для определения значений симплекс-множителей.
5.11. С чем связана идея, используемая в симплексном методе при определении базисного переменного, выводимого из базиса? 5.12. Для классической транспортной задачи, транспортная таблица которой представлена в табл. 5.5, найдите начальное базисное решение, используя: а) правило северо-западного угла; б) метод минимальной стоимости. Ответ представьте в виде матрицы переменных модели. Ответ: 1000 0 0 600 0 400 а) Х = 900 600 0 ; б) Х = 1300 200 0 0 800 400 0 1200 О 5.13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
