Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике - файл n1.doc

приобрести
Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике
скачать (3829.5 kb.)
Доступные файлы (1):
n1.doc3830kb.10.09.2012 14:34скачать

n1.doc

1   ...   24   25   26   27   28   29   30   31   32

§ 8.5. Теорема о конечности симплекс-алгоритма



Во всех рассмотренных нами примерах на симплекс-метод дело обстояло очень благополучно в том смысле, что процесс после конечного числа шагов заканчивался либо нахождением оптимального решения, либо установлением того факта, что min f = -. Всегда ли будет так? Поскольку процесс останавливается при наступлении одного из случаев I или II из § 8.1, то поставленный вопрос равнозначен следующему: не может ли случиться, что, производя (по симплекс-методу) шаг за шагом вычисления, мы никогда не окажемся перед одним из случаев I или II? По этому поводу можно высказать следующие соображения.

Каждый шаг состоит в замене одного базиса Б другим Б', причем эта замена происходит таким образом, что значение целевой функции f (для базисного решения) не увеличивается.

Предположим теперь, что процесс продолжается без остановки, производя бесконечную последовательность базисов

для которых

Ввиду того что число всех возможных базисов конечно, в последовательности (8.35) некоторые базисы должны повторяться. Следовательно, должны встречаться цепочки

в которых начальное и конечное звенья совпадают. Такие цепочки называются циклами. Ясно, что тогда и

откуда следует в силу (8.36), что

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

Случаи зацикливания хотя и встречаются, но крайне редко. В литературе по линейному программированию имеется всего несколько примеров такого рода, но и те, как отмечают их авторы, построены не без труда. Как правило, можно несложным путем избежать зацикливания. Для этого следует в случае появления цикла изменить последовательность вычислений. Именно, в той симплекс-таблице, с которой начинается данный цикл (или в любой другой таблице этого цикла), нужно выбрать другой разрешающий элемент (разумеется, в тех столбцах, где такой выбор возможен).

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

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

Условимся считать вектор

положительным и записывать это как

если А ? 0 и первая из отличных от нуля координат вектора А положительна. Если даны два вектора:

то мы скажем, что вектор А больше, чем вектор В (или что вектор В меньше, чем вектор А), если разность А - В есть положительный вектор. Другими словами, А > В означает, что

или же

или же

Очевидно, для любых двух векторов А и В выполняется одно и только одно из соотношений

Далее, если А > В и В > С, то А > С.

Обратимся теперь непосредственно к доказательству теоремы.

Пусть дана задача линейного программирования, причем система ограничений с самого начала разрешена относительно некоторого базиса, скажем x1, х2,..., хr. Итак, дана система

и линейная функция

Как обычно, требуется среди неотрицательных решений системы найти такое, которое минимизирует функцию f.

Исходным данным нашей задачи соответствует некоторая симплекс-таблица. Составим эту таблицу, а затем припишем к ней справа еще r столбцов:

(приписанная часть здесь заключена в пунктирную рамку). Числа cij и cj (i,j = 1,2,..., r) могут выбираться как угодно, но с одним условием: матрица ( cij) должна быть невырожденной.

Условимся называть базис положительным, если все векторы

положительны в указанном ранее смысле. Разумеется, если все свободные члены bi положительны, то базис будет положительным независимо оттого, какие числа стоят в приписанной части таблицы. Однако если какое-либо из чисел bi равно нулю, то условие положительности базиса накладывает некоторое ограничение на числа ci1, ci2, …, cir: первое отличие от нуля среди них должно быть положительным. Таким образом, свойство базиса быть положительным может зависеть не только от самой системы ограничений (8.37), но и от приписанных чисел cij.

Решение задачи по симплекс-методу сводится к последовательным заменам базиса. При этом над строками симплекс-таблицы производятся определенные действия. Условимся всякий раз, когда совершается какое-либо преобразование над строками симплекс-таблицы, выполнять то же самое преобразование и над приписанной к таблице частью.

Очередной шаг симплекс-метода начинается с выбора разрешающего элемента. Напомним, как производится этот выбор. Мы находим среди чисел ?r+1, ..., ?n последней строки положительное число ?j, после чего просматриваем все числа a1j , а2j, ..., arj столбца хj. Для каждого положительного аkj составляем отношение и затем среди этих отношений выбираем наименьшее, допустим . Тогда элемент aij и будет разрешающим. Если минимум отношения достигается сразу при нескольких значениях k, то в качестве i мы берем любое из этих значений. Возможность подобного выбора вносит в расчеты некоторый элемент произвола. Теперь мы устраним этот произвол и условимся выбирать разрешающий элемент в соответствии со следующим правилом: сравниваются векторы Сk для всех положительных akj и берется наименьший из них. Допустим, что наименьшим является Ci. Тогда в качестве разрешающего элемента берется aij. Нетрудно понять, что этим правилом выбор разрешающего элемента определен однозначно. Действительно, среда векторов С1, ..., Сr не может быть равных — в противном случае две строки матрицы (cij) оказались бы пропорциональными, что противоречит невырожденности этой матрицы.

Введем в рассмотрение еще один вектор

После очередного шага симплекс-метода числа, стоящие в приписанной части таблицы, конечно, изменяются; в частности, вектор С заменяется другим вектором С'. Докажем, что если исходный базис был положительным, то:

1) новый базис снова будет положительным;

2) новый вектор С' меньше, чем старый вектор С:

Из этих утверждений вытекает справедливость доказываемой нами теоремы. В самом деле, если вектор С с каждым шагом уменьшается, то это означает, в частности, что мы не можем (после скольких угодно шагов) вернуться к исходному базису. Тем самым зацикливание исключено, и процесс после конечного числа шагов должен закончиться отысканием оптимального решения.

Вспомним, как происходит преобразование симплекс-таблицы. Выбрав разрешающий элемент aij, мы умножаем i-ю строку таблицы на . Таким образом,

и так как aij > 0, Ci > 0, то С'i > 0. Из любой другой строки вычитается подходящее кратное i-й строки, подобранное с таким расчетом, чтобы элемент, стоящий в j-м столбце, обратился в нуль. В результате получим:

Если при этом аkj < 0, то Сi > 0 и С'i > 0. Если же akj > 0, то

Но в силу условия на выбор разрешающего элемента вектор, записанный в скобках, положителен: следовательно, С'k > 0. Это показывает, что новый базис является положительным. Наконец, заметим, что

Так как в данном случае ?j > 0, то мы получаем С' < С, что и требовалось доказать.

Чтобы завершить доказательство теоремы, нам остается ответить только на один вопрос: как обеспечить положительность исходного базиса? Но это совсем просто: достаточно, например, приписать к исходной симплекс-таблице справа следующие числа:

Здесь матрица (cij) — единичная, а все числа последней строки равны нулю. Теорема доказана.

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

Если не помнить этого обстоятельства, то можно прийти к курьезам. Один из таких случаев описан в литературе по линейному программированию и связан с рассмотренной нами ранее задачей о диете. Рассчитываемая диета должна была включать 77 видов пищи. Формулировка задачи в терминах линейного программирования включала 9 уравнений с 86 неизвестными, из которых 9 были дополнительными. Оптимальное решение, конечно, удовлетворяло всем требованиям задачи. Однако, поскольку симплекс-метод дает только базисное решение, оптимальная диета включала лишь 9 различных видов пищи (пшеничную муку, кукурузу, сгущенное молоко, растительное масло, сало, говяжью печень, капусту, картофель и шпинат). Ясно, что подобная диета не вполне отвечала бы требованиям вкуса и разнообразия пищи.

Правильная постановка задачи должна, разумеется, учитывать и такие требования.

1   ...   24   25   26   27   28   29   30   31   32


§ 8.5. Теорема о конечности симплекс-алгоритма
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации