Беклемишев - Дополнительные главы линейной алгебры (947281), страница 67

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 67)

Номер, на котором достигает минимума отношение — г~/д~ для отрицательных аг а определяет столбец, выводимый из базиса двойственной задачи. Соответствие, которое существует между базисами двойвтнеиной задачи и псевдобазисами исходной, позволяет описать пронеси решения двойственной задачи по симплекс-методу, не упоминая двойственную задачу и используя только термины, связанные с аю. ход~юй задачей. Получаемый в результате метод решения исходнпй задачи носит название двойственного симплекс-метода, Коуотах» опишем его.

З04 ГЛ, Ч, СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ Допустим, что мы уже построили некоторый псевдобазис. Первое, что мы должны сделать, зто проверить, не соответствует ли он решению. Для этого вычисляются х», 1 = 1, ..., т. Если они все неотрнцательны, решение получено. Пусть среди элементов х; столбца хт имеются отрицательные. Каждому из отрицательных элементов х« соответствует строка Ф» = = А,'и„. Если найдется такой отрицательный элемент х«, для которого Ф» ) О, то двойственная задача имеет неограниченную сверху т целевую функцию и неразрешима. Следовательно, в этом случае исходная задача неразрешима из-за несовместности ограничений. Допустим теперь, что предположение предыдущего абзаца не т выполнено, и в кахсдой строке «б» при отрицательном х, есть отрицательный элемент. Мы выводим из псевдобазиса столбец, соответствующий максимальному по модулю отрицательному элементу столбца х,.

Пусть его номер й. В соответствующей ему строке ат отыскиваем все отрицательные элементы, и для них составляем отношения — Л»/с(р Номер минимального нз этих отношений определяет столбец, вводимый в псевдобазпс. Это правило обеспечивает неотрицательность всех чисел с)с», соответствующих новому набору столбцов, и этот набор, таким образом, является псевдобазисом.

На этом шаг двойственного симплекс-метода заканчивается. Проблема построения начального псевдобазиса (или базиса для двойственной задачи), как и в прямом симплекс-методе, вообще говоря, вызывает затруднения. Двойственный симплекс-метод может оказаться предпочтительнее потому, что начальный базис для сопряженной задачи, может быть указан без затруднений. Однако возможно и обратное полохсение: для праман задачи начальный базис указать легче, чем для двойственной. К числу задач, в которых начальный базис двойственной задачи может быть легко указан, относятся так называемые задачи с верхними ограничениями.

В этих задачах переменные х» удовлетворяют не только условию неотрицательности, но и ограничениям вида х» ~ й». В задаче с верхними ограничениями при помощи переноса начал а координат приводится задача с двусторонними ограничениями вида сзс ( х» ~ р». Один общий метод построения начального базиса двойственной задачи основан на введении «лишних» верхних ограничений. Если В ограничениям исходной задачи добавить ограничения где М вЂ” число большее, чем самая большая компонента решения, то эти ограничения, очевидно, не повлияют на решение задачи, но превратят ее в задачу е верхними ограничениями.

Естественно, что величина М ие может быть уверенно указана перед началом решения, Поэтому расчеты организуются так, чтобы счнГать М $4 симилекс-метод больше любого числа, которое может встретиться в процессе расче- тов. Подробнее на этом вопросе мы останавливаться не будем. 9. Зацикливание. Вырожденной задачей линейного программи- рования мы назвали такую задачу, в которой хотя бы одной вер- шине многогранного множества допустимых точек, соответствует не один базис, а больше.

Это явление связано с обращением в нуль базисных переменных, илн, говоря геометрическим язьпсом, с тем, что через данную вершину проходит больше чем п гиперплоскостей, получаемых обращением ограничений задачи в равенства. Вырож- денную вершину мы можем рассматривать как две ~или больше) совпавшие вершины или как вершины, соединенные ребром ну- левой длины, Мы предполагали задачу невырожденной как прн рассмотрении прямого, так и при рассмотрении двойственного симплекс-метода.

Однако в действительности вырожденные задачи встречаются до- статочно часто. Например, если мы начинаем с базиса, составлен- ного из столбцов, соответствующих изолированным переменным (см. и. 7), и в столбце свободных членов имеется нулевой элемент, то одна из базисных переменных будет равна нулю, и задача— вырожденная. Таким образом, предположение о невырожденности задачи че- ресчур ограничительно. Посмотрим, какие затруднения может вы- звать невыполнение этого ограничения. Отличие от нуля базисных переменных само по себе, в сущности, не используется.

Затрудне- ние может вызвать то, что одной и той же вершине соответствуют несколько различных базисов. Проекция градиента целевой функ- ции на ребро нулевой длины не определена, но для определения столбца, выводимого из базиса, мы пользуемся не проекциями, а числами бг, вычисляемыми по формуле (15), которые определены в любом случае.

Поэтому, если новый базис соответствует старой ~ вершине, мы заметим это только в конце шага, найдя, что значение целевой функции не изменилось. Итак, по алгоритму симплекс-метода мы переходим к другому базису, но можем остаться в той же самой вершине, н после вы- полнения шага симплекс-метода значение целевой функции не умень- шится. Само по себе это еще не означает, что нахождение минимума нельзя довести до конца. Но может оказаться, что при действую- щем правиле выбора столбца, выводимого из базиса, н столбца, вводимого в базис, мы будем переходить от одного базиса, соот- ветствующего данной вершине, к другому и после ряда шагов вер- немся к тому базису, с которого начали.

Такое явление называется зацикливанием. Следует иметь в виду, что возникновение зацикливания свя- зано не с существом метода, а с второстепенным вопросом — пра- вилом выбора столбцов, вводимых в базис и выводимых из базиса. Это правило может быть усовершенствовано так, чтобы зациклива- ние не возникало. Следующий способ наиболее прост с точкц.зре- Зва гл ч. системы нее»ависта и линеяноя пгогехммиговхиия ния обоснования, но, возможно, приводит к длинной последовательности бесполезных вычислений.

Если появляются несколько переменных, каждая из которых может быть выведена из базиса, то эта переменная выбирается случайным образом. Так как среди переменных заведомо имеются такие, что выведение их из базиса даст базис, соответствующий другой вершине, после некоторого числа проб мы выведем одну из таких переменных. Имеются и более совершенные приемы»борьбы с зацикливанием», но мы не будем на них останавливаться. Заш.кливаиие, как в прямом, так и в двойственном симплекс-ме»оде, явление настолько редкое, что примеры задач, в которых возникало бы зацикливание, приходится специально изобретать. Тем пе менее с принципиальной возможностью зацикливания приходится считаться. $ 5.

Приложения линейного программирования 1. Транспортная задача. Из всего множества приложений линейного программирования мы сможем здесь познакомиться лишь с немногими. При сколь угодно строгом отборе этих немногих приложений начать следует, по-видимому, с так называемой транспортной задачи. Это одна из первых линейных оптимизационных моделей, которая была построена в !939 г., еще до появления линейного программирования как самостоятельной области науки. Для ее решения был предложен ряд способов, вошедших в число классических методов линейного программирования.

В простейшем варианте транспортная задача формулируется следующим образом. Рассматриваются т поставщиков какой-то продукции и и ее потребителей. Пусть поставщики имеют запасы продукции а„..., а, а потребители должны получить соответственно Ь„..., Ь„единиц этой продукции. Заданы затраты на перевозку единицы продукции от каждого поставщика к любому потребителю сц, 1 = 1, ..., и», 1 = 1, ..., л. При этих условиях требуется составить план перевозок, т. е. для всех пар ц указать количество продукции хц, перевозимое от 1-го поставщика к 1ьму потребителю.

При этом нужно самым экономным способом удовлетворить потребности всех потребителей и вывезти всю продукцию от поставщиков. Естественно, эти требования выполнимы только в том случае, когда РИ » ~ а» = ~; Ьг. с» ! Если это условие выполцено, транспортная задача называется сбалансированной. В общем случае задача легко приводится к сбалан.

сированной введением фиктивного поставщика или фиктивного потребителя. Все, требования к плану перевозок, включая подразумеваю- ЩУЮСЯ НЕОтРИЦатЕЛЬНОСт ЧИСЕЛ Хц„МОГУт 6Ытъ ЭавиеаНЫ И ВИ1ЗЗ 3 К ПРИЛОЖЕНИЯ ЛИНЕИНОГО ПРОГРАММИРОВАНИЯ 307 следующей задачи линейного программирования: а ~х~ ~ки=аь / ! ~ ', с,/х(/ -~ пп' и. (,( ", х,/=Ь/, (= ( к(/~ О, В задачу входит тп переменных и т + и ограничений-равенств. Форма записи задачи отличается от канонической только тем, что ограничения линейно зависимы. В существовании линейной зависимости легко убедиться: сумма равенств первой группы 'У, 'ху = ~х,", Ь, (,/ / та же самая, что и сумма равенств второй группы 5; к(/ = ~х~~ а, (.

/ (задача предполагается сбалансированной), Линейную зависимость уравнений не исключают, чтобы не нарушать симметрии. Обозначим буквой Т матрицу системы ограничений. Каждый из ее столбцов содержит две единицы и т + и — 2 нулей. Чтобы лучше представить себе строение этой матрицы, выпишем ее для случая т = 2, и = 3. Переменные и правые части ограничений на- писаны для идентификации столбцов и строк, хм хе( хн х„ 1 О О О Гн х( х„ 1 1 О О Т= 1 О О 1 О О О 1 ! 1 О 1 О О ! О О 1 О 1 О О 1 ь(.

ье ь Матрица имеет большие (по сравнению с т и и) размеры и специальный разреженный вид. Поэтому естественно постараться организовать расчеты так, чтобы не преобразовывать эту матрипу. Благодаря ее специальному строению это оказывается возможным. Докажем следующее замечательное свойство матрицы Т. П р е д л о ж е н и е 1.

Каждая невырожденная псдматрица матрицы Т перестановкой строк и столбцов может быть приведена к треугольному виду. Докажем сначала, что в невырожденной подматрице Т' матрицы Т обязательно найдется столбец, содержащий одну единицу. Действительно, если все строки подматрицы относятся к первой (нли все ко второй) группе строк матрицы Т, то каждый столбец Содержит" одну единицу. Если же в подматрице присутствуют Отроки нз равных групп, то сложим между собой страни 'йерйой 308 гл, ч.

Характеристики

Список файлов книги