Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 23
Текст из файла (страница 23)
Доказательство можно провести индукцией по числу гл+ и = й. Пусть ль+ л = 2 — минимально возможное число. Матрица А состоит из единственного элемента н утверждение очевидно. Предположим, что для пз + л = й получаемые этим методом столбцы линейно независимы. Докажем соответствующее утверждение для го+о = й+1. Не ограничивая общности, считаем, что на первом этапе выводится из рассмотрения первая строка или первый столбец (в противном случае мы можем строки или столбцы переобозначить и поменять местами).
Если мы выводим из рассмотрения первую строку матрицы, то зто означает, что первый пункт отправления А, обслужен полностью, зп — базисный элемент, а все элементы хц = О, 7' = 2,...,л. Первое ограничение уравнений (а) выполнено, в матрице ограничений А можно убрать первую строку и первые и столбцов. Получилась меньшая матрица размера (т — 1+ л) х (т — 1)л, а для нее по предположению индукции соответствующие столбцы являются линейно независимыми. Добавление столбца с единицей на первом месте (и еще на одном из последних л мест) к ль -1- л — 2 столбцам, расширенным и начинающимся с нуля образует систему ш+ л — 1 линейно независимых столбцов. Если мы выводим из рассмотрения первый столбец матрицы, то зто означает, что первый пункт назначения обслужен полностью, пн— базисный элемент, а все элементы ап = О, 1 = 2,...,гл.
Первое ограничение уравнений (Ь) выполнено, в матрице ограничений А можно убрать гл+ 1-ю строку и соответствующие гп столбцов. Получилась подобная меньшая матрица размера (ш + и — 1) х (и — 1)гл, а для нее по предположению индукции соответствующие столбцы являются линейно независимыми. Добавление столбца с единицей на гл+ 1-м месте (и еще на одном из первых лз мест) к го+ л — 2 линейно независимым столбцам, расширенным и имеющим на гп+ 1-м месте нули образует систему из ш+ и — 1 линейно независимых столбцов. Индукция закончена.
128 Глава 2. Линейное программирование 5.4. Метод потенциалов Сформулируем правило решения транспортной задачи методом потенциалов (обоснование этого метода булет дано в п. 5.7). ! . Привести задачу к замкнутой модели (см. п. 5.1). 2. Найти первоначальный план перевозок х, являюизийгя крайней точкой мноягества допустимых элементов. 3. Исследование плана перевозок х.
Для найденного плана х построить матрицу С = (су) щ!,, с;,". = и! + е,, определяя гп+ и потенциалов и;,е из системы го+ и — 1 уравнений: я, + о. = с; для базисных индексов з,31 Эти уравнения линейно независимы (зто следует из линейной независимости столбцов, соответствующих базисным элементам), поэтому для однозначного определения потенциалов и„о положим заранее один из потенциалов заданной величине, например, положим и! — — О. Замечание.
Элементы с,з матрицы С не зависят от первоначального выбора и!, Действительно. Предположим, что вместо первоначального потенциала и, мы бы взяли потенциал й! = я! +1. Тогда 6! = о, — ! и все й; = и; + 1, б. = в — ! при базисных з,у', поскольку нз + ез = сзз при базисных 3,7. Таким образом, сумма йз+й = и, +!+ о — ! = к, + о = с;. 3 '3 не зависит от выбора первоначального потенциала и,.
4. Провести исследование матрицы 35: = С вЂ” С. Если 25 > О, то исследуемый план х является решением задачи (Р), а потенциалы и„е являются решением двойственной задачи. Если среди элементов матрицы 21 есть отрицательные, то выберем наименьший элемент. Пусть, например, зьз,зт = Ппп 2543 < О. 15 5. Построить новый план перевозок, являющийся крайней точкой мнохсества допустимых элементов. Положим т;'„„= 1, х,' = х, х ! для базисных индексов 3, у, где 1— некоторая положительная величина (не изменяя остальные небазисные компоненты хо равные нулю) так, чтобы х'; по-прежнему были неотрицательны, но олна из базисных компонент обратилась бы в ноль. Вектор матрицы А, соответствующий этой компоненте, выводим из числа базисных, а вектор матрицы А, соответствующий переменной хцзт, вводим в число базисных векторов.
Далее вновь начинаем исслелование полученной крайней точки х', т.е. возвращаемся к и.3. В невырожденной задаче в ноль может обратиться только олна из компонент вектора х. В вырожденной задаче в ноль может обратиться несколько компонент. В этом случае из числа базисных векторов исключается любой вектор с нулевым значением, как правило исключаегся вектор с наибольшей стоимостью перевозок. 129 $5. Транспортная задача 5.5. Примеры транспортных задач Пример 1. 2хн + 2х и + 4хы + 8Х!4 + 4хп + 5хы + 7хм + бхз« + +без!+Зхзз+4хзз+9хз« пнп; х!! + Хз! + хз! < 22, х!2+ х22+ х32 < 2, х!з + хзз + хзз < 17, Х!4+ Х24 + Х34 ч 11~ х!! +хо+ хо + х!4 =!4, Х2! + Х22 + Х23 + Х24 = 18, хз! + хм + хзз + хз! —— 16, ХО >О, 4=1,2,3, 7'=1,2,3,4. Решение. Поскольку суммарные запасы груза на всех пунктах отправления меньше суммарных запросов пунктов назначения, т.е.
3 4 2 о! = 48 < 2 , 'Ь; = 52, то надо привести задачу к замкнутой модели. 3=! 3=.! Введем фиктивный пункт отправления А« с требуемой величиной выво- 4 3 за ૠ— — 2 Ь вЂ” 2'а! = 4 и нулевыми стоимостями перевозок из этого 3=! 3=! пункта. Зададим транспортную задачу в виде платежной матрицы; Построим по метолу «Северо-западного угла» первоначальное распреде- ление: Для краткости в матрице плана перевозок не пишем нулевые значения небазисных перевозок. Значение функционала равно 225. Число ненулевых элементов в первоначальном плане перевозок из+и-1 = 4+4-! = 7.
5 3*«, и! 131 4 5. 'Цаиспертиая задача !ЗО Глава 2. Линейное программирование Это позволяет сразу перейти к исследованию на оптимальность найден- ного плана. Построим матрицу С'. Ь34 — — пнп Ь;3 = -6 < О. Добавляя в первоначальный план распределегд ния на место нулевого небазисного элемента х34 величину 1, получим второй план возможных перевозок Величина ! = 7. Значение функционала = 183.
Построим матрицу С: 4Ъ~3 аа33 — ) 343 — Пцн аа33' = — ! < О. ВО МНОжЕСтВО баЗИСНЫХ ЭЛЕМЕНТОВ °,/ включим элемент хо с наименьшей стоимостью перевозок. Добавляя в первоначальный план распределения на место нулевого небазисного элемента х43 величину 1, получим третий план возможных перевозок: ' В матроне С баанснмс аасмснтм бумм рмаеаать ноауашрнмм шрифтом.
0 — 0 В матрице га = С вЂ” С = 8 0 — 0 В матрице 4з = С вЂ” С = 5 2 — 2 0 0 -6 минимальный элемент 7 5 0 — 1 — 1 4'~ 0 0 0 минимальные элементы 1 — 1 0 Величина ! = 1. Значение функционала = 182. Построим матрицу С: ~0 — 1 0 4~ — 0 0 1 0 В матрице Ь = С вЂ” С = 4 0 0 5 минимальный элемент 2 1 0 0 Ь13 = ПЦП 43Ч = — 1 < О. Добавляя в первоначальный план распределения ьу на место нулевого небазисного элемента хм величину 1, получим четвертый план возможных перевозок Величина 1 = 2. Значение функционала = 180. Построим матрицу С: 0 0 0 4 Поскольку 43 = с — с = 4 1 0 5 > О, то найденный четвер™й — 0 1 1 0 2 2 0 0 план перевозок является оптимальным и суммарная стоимость 180. !ЗЗ б 5. ТРаиспаргиая задача 132 Глава 2.
Линейное программирование Пример 2. хи + 2хн+ Зхы+4хм+ 4хг~ + Зхп+ 2згг+ 2хгг+ 2хгг+ хга пнп; х~~ + хи + хг~ = 2, хи + я,г+ хц+х1а м 3, + + — 3, х1г + хгг + хгг = хп+хп+хгг+хга =4, + + =4 х~з + хгз + хзг = хг1 + хзг+ хгз+ хга = 5 + +х =3 хм + хга + хм = х; >О, г=1,2,3, г=1,2,3,4. Решение. Поскольку суммарные запасы отправителей равны суммар- г а ным запросам потребителей, т.е. ',г„а; = 2 Ь, = 12, то данная задача ~=! г=! является замкнутой моделью транспортной задачи. Зададим задачу виде платежной матрицы: Построим по метолу «Северо-западного угла* первоначальное распреле- ление: Для краткости в матрице плана перевозок не пишем нулевые значения небазисных перевозок. Значение функционала равно 21.
Число ненулевых элементов в первоначальном плане перевозок гп+и — 1 = 3+4 — 1 = б Это позволяет сразу перейти к исследованию на оптимальность найденного плана. Построим матрицу С: (О 0 2 4~ В матрице г3 = С вЂ” С = ~ 2 0 0 — 1~ минимальный элемент — 2 — 1 0 0 ахи = ппп ггаг = -2 < О. Добавляя в первоначальный план распределения ад на место нулевого небазисного элемента хг~ величину 1, получим второй план возможных перевозок Величина ! = 2. Из трех обнулившнхся базисных элементов в базисе оставили два элемента с наименьшими стоимостями перевозок. Значение функционала равно 17. Построим матрицу С: /О 0 0 2а! В матрице аз = С вЂ” С = ~ 4 2 0 — 1~ минимальный элемент 0 1 0 0 Ьга = т!и гзгг = — 1 < О. Добавляя в первоначальный план распреде'.г ления на место нулевого небазисного элемента хга величину 1, получим третий план возможных перевозок Величина ! = 3. Значение функционала = 14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
