XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 31
Текст из файла (страница 31)
Симплеисиый метод решения задач транспортного типа 223 222 б. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА Таблица 5.19 Заметим, что большинство исследователей склонны считать метод минимальной стоимости более эффективным (в смысле значения целевой функции, соответствующего найденному начальному базисному решению) по сравнению с методом северозападного угла. Но в общем случае это вряд ли верно (см. задачу 5.12) и при решении практических задач для нахождения начального базисного решения классической транспортной задачи можно использовать любой иэ известных методов. Изучение симплексного метода решения классической транспортной задачи при известном начальном базисном решении начнем с доказательства трех основополагающих утверждений.
Условимся называть систему линейных алгебраических уравнений треуеольпоб, если она содержит по крайней мере одно уравнение с единственным неизвестным, при исключении которого опять найдется по крайней мере одно уравнение с единственным неизвестным, и так далее, пока не будут исчерпаны все неизвестные'. Теорема 5.1. Все допустимые базисные решения классической транспортной задачи задаются треугольной системой линейных алгебраических уравнений. М Пусть рассматриваемая классическая транспортная задача представлена своей транспортной таблицей (см.
табл. 5.1). До- 'Такая система после соответствующей перестановки уравнений и переменных преобразуется в систему с верхней треугольной матрипей. кажем, что по крайней мере одна строка или один столбец этой таблицы содержит лишь одно базисное переменное, после исключения которого вновь образованная транспортная таблица сохранит это свойство. Прежде всего заметим, что з; > О, 1 = 1, т, и О > О, у = = 1, п. А так как небазнсные переменные модели принимают лишь нулевые значения, то каждая строка и каждый столбец транспортной таблицы содержат по крайней мере по одному базисному переменному. Табл.
5.1 содержит т строк и п столбцов, на пересечении которых расположены переменные х;,. По результатам анализа ограничений (5.15) — (5.17) типа равенства, соответствующих рассматриваемой транспортной таблице, из этих тп переменных лишь т+ п — 1 будут базисными переменными. Поэтому предположение о наличии не менее двух базисных переменных в каждом столбце и каждой строке табл. 5.1 должно быть отвергнуто, так как в этом случае общее число базисных переменных модели не может быть меньшим, чем п+ т.
Не останавливаясь на доказательстве этого очевидного факта, приходим к выводу, что в табл. 5,1 есть по крайней мере одна строка (или столбец), содержащая единственное базисное переменное модели. Если вычеркнуть эту строку (или столбец), произведя необходимую корректировку по спросу (или по поставкам), то проведенные рассуждения можно повторить для вновь полученной транспортной таблицы.
А так как табл. 5.1 эквивалентна системе линейных алгебраических уравнений (5.16), (5.17),то исходное утверждение доказано полностью. В Теорема 5.2. Значение каждого базисного переменного х; в допустимом базисном решении определяется равенством (5.21) лбу з бз где 1 и и' — множества номеров строк и столбцов транспортной таблицы классической транспортной задачи (см. табл. 5.1), 224 5. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА определяющих значение базисного переменного х! в допустимом базисном решении. 4 Согласно теореме 5.1, любое допустимое базисное решение классической транспортной задачи задается треугольной системой линейных алгебраических уравнений. Поэтому в транспортной таблице рассматриваемой задачи (см.
табл. 5.1) по крайней мере одна строка или один столбец содержат единственное базисное переменное хре. Если это строка, то полагают хре —— Яр, в табл. 5.1 заменяют Ое на Ве — Яр и заштриховывают в ней строку с номером р. Если это столбец, то полагают хре — — Ою в табл. 5.1 заменяют Яр на Яр — Р, и заштриховывают в ней столбец с номером д. В результате получают новую таблицу, для которой повторяют эту же процедуру, и так далее, пока не будут определены значения всех базисных переменных в допустимом базисном решении. Из приведенных рассуждений и следует справедливость равенства (5.21).
> Теорема 5.3. Если для транспортной задачи (5.2) выполнены условия (5.3), то в любом ее допустимом базисном решении базисные переменные принимают значения из множества 1ЧО (01. Выполнение условий (5.3) для транспортной задачи (5.2) означает, что мощности всех источников н всех стоков являются целыми положительными. Поэтому утверждение теоремы 5.3 вытекает нз теоремы 5.2. > Замечание 5.7. Поскольку оптимальное решение транспортной задачи (5.1), (5.2) является допустимым базисным решением, то при выполнении условий (5.3) оно удовлетворяет требованию иелочисленности. ф Предположим теперь, что для классической транспортной задачи (5.2), (5.4) известно начальное базисное решение.
Лля 5.5. С иипяененый метод решения задач транспортного типа 225 этой задачи ограничения типа равенства представлены системой линейных алгебраических уравнений (5.15) — (5.17), а целевая функция !(х11,...,х „) =~~ ~~! с;,х;, (5.22) ~=! 1=1 Если каждое 1-е уравнение системы (5.15) умножить на и; с последующим их суммированием по ! = 1, т, а каждое 1-е уравнение системы (5.16) умножить на о„с последующим их суммированием по у' = 1, и, то с учетом (5.22) получаем о! и (с;, — и; — о,)х;, = 1=1 1=1 ш н = ах!1~.
"|хшн) — ~~ Яи! — ~, О,оз (5.23) 1=! 1=1 Значения параметров и;, ! = 1, т, и оз, ! = 1, и, при которых коэффициенты в левой части равенства (5.23) при базисных переменных, входящих в исходное допустимое базисное решение, были равны нулю, называют симплезвс-миоз!сителлми лми1 соответствующими рассматриваемому допустимому базисному решению. Мож но показать, что для оптимального решения изучаемой классической транспортной задачи симплекс-множители являются значениями двойственных переменных в оптимальном решении двойственной задачи линейного программирования.
Поэтому для обозначения симплекс-множителей использ— т обозначения двойственных переменных. ользуМножество й пар индексов (1, у), соответствующих базисным переменным, содержит т+ п — 1 элементов, и можно показать, что система т+ и — 1 линейных уравнений и!+и! =об (! !) б!1, (5.24) всегда Разрешима относительно т+ и неизвестных и;, — 1 ни =1п.
П иеиэ — При ее решении, как правило независимо му еиэвестному придают нулевое значение. Л.Л. Симолеясный метод решения эадач транспортного типа 227 226 о. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА Решив систему линейных алгебраических уравнений (5.24) и определив значения симплекс-множителей, можно найти значения 4, = с;, — ич — п„(1, З') ф Й, (5.25) для коэффициентов при свободных переменных в левой части равенства (5.23). Согласно (5.23), уменьшить значение целевой функции 7', соответствующей исходному допустимому базисному решению, можно путем введения в базис рассматриваемой задачи линейного программирования лишь того свободного переменного х,, для которого д; < О. При этом естественно выбирать то свободное переменное, для которого отрицательный коэффициент будет наибольшим по модулю. Если же коэффициенты при всех свободных переменных будут неотрицательными то уменьшить значение целевой функции невозможно и исходное допустимое базисное решение является оптимальным решением.
Пример 5.9. Продолжим рассмотрение классической транспортной задачи, начатое в примере 5.8. Для этой задачи найдено начальное допустимое базисное решение, характеризуемое значениями базисных переменных модели яы се 6, хээ = 1, яз1 — — 1, тзз = 4, хээ = 3, тзл — — 2 и значением целевой функции У= 2 6+0. 1+5 1+8.4+15 3+9.2= 112 (см. табл. 5.17). Воспользовавшись этими результатами и данными, представленными в табл. 5.17, выписываем систему линейных алгебраических уравнений (5.24): в1+ р1 — -2, в2+п2=0, из+из = 5, из+из=8, из+ из =15 из+па = 9 и находим симплекс-множители в предположении, что из = 0: и1 = -3, из = -8, из = О, п1 = 5, рз = 8, пз = 15, рл = 9. Используя полученные значения симплекс-множителей и извест- ные удельные стоимости (с;Д, представленные в табл.
5.17, вычисляем коэффициенты при свободных переменных соглас- но (5.25): пш = 3+3 — 8= — 2, д1з = 11+ 3 — 15= -1, д14 = 7 + 3 — 9 = +1, пю =1+8 — 5=+4, ПЗЗ = 6+ 8 — 15 еа — 1, вял=1+8 †9. В новое допустимое базисное решение удобно ввести свободное переменное х,з, так как )с11э) = шахЦдд(, )д1з), )Ыэз9. Ф Теперь необходимо найти то базисное переменное, которое должно быть выведено из базиса. В симплекс-методе реализация этого шага связана с условием доиустппмосши выбора. Заметим, что для транспортной задачи все коэффициенты при переменных в ограничениях (5.15), (5.16) типа равенства равны либо единице, либо нулю. Поэтому в отношениях, используемых в симплекс-методе при проверке условия допустимости выбора, в знаменателе всегда будет стоять единица, и они полностью определяются значениями базисных переменных.
Для уяснения идеи, используемой в симплексном методе при определении базисного переменного, выводимого из базиса, обратимся к примеру 5.9 и предположим, что при введении в базис свободного переменного я,з оно примет значение ш > О. В этом случае для сохранения ограничения по первой строке транспортной таблицы (см. табл. 5.17) значение базисного переменного хы должно уменьшиться на м, т.е, хм — — 6 — ш. Но тогда для сохранения ограничения по первому столбцу транспортной таблицы значение базисного переменного хз, должно увеличиться на ш, т.е. хз, = 1+ ш.
В этом случае для 228 о. ЗАДАЧИ ТРАНСПОРТНОГО ТИПА Л $ Симпаеисиыи метод р задач тр портиого типа 229 сохранения ограничений по третьей строке и второму столбцу транспортной таблицы значение базисного переменного хзг должно уменьшиться на м, т.е. хзг = 4 — ш.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
