«Brian D Bunday, B.Sc., Ph.D., F.S.S., F.I.M.A. School of Mathematical Sciences, University of Bradford Edward Arnold Б. Банди ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Перевод с английского О.В. Шихеевой Под редакцией В.А. ...»

Б. Банди

ОСНОВЫ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Basic Linear

Programming

Brian D Bunday,

B.Sc., Ph.D., F.S.S., F.I.M.A.

School of Mathematical Sciences, University of Bradford

Edward Arnold

Б. Банди

ОСНОВЫ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Перевод с английского О.В. Шихеевой

Под редакцией В.А. Волынского

МОСКВА «РАДИО И СВЯЗЬ» 1989 ББК 32.973 Б23 УДК 519.852 (420) Редакция переводной литературы Банди Б.

Б23 Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. - 176 с.: ил.

ISBN 5-256-00186-8.

В книге английского автора освещены основные положения и методы линейного программирования.

Рассмотрены симплекс-метод и его реализация на ЭВМ, проблема вырожденности, анализ чувствительности и двойственный симплекс-метод, транспортная задача, задача о назначении, двойственность в линейном программировании и др. Алгоритмы решения различных задач линейного программирования реализованы на языке Бейсик, причем программы несложно перевести на такие языки, как Фортран или Паскаль.

Для инженерно-технических работников, связанных с применением линейного программирования.

Б 1602011000-042 141.89 ББК 32. 046 (01)- Производственное издание

БАНДИ БРАЙАН

ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Заведующая редакцией О. В. Толкачева Редактор М. Г. Коробочкина Художественный редактор А. С. Широков Обложка художника В. Н. Забайрова Технический редактор О. А. Гришкина Корректор Г. Г. Казакова ИБ № Подписано в печать с оригинала-макета 11.01.89. Формат 60x88/16. Бумага Тип. № 2. Гарнитура "Пресс-роман". Печать офсетная. Усл. печ. л. 10,78.

Усл. кр.-отт. 11,52. Уч.-изд. л. 10,51. Тираж 50 000 экз. (1 завод: 1 - 25 000 экз.).

Изд. №22183. Заказ № 6622. Цена 70 к.

Издательство "Радио и связь". 101000 Москва, Почтамт, а/я Ордена Октябрьской Революции и ордена Трудового Красного Знамени МПО "Первая Образцовая типография имени А. А. Жданова" Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли.113054 Москва, Валовая, ©B D Bunday ©Перевод на русский язык, предисловие и примечания редактора перевода, ISBN 5-256-00186-8 (рус.) дополнительный список литературы.

ISBN 0-7131-3509-3 (англ.) Издательство "Радио и связь", Оглавление Предисловие редактора перевода

ДОПОЛНИТЕЛЬНЫЙ СПИСОК ЛИТЕРАТУРЫ

ПРЕДИСЛОВИЕ

ГЛАВА 1 ОСНОВНЫЕ ИДЕИ

1.1. ВВЕДЕНИЕ

1.2. ГРАФИЧЕСКОЕ РЕШЕНИЕ ДВУХМЕРНЫХ ЗАДАЧ

1.3. СТАНДАРТНАЯ ФОРМА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.............. 1.4. ОБОБЩЕНИЕ НА СЛУЧАЙ n ПЕРЕМЕННЫХ

1.5. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.6. УПРАЖНЕНИЯ

ГЛАВА 2. СИМПЛЕКС-МЕТОД

2.1. СИМПЛЕКС-МЕТОД ПРИ ЗАДАННОМ НАЧАЛЬНОМ ДОПУСТИМОМ

БАЗИСНОМ РЕШЕНИИ

2.2. РЕАЛИЗАЦИЯ СИМПЛЕКС-МЕТОДА НА ЭВМ

2.3. ПОРОЖДЕНИЕ НАЧАЛЬНОГО БАЗИСНОГО ДОПУСТИМОГО РЕШЕНИЯ........... 2.4. ПОЛНОЕ ИЗЛОЖЕНИЕ СИМПЛЕКС-МЕТОДА

2.5. ПРОБЛЕМЫ ВЫРОЖДЕНИЯ

2.6. УПРАЖНЕНИЯ

ГЛАВА 3 АНАЛИЗ УСТОЙЧИВОСТИ РЕШЕНИЯ

3.1. ОБРАЩЕНИЕ БАЗИСА И СИМПЛЕКС-МНОЖИТЕЛИ

3.2. ЧТО ПОЛУЧАЕТСЯ ПРИ ИЗМЕНЕНИИ ЗАДАЧИ

3.3. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

3.4. УПРАЖНЕНИЯ

ГЛАВА 4 ТРАНСПОРТНАЯ ЗАДАЧА

4.1. ПОСТАНОВКА ЗАДАЧИ И ЕЕ РЕШЕНИЕ

4.2. АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО УЛУЧШЕНИЯ ПЛАНА

4.3. ДИСБАЛАНС И ВЫРОЖДЕННОСТЬ В ТРАНСПОРТНОЙ ЗАДАЧЕ

4.4. ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ НА ЭВМ

4.5. УПРАЖНЕНИЯ

ГЛАВА 5 ЗАДАЧА О НАЗНАЧЕНИЯХ

5.1. ВВЕДЕНИЕ

5.2. МЕТОД РЕШЕНИЯ МАКА

5.3. РЕАЛИЗАЦИЯ МЕТОДА МАКА НА ЭВМ

5.4. УПРАЖНЕНИЯ

ГЛАВА 6 УЛУЧШЕННЫЙ СИМПЛЕКС-МЕТОД

6.1. УЛУЧШЕННЫЙ СИМПЛЕКС-АЛГОРИТМ

6.2. ИНИЦИАЛИЗАЦИЯ АЛГОРИТМА

6.3. ЕЩЕ РАЗ О ВЫРОЖДЕННОСТИ

6.5. УПРАЖНЕНИЯ

ГЛАВА 7. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

7.1. ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ

7.2. ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

7.3. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ С ТОЧКИ ЗРЕНИЯ ДВОЙСТВЕННОСТИ

7.4. УПРАЖНЕНИЯ

РЕКОМЕНДАЦИИ ДЛЯ ДАЛЬНЕЙШЕГО ЧТЕНИЯ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ОТВЕТЫ К УПРАЖНЕНИЯМ

Предисловие редактора перевода Линейное программирование как раздел исследования операций имеет почти сорокалетнюю историю. Внедрение вычислительной техники дало значительный толчок исследованиям в этой области математики. Был разработан ряд алгоритмов решения задач линейного программирования, а в последующие годы были созданы программы и пакеты программ преимущественно для больших ЭВМ. Основная масса литературы по линейному программированию в нашей стране выпущена в 60 - 70-е годы. Исследования в этой области (как теоретические, так и прикладные) продолжаются и в настоящее время. Однако книг по приложениям линейного программирования, учитывающих появление новых алгоритмических языков, а также микроЭВМ и персональных ЭВМ, практически нет.

Предлагаемая читателям книга восполнит этот пробел.

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

Отличительной особенностью книги является ее прикладной характер. Автор не только подробно описывает математический аппарат решения задачи, но и предлагает строгий алгоритм решения, а затем приводит программу на языке Бейсик с описанием ее особенностей. Такая форма изложения удобна и для обучения, и для получения справочного материала. Все более широкое распространение персональных ЭВМ, для которых основным языком программирования является Бейсик, будет способствовать росту интереса к программам, приведенным в книге.

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

ДОПОЛНИТЕЛЬНЫЙ СПИСОК ЛИТЕРАТУРЫ

1. Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование. Теория, методы и приложения. - М.: Наука, 1969. - 424 с.

2. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. - М.: Наука, 1976. - 191 с.

3. Булавский В. А.,Звягина Р. А., Яковлева М. А. Численные методы линейного программирования/ Под ред. Л. В. Канторовича. - М.: Наука, 1977. - 367 с.

4. Раскин Л. Г., Кириченко И. О. Многоиндексные задачи линейного программирования. Теория, методы, приложения. - М.: Радио и связь, 1982. - 239 с.

ПРЕДИСЛОВИЕ

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

Математическая теория в предлагаемой книге рассматривается вполне корректно, хотя имеются и более строгие изложения. Недостаточная строгость изложения компенсируется обилием примеров. Основная задача книги - показать, каким образом теоретические идеи воплощаются в практические вычислительные процедуры, реализуемые на ЭВМ. Появление основных теоретических идей совпало по времени с появлением компьютеров, и это не случайно1. Без компьютеров невозможно использовать весь потенциал теории при решении практических задач.

Программы в книге написаны на языке Бейсик (предполагается, что читатель с ним знаком), широко распространенном на большинстве микрокомпьютеров. На многих больших ЭВМ реализованы пакеты программ, основанные на методах, обсуждаемых в настоящей книге. Однако большие ЭВМ могут быть труднодоступны, а пакеты прикладных программ часто применяются вслепую. Интерактивный режим работы микрокомпьютеров позволяет студентам лучше понять, как работают программы. Не надо думать, что эти программы нельзя улучшить. Автор был бы рад получить от читателей соображения по улучшению программ. Предлагаемые программы просты и практичны. При желании можно применить их на других ЭВМ - они легко могут быть переведены на такие языки, как Фортран или Паскаль.

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

В операторах присваивания команда LET опускается. На некоторых компьютерах эта команда обязательна и должна быть вставлена. Команда THEN включена в операторы IF...

THEN GOTO, хотя на некоторых компьютерах команды THEN или GOTO могут быть опущены. Не использовались конструкции IF... THEN... ELSE и REPEAT... UNTIL......, поскольку они применимы не на всех компьютерах. Предполагается, что нумерация массивов начинается с 0. Если нумерация массивов ЭВМ начинается с 1, необходимы некоторые изменения. В любом случае достаточно увеличить на 1 аргументы всех операторов DIM. Например, вместо DIM А (М) будет DIM А (М + 1), вместо В (К, L) - В (К + 1, L + 1) и т. д. Может быть, читатели найдут более элегантные изменения. Приводимые численные результаты получены на ЭВМ PET. На некоторых ЭВМ, работающих с числами другой точности, результаты могут не воспроизводиться идентично, однако различия должны возникать лишь в последних, несущественных знаках.

Автор выражает благодарность друзьям, коллегам и студентам, внесшим вклад в эту книгу. Многие задачи были решены студентами на экзаменах университета г. Брэдфорда.

Автор признателен за разрешение их использовать. Особенно хотелось бы упомянуть доктора Р. И. Скратона, который помимо сделанных им улучшений в численном анализе позволил автору использовать в некоторых программах его форматирующие процедуры.

Автор благодарен К. Маку за полезные и содержательные беседы о его методе решения задачи назначения и подходах к программированию этого метода. В заключение автор Это утверждение ошибочно, так как идеи линейного программирования были разработаны еще до появления ЭВМ (см., например, Канторович Л. В. Математические методы в организации и планировании производства Л.: ЛГУ, 1939). - Прим. ред.

благодарит В. Хантер, превратившую беспорядочную рукопись в аккуратно перепечатанный текст.

Брайан Банди

ГЛАВА 1 ОСНОВНЫЕ ИДЕИ

1.1. ВВЕДЕНИЕ Методы линейного программирования оказались весьма эффективными для решения некоторых задач из области исследования операций. Слово "программирование" мы понимаем как планирование, и это определяет характер рассматриваемых приложений.

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

Пример Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки.

Для каждого изделия модели А требуется 3 м2 досок, а для изделия модели В - 4 м2. Фирма может получить от своих поставщиков до 1700 м2 досок в неделю. Для каждого изделия модели А требуется 12 мин машинного времени, а для изделия модели В - 30 мин. В неделю можно использовать 160 ч машинного времени.

Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В - 4 дол. прибыли?

Чтобы сформулировать эту задачу математически, обозначим через x 1 количество выпущенных за неделю полок модели А, а через x 2 - количество выпущенных полок модели В. Задача состоит в том, чтобы найти наилучшие значения x 1 и x 2. Очевидно, наилучшими для данной задачи являются такие значения, которые максимизируют еженедельную прибыль. Еженедельная прибыль Фирма будет получать максимальную еженедельную прибыль, если максимизирует целевую функцию P = 2 x 1 + 4 x 2.

Согласно классической теории оптимизации функция принимает экстремальные значения в точках, в которых обращаются в нуль ее производные, либо на границе области определения. Рассмотрения производных в нашем случае недостаточно, так как и никаким выбором x 1 и x 2 нельзя обратить эти производные в нуль. Действительно, чтобы увеличить функцию Р, надо увеличить x 1 и x 2. Но (и в этом суть проблемы) значения x 1 и x 2 не могут быть увеличены неограниченно. Эти значения ограничены, в частности, лимитами на сырье и машинное время.

Поскольку выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательны, т. е.

Теперь ограничения на наличие досок и машинное время могут быть записаны следующим образом:

Следовательно, задача состоит в том, чтобы найти значения x 1 и x 2, ограничениям типа неравенства (1.3) и Это типичная двухмерная задача линейного программирования. Целевая функция, которая должна быть максимизирована, является линейной Ограничения на эти переменные тоже линейны (они представлены на рис.

1.1). Условия неотрицательности рассмотрением положительного квадранта. Границы определяются прямыми Стрелка на каждой границе рис 1.1 указывает, с какой стороны прямой выполняется ограничение. Заштрихованная область ОАВС, содержащая точки, для которых соблюдены условия (1.2) и (1.3), называется допустимой. Точки внутри и на границе этой области изображают допустимые решения. Допустимых решений много. Задача состоит в том, чтобы найти решение (может ли их быть более одного?), максимизирующее функцию P.

Штриховыми линиями на рис. 1.1 изображены прямые 2 x 1 + 4 x 2 = 800, обозначенные a и b соответственно. Эти прямые параллельны и представляют собой две линии уровня функции P со значениями соответственно 0 и 800.

Ясно, что значение функции P возрастает по мере того, как линии уровня удаляются от начала координат в положительном квадранте. Действительно, вектор с компонентами,, т. е. вектор с компонентами перпендикулярен штриховым линиям и направлен в сторону, противоположную началу координат.

Линией уровня с наибольшим значением функции P, имеющей хотя бы одну общую точку с допустимой областью, является прямая c, проходящая через вершину B ; на ней P принимает значение 1400. Точка B, в которой x 1 = 300, x 2 = 200, соответствует оптимальному решению задачи. Эти значения могут быть получены как решения уравнений Следовательно, максимальная прибыль составляет 2 300 + 4 200 = 1400. При оптимальном решении оба ограничения превращаются в равенства, что означает полное использование сырья и машинного времени.

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

Общая задача линейного программирования состоит в максимизации (или минимизации) линейной функции от вещественных переменных неотрицательности и m линейным ограничениям Среди ограничений могут одновременно встречаться знаки, = и. Задача состоит в максимизации (минимизации) целевой функции. Значения b i, c j, a ij предполагаются известными. Часто мы будем (как в примере 1) приводить их конкретную интерпретацию в практических задачах.

В матричных обозначениях задача может быть представлена следующим образом:

максимизировать (минимизировать) функцию Индекс 0 в векторе x 0 и в матрице A0 указывает на то, что это начальные значения.

Смысл этого станет ясен в разд. 1.3.

1.2. ГРАФИЧЕСКОЕ РЕШЕНИЕ ДВУХМЕРНЫХ ЗАДАЧ

На примере, рассмотренном в предыдущем разделе, мы показали, каким образом задачи линейного программирования возникают на практике, и продемонстрировали графический метод их решения. Рассмотрев еще несколько примеров такого рода, достаточно простых, чтобы было "видно, что происходит", мы сможем выявить несколько общих свойств задач линейного программирования, которые могут подсказать путь к их общему решению.

Пример Минимизировать функцию при ограничениях x 1, x изображенной на рис. 1.2, является четырехугольник PQRS. Два последних ограничения усиливают условия неотрицательности. Функция z убывает в направлении вектора Минимальное значение функции z = – 68 и достигается в точке R = (12, 8). Заметим, что, как и в примере разд.

1.1, минимум достигается в вершине допустимой области. Оптимальным решением задачи является точках x 1 = 12, x 2 = 8 с минимальным значением функции z = – 68.

Иногда задача имеет более чем одно оптимальное решение.

Пример Минимизировать функцию z = 6x 1 2x при ограничениях На рис. 1.3 четырехугольник ОАВС изображает допустимую область = 2, и, таким образом, вектор указывает направление убывания функции z.

Любая точка на отрезке ВС является оптимальным решением. В частности, в вершинах В = оптимальные решения, соответствующие одному и тому же минимальному значению функции z = – 12.

представляется формулой Для каждой такой точки значение функции z равно минимальное значение.

Иногда решение задачи не ограничено.

Пример z = x1 + x при ограничениях x 1, x Допустимая область, изображенная на рис. 1.4, не ограничена в направлении, в котором функция z возрастает, т. е. в допустимой области не существует конечной точки, в которой функция z достигала бы максимума. Решение, как и максимальное значение функции задачи с неограниченными допустимыми областями имеют конечные решения. Например, задача максимизации функции z / = x 2 при ограничениях из примера 3 имеет конечное решение.

Разумеется, если бы задача состояла в минимизации функции z = x 1 + x 2 при тех же ограничениях, то минимум достигался бы в единственной точке z (min) = 1 в вершине допустимой области ( x 1 = 1, x 2 = 0).

Иногда задача не имеет решения, поскольку допустимой области не существует.

Пример Минимизировать функцию z = 2x 1 + 3x при ограничениях x 1, x 2 0, Ограничения задачи противоречивы, поэтому нет допустимых решений (рис. 1.5).

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

Эти результаты могут быть обобщены. Сначала покажем, что задачи линейного программирования могут быть приведены к стандартной форме.

1.3. СТАНДАРТНАЯ ФОРМА ЗАДАЧ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

На первый взгляд задачи линейного программирования представляются по-разному. Все они могут быть приведены к стандартной форме, в которой целевая функция должна быть минимизирована, а все ограничения должны быть заданы в виде равенств с неотрицательными переменными.

Привести задачу к стандартной форме очень просто, используя следующие правила:

а) Максимизация целевой функции минимизации целевой функции z / = c 1 x 1 c 2 x 2 K c n x n.

б) Ограничение в виде неравенств, например 3x 1 + 2x 2 x 3 6, может быть приведено к стандартной форме 3x 1 + 2x 2 x 3 + x 4 = 6, где новая переменная x 4 неотрицательна.

Ограничение x 1 x 2 + 3x 3 10 может быть приведено к стандартной форме x 1 x 2 + 3x 3 x 5 = 10, где новая переменная x 5 неотрицательна.

в) Если некоторая переменная x k может принимать любые значения, а требуется, чтобы она была неотрицательная, ее можно привести к виду x k = x /k x //, где x /k 0 и Таким образом, приведение задачи к стандартной форме может потребовать введения дополнительных переменных (по-прежнему неотрицательных).

Аналогично соотношениям (1.7), (1.8), (1.9) выразим наиболее общую задачу линейного программирования в следующем виде:

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

Так. пример 1 разд. 1.2 может быть приведен к следующему виду:

Пример 1 разд 1.1 может быть приведен к следующему виду:

В матричной форме ограничения можно записать таким образом:

Они состоят из двух уравнений с четырьмя неизвестными. Любое неотрицательное решение при этих ограничениях является допустимым решением.

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

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

приведенную таблицу).

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

Оптимальному решению задачи будет соответствовать вершина этого многогранника, поскольку поверхностями уровня целевой функции будут плоскости вместо прямых, а плоскость, соответствующая наименьшему значению, имеет, вообще говоря, только одну общую точку с допустимой областью; эта точка и будет вершиной выпуклого многогранника, соответствующей оптимальному решению задачи.

Мы увидим, что этот результат закономерен. Базисные решения системы m уравнений с n неизвестными соответствуют вершинам допустимой области; оптимальное решение (если оно существует) соответствует базисному допустимому решению и, следовательно, является вершиной допустимой области.

1.4. ОБОБЩЕНИЕ НА СЛУЧАЙ n ПЕРЕМЕННЫХ Прежде чем получить упомянутые выше результаты, необходимо обобщить некоторые геометрические понятия.

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

1.2. Однако в n -мерном пространстве наглядно представить себе ситуацию очень трудно.

Для решения геометрических задач в этом случае необходимы алгебраические методы.

Прежде чем определить выпуклое множество, введем несколько терминов. Для обозначения точки n -мерного пространства будем использовать символ Отрезок PQ, где P и Q - две точки, представленные векторами p и q, состоит из точек, определяемых соотношением Точечное множество S называется выпуклым, если для любых точек P и Q этого множества весь отрезок PQ содержится в множестве S.

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

Выпуклой оболочкой точек P1, P2, K, Pk, представленных векторами p 1, p 2, K, p k, называется множество точек вида На рис. 1.6, а изображено выпуклое множество. Множество, изображенное на рис.

1.6, б не является выпуклым – некоторые точки отрезка VW не принадлежат ему. Точки точек P 1 P 2 есть отрезок P 1 P 2. Выпуклая оболочка трех точек – треугольник P 1 P 2 P 3, четырех – тетраэдр P 1 P 2 P 3 P 4, а пяти точек - гипермногогранник с вершинами в этих пяти точках.

1.5. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Общая задача линейного программирования в стандартной форме записывается следующим образом:

Ограничения можно задать в виде Ax = b, x 0, где матрица A имеет ранг m ( < n).

Теперь докажем следующие основные утверждения линейного программирования.

Утверждение 1. Если ограничения имеют допустимое решение, то они имеют и базисное решение.

Докажем это, построив базисное допустимое решение. Пусть в допустимом решении n r переменных равны 0, а остальные положительны. Тогда без потери общности а a j - столбцы матрицы A.

Если a j - линейно независимы, то r m - ранг матрицы A и решение является базисным допустимым решением ( m r базисных переменных равны 0).

Если a 1, a 2, K, a r линейно зависимы, то (при необходимости это равенство может быть умножено на -1).

тогда Если выбрать k так, что то значения неотрицательны и поэтому являются допустимыми решениями, в которых по крайней мере r 1 переменная имеет строго положительное значение. Следовательно, количество строго положительных переменных уменьшено на одну переменную. Продолжая рассуждения таким же образом, в конце концов придем к ситуации, при которой r m, т.e.

получим базисное допустимое решение.

Утверждение 2. Допустимая область является выпуклым множеством.

Если x и y принадлежат допустимой области и A x = b, A y = b, причем x 0, y 0, тогда, если Следовательно, Таким образом, w принадлежит допустимой области, значит, доказано, что допустимая область является выпуклым множеством.

Утверждение 3. Базисные допустимые решения соответствуют вершинам выпуклого множества последние n m координат вектора x равны 0.

A u = b, A v = b, u, v 0. Таким образом, для последних n m координат имеем имеет решение только в случае uj = v j = 0, где j = m + 1, K, n.

Таким образом, u, v - базисные допустимые решения, обращающиеся в 0 в тех же точках, что и x 0. Поэтому из единственности решения x 0 следует, что x 0 = u = v, что противоречит выбору u и v. Поэтому каждое базисное допустимое решение - вершина.

Можно доказать и обратное, т. е. что все вершины соответствуют: базисным допустимым решениям.

Пусть x 0 - вершина допустимой области. Пусть r координат x 0 строго положительны.

r не превосходит m, т. е. x 0 - базисное допустимое решение. Пусть Покажем, что x 0, x 0, K, x 0 ( r > m ) положительны. Пусть a 1, a 2, K, a r - соответствующие столбцы матрицы A ; предположим, что они линейно зависимы.

Как и при доказательстве утверждения 1, найдем такие j, не все равные 0, что Легко видеть, что если то векторы удовлетворяют условию x 1 0, x 2 0.

Поскольку A = 0, то Аналогично A x 2 = b.

x 0 - не вершина, а это противоречит выбору x 0, значит, r не превосходит m.

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

Утверждение 4. Если целевая функция имеет конечный минимум, то, по крайней мере, одно оптимальное решение является базисным.

Пусть допустимые базисные решения соответствуют точкам P 1, P 2, K, P k векторов p 1, p 2, K, p k, и пусть целевая функция принимает в этих точках значения любой другой точки в допустимой области значение функции z в этой точке Таким образом, нахождение в выпуклой оболочке точек P 1, P 2, K, P k точки x, в которой функция z удовлетворяющих условию 1 = 1 и минимизирующих функцию z.

Среди значений z 1, z 2, K, z k имеется минимальное (их может быть несколько). Пусть z j такое значение, т. е. z j z i для i = 1, 2, K, k.

Величина i z i, являющаяся взвешенной средней величин z 1, z 2, K, z k, с весами функции z достигается в вершине P j.

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

1.6. УПРАЖНЕНИЯ 1. Фирма производит два продукта А и В, рынок сбыта которых неограничен. Каждый продукт должен быть обработан каждой из машин I, II, III. Время обработки в часах для каждого из изделий А и В приведено ниже:

I II III

Время работы машин I, II, III соответственно 40, 36 и 36 ч в неделю. Прибыль от изделий А и В составляет соответственно 5 и 3 дол.

Фирме надо определить недельные нормы выпуска изделий А и В, максимизирующие прибыль. Сформулируйте эту задачу как задачу линейного программирования и решите ее.

2. Максимизируйте функцию w = x 1 + 2x при ограничениях x 1 0, x 2 0, 3. Приведите задачу 2 к стандартной форме. Покажите, что она имеет 15 базисных решений, 5 из которых допустимы. Поставьте эти решения в соответствие вершинам допустимой области.

4. Минимизируйте функцию z = 2x 1 x при ограничениях x 1 0, x 2 0, 5. Минимизируйте функцию z = 3x 1 x при ограничениях x 1 0, x 2 0, в случаях 6. Минимизируйте функцию z = x 1 5x 7. Максимизируйте функцию 3x 1 + 6x 2 + 2x Покажите, что допустимая область этой трехмерной задачи является выпуклым многогранником, и что оптимальное решение достигается в вершине.

8. Фирме требуется уголь с содержанием фосфора не более 0,03 % и с долей зольных примесей не более 3,25 %. Три сорта угля А, В, С доступны по следующим ценам (за 1 т):

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

9. Средства очистки пола оценивают по следующим трем показателям: а) очищающие свойства, б) дезинфицирующие свойства, в) раздражающее воздействие на кожу. Каждый из этих показателей измеряется по линейной шкале от 0 до 100 единиц.

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

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

10. Фирма производит два продукта А и В, продаваемых соответственно по 8 и по центов за упаковку; рынок сбыта для каждого из них практически неограничен. Продукт А обрабатывается на машине 1, продукт В - на машине 2. Затем оба упаковываются на фабрике:

1кг сырья стоит 6 центов: машина 1 обрабатывает 5000 кг в 1 ч с потерями 10%. Машина обрабатывает 4000 кг в 1 ч и с потерями 20 %. Машина 1 доступна 6 ч. в день, ее использование стоит 288 дол. в 1 ч. Машина 2 доступна 5 ч в день, ее использование стоит 336 дол в 1 ч. Упаковка продукта А весит 1/4 кг, а упаковка продукта В - 1/3 кг. Фабрика может работать 10 ч в день, производя в 1 ч продукцию стоимостью 360 дол. За 1 ч можно упаковать 12000 продуктов А и 8000 продуктов В.

Компания хочет определить такие значения x 1 и x 2 потребления сырья для продуктов А и В (в тысячах килограммов), при которых дневная прибыль максимальна. Сформулируйте задачу как задачу линейного программирования и вычислите оптимальное решение графически.

11. Приведите двухмерные задачи из примеров разд. 1.2 к стандартной форме. Найдите все базисные решения и покажите, что допустимые базисные решения могут быть сопоставлены с вершинами допустимой области.

12. В некоторой местности в двух пунктах А и В имеется потребность в дополнительном транспорте. В пункте А требуется 5 дополнительных автобусов, а в пункте В - 7. Известно, что 3, 4 и 5 автобусов могут быть получены соответственно из гаражей G 1, G 2 и G 3.

Как следует распределить эти автобусы между пунктами А и В, чтобы минимизировать их суммарный пробег? Расстояния от гаражей до пунктов А и В приведены в таблице.

13. Компания производит полки для ванных комнат двух размеров - А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется м2 материала, а для полки типа В - 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется мин машинного времени, а для изготовления одной полки типа В - 30 мин; ЭВМ можно использовать 160 ч в неделю. Если прибыль от продажи полок типа А составляет 3 дол., а от полок типа В – 4 дол., то сколько полок каждого типа следует выпускать в неделю?

14. Автозавод выпускает две модели: «Каприз» и (более дешевую) «Фиаско». На заводе работает 1000 неквалифицированных и 800 квалифицированных рабочих, каждому из которых оплачивается 40 ч в неделю. Для изготовления модели "Каприз" требуется 30 ч неквалифицированного и 50 ч квалифицированного труда; для "Фиаско" требуется 40 ч неквалифицированного и 20 ч квалифицированного труда. Каждая модель "Фиаско" требует затрат в размере 500 дол. на сырье и комплектующие изделия, тогда как каждая модель "Каприз" требует затрат в размере 1500 дол.; суммарные затраты не должны превосходить 900 000 дол. в неделю. Рабочие, осуществляющие доставку, работают по пять дней в неделю и могут забрать с завода не более 210 машин в день. I Каждая модель "Каприз" приносит фирме 1000 дол. прибыли, а каждая модели "Фиаско" дол. прибыли. Какой объем выпуска каждой модели Вы бы порекомендовали? Что бы Вы порекомендовали для повышения прибыли фирмы?

15. Заводы фирмы расположены в городах Лидсе и Кардиффе; они доставляют товары на склады городов Манчестер, Бирмингем и Лондон. Расстояния между этими городами приведены в таблице (расстояния округлены до десятков миль) :

а) Завод в г. Лидсе выпускает в год 800 т товаров, а в г. Кардиффе - 500 т.

Манчестерский склад вмещает 400 т, бирмингемский - 600 т, а лондонский - 300 т. Как следует транспортировать товары для минимизации цен на перевозки?

б) На дороге Лондон - Кардифф ведутся работы, удваивающие стоимость перевозок по ней. Как бы Вы пересмотрели расписание?

ГЛАВА 2. СИМПЛЕКС-МЕТОД

2.1. СИМПЛЕКС-МЕТОД ПРИ ЗАДАННОМ НАЧАЛЬНОМ

ДОПУСТИМОМ БАЗИСНОМ РЕШЕНИИ

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

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

Базисное решение, удовлетворяющее ограничениям, можно получить, если найти m столбцов матрицы A, образующих несингулярную матрицу B m n. Если эти столбцы соответствуют переменным x 1, x 2, K, x m, то ограничения могут быть преобразованы так, чтобы выразить x 1, x 2, K, x m через b и остальные x, что можно записать в виде x 1, x 2, K, x m исключатся из z и мы получим Разумеется, уравнения (2.4) и (2.3) выражают одинаковые ограничения, а уравнения (2.5) и (2.1) представляют одну и ту же целевую функцию, хотя и в разных алгебраических формах. Уравнения (2.4) и (2.5) являются канонической формой для базиса x 1, x 2, K, x m. Если положить x m + 1, x m + 2, K, x n равными 0, то соотношения задают базисное решение. Если все b /i > 0, это решение допустимо. Среди таких решений надо найти оптимальное. Симплекс-метод обеспечивает систематическую процедуру для такой замены одной допустимой канонической формы на другую, при которой значение целевой функции уменьшается.

Отметим, что если матрица A может быть разбита следующим образом:

размерностью m n m (остаток матрицы A ), умножение уравнения (2.3) на B приводит к уравнению (2.4). Для базисного допустимого решения должна существовать матрица B 1.

Для системы уравнений (2.3) из соотношения следует соотношение Имеем также где c T = ( c 1, c 2, K, c m) - вектор-строка коэффициентов базисных переменных в исходном виде для функции z (см. уравнение (2.1)).

Для нахождения базисного допустимого решения такой метод весьма неэффективен.

Иногда базисное допустимое решение очевидно, как в выбранном для иллюстрации симплекс-метода примере 1 из разд. 1.1, который уже решен графически.

Пример Минимизировать функцию 2x 1 4x 2 = z при ограничениях x 1 0, x 2 0, В стандартной форме с неотрицательными дополнительными переменными x 3 и x ограничения и целевая функция принимают вид Поскольку в этом случае коэффициенты b положительны, а новые переменные имеют коэффициент +1, ясно, что набор x 1 = x 2 = 0, x 3 = 1700, x 4 = 1600 образует базисное фундаментальное решение, а уравнения (2.11) имеют соответствующий вид.

Функция z, имеющая нулевое значение, выражена через небазисные переменные, которые также имеют нулевое значение. Как в таком случае можно уменьшить значение функции z ? Поскольку x 1 и x 2 должны быть неотрицательны, любое изменение их значений является увеличением этих значений. Поскольку коэффициенты при x 1 и x 2 в канонической форме функции z отрицательны, любое такое изменение приведет к убыванию функции z. Вместо того чтобы увеличить их значения одновременно, для простоты выберем одну из переменных. Так как коэффициент при x 2 больше по модулю, выбираем x 2.

Однако при увеличении x 2 значения x 3 и x 4 будут изменяться, поскольку должны выполняться уравнения (2.11). Все переменные при этом должны оставаться неотрицательными. Таким образом, должен существовать предел увеличения x 2.

Поскольку 3x 1 + 4x 2 + x 3 = 1700, x 3 обращается в 0 при x 2 = 1700/4 = 425.

Поскольку 2x 1 + 5x 2 + x 4 = 1600, x 4 обращается в 0 при x 2 = 1600/5 = = 320.

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

Второе ограничение может быть записано в виде Если вычесть это уравнение, умноженное на 4, из уравнения (2.11) (4 - коэффициент при x 2 в этом уравнении), а затем вычесть это же уравнение, умноженное на - 4, из выражения для целевой функции (- 4 - коэффициент при x 2 в целевой функции), то переменная x будет исключена отовсюду, кроме второго ограничения, куда она входит с коэффициентом 1.

Ограничения и целевая функция принимают вид что является канонической формой для базиса x 2, x 3, представляющего базисное допустимое решение.

Небазисными переменными стали переменные x 1 и x 4. В данный момент они равны 0.

Теперь можно уменьшить значение функции z, увеличив только x 1. Но на сколько можно увеличить x 1, чтобы x 2 и x 3 оставались неотрицательными?

Для уравнения Для уравнения Таким образом, нельзя увеличивать x 1, более чем до 300 (минимального из этих значений). После деления на 7/5 (коэффициент при x 1 ) первое ограничение принимает вид Исключим x 1 из другого ограничения и выражения для целевой функции, вычтя последнее соотношение, умноженное на 2/5 и -2/5, из ограничения и целевой функции.

Получим каноническую форму задачи в базисе x 1, x 2, тоже являющимся допустимым. Она имеет следующий вид:

Заметим, что увеличение любой из небазисных переменных x 3, x 4 (эти переменные входят в выражение для целевой функции z с положительными коэффициентами) приведет к возрастанию функции z. Таким образом, дальнейшее убывание функции z невозможно и достигнуто минимальное значение функции z, равное -1440 при допустимом базисном решении x 1 = 300, x 2 = 200, x 3 = x 4 = 0. Если вернуться к геометрической интерпретации на рис.. 1.1, то можно убедиться, что последовательность канонических форм привела из точки 0 в точку A и из точки A в точку B - точку минимума. Читателю рекомендуется проверить, что при выборе в уравнениях (2.11) увеличения x 1 та же процедура привела бы из точки 0 в точку B через точку C.

Этот итерационный процесс удобно проиллюстрировать в так называемых симплекстаблицах. Они состоят из уравнений (2.11) - (2.13) для ограничений и целевой функции, записанных в виде Ниже приведены три таблицы.

На итерации 0 звездочкой отмечено значение 5 - коэффициент при переменной, которую мы собираемся обратить в базисную в предельном ограничении. На итерации 1 отмечено число 7/5. Заметим также, что мы ставим точки вместо переменных, обязанных иметь нулевые значения, чтобы отличить их от переменных, обращающихся в 0 случайно.

Результаты, полученные в рассмотренном примере, можно обобщить. Предположим, что начальная каноническая форма задана, и что на k -й итерации получена каноническая форма, заданная уравнениями (2.4) и (2.5), запись которых приведена ниже в таблице.

Итерационный процесс состоит из трех шагов.

1. Найти переменную для включения в базис.

коэффициентов c m +1, K, c s, K, c /n. Пусть это коэффициент c /s. Если коэффициент c /s отрицателен, то увеличение x s приведет к убыванию функции z. В связи с этим принимается соглашение, что если некоторые коэффициенты c /j - отрицательны, то из них следует выбрать наибольший по модулю коэффициент. Это разумно, но несущественно, поскольку подходит любое отрицательное значение c /j. Если все c /s 0, то значение функции z не может быть уменьшено, и минимум найден.

2. Найти переменную для исключения из базиса.

Насколько можно увеличивать x s, не нарушая условия неотрицательности текущих базисных переменных? Если в i -м ограничении a /is > 0, то наибольшее значение, которое отрицательна. (Если a 0, то при увеличении x s базисная переменная x i возрастать.) Таким образом x s может увеличиваться до значения Если этот минимум достигается в строке r, то x r обращается в 0, когда x s принимает значение b /r / a /rs. Другие базисные переменные останутся неотрицательными. Элемент a /rs называется ведущим2 элементом, строка r - ведущей строкой, а столбец s - ведущим столбцом.

3. Построить новую каноническую форму.

Теперь новый базис x 1, x 2, K, x s, K, x m; x r и переменная x r стала базисной.

Чтобы построить новую каноническую форму, коэффициент при x s в ведущей строке сделаем равным 1, поделив строку на a /rs, чтобы образовать новую ведущую строку.

Используется также термин "разрешающий". - Прим. ред. Затем удалим x s из других ограничений целевой функции. Для этого из i -строки ( i r ) с коэффициентом a /is при x s вычтем преобразовать целевую функцию с коэффициентом c /s (< 0) при x s, вычтем c /s (новая ведущая строка) из строки соответствующей целевой функции.

На очередной итерации каноническая форма будет выглядеть следующим образом:

где Формулы (2.15) - (2.20) запоминать не надо; они приведены здесь для дальнейших ссылок.

Вычисления удобнее выполнять в соответствии с шагом 3.

Теперь, построив новую каноническую форму, необходимо вернуться к шагу 1 и выбрать минимальное из чисел с +. В конце концов мы обнаружим, что все они положительны; это и будет означать, что минимум функции z достигнут.

Пример Минимизировать функцию 6x 1 2x 2 = z Это - пример 2 разд. 1.2, представленный в стандартной форме.

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

На итерации 1 коэффициенты при небазисных переменных неотрицательны. Сравнение с рис. 1.3 показывает, что мы передвинулись из точки 0 в точку С. Оптимум найден в точке С, в которой x 1 = 2, x 3 - 5, x 2 = x 4 =0, с минимальным значением функции z, равным -12.

Нулевой коэффициент при x 2 в выражении для функции показывает, что можно было бы увеличить x 2. Такое увеличение не привело бы ни к возрастанию функции, ни к убыванию.

Это случай, когда имеется более чем одно оптимальное решение.

Полученные в результате каноническая форма и соответствующая таблица (ведущий элемент отмечен звездочкой) приведены ниже.

Эта таблица оптимальных решений соответствует точке В на рис. 1.3. Видно, к чему приводит многочисленность оптимальных точек, найденных в процедуре: она приводит к наличию нулевых коэффициентов в канонической форме оптимального решения для функции z.

Пример Минимизировать функцию x 1 x 2 = z Ясно, что точка x 1 = 1, x 4 = 2, x 2 = x 3 = 0 является базисным решением и что ограничения приведены в соответствующем виде, так что метод применим. Целевая функция содержит одну из базисных переменных x 1. Пользуясь первым ограничением, можно исключить x 1 и получить 2x 2 x 3 = z + 1.

Эта задача - пример 3 разд. 1.2. Приведем первую таблицу, соответствующую точке А на рис. 1.4:

Здесь приведена также вторая таблица, вычисленная обычным образом. Она соответствует точке В на рис. 1.4. Функция z может быть еще уменьшена увеличением x 3. Но здесь возникает определенная трудность. В столбце, соответствующем x 3, в ограничениях нет строго положительных коэффициентов. Таким образом, сколько не увеличивай x 3, базисная переменная никогда не обратится в 0. Действительно, x 1 будет увеличиваться, а x 2 оставаться неизменным. Это случай неограниченного решения (см. рис. 1.4). В симплексметоде неограниченность решения выражается в том, что все коэффициенты a /is 0.

2.2. РЕАЛИЗАЦИЯ СИМПЛЕКС-МЕТОДА НА ЭВМ Вычислительная процедура симплексметода является итерационным процессом.

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

Симплекс-метод - это метод для ЭВМ. Не случайно развитие теории линейного программирования совпало по времени с развитием ЭВМ. Без них теория имела бы весьма узкую область приложений.

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

основном из трех шагов. Сначала находим min c /j = c /s ( < 0 ), чтобы определить переменную для включения в базис. Затем строка базисной переменной для удаления из базиса находится по формуле Конечно, этот результат совпадает с выражением (2.14). В конце концов, приходим к следующей канонической форме в соответствии с уравнениями (2.15) - (2.20).

Текст программы соответствует блок-схеме, приведенной на рис. 2.1; в программе используются те же обозначения, что и в тексте. Значения переменных и целевой функции ( b /i и z /0) запоминаются в нулевом столбце матрицы А. Последняя строка этой матрицы используется для коэффициентов целевой функции. Данные в строках 4000 - соответствуют данным примера 1 разд. 2.1.

10 REM В ПРОГРАММЕ РЕАЛИЗОВАН СИМПЛЕКС-МЕТОД С ЗАДАННЫМ

15 REM БАЗИСНЫМ ДОПУСТИМЫМ РЕШЕНИЕМ ДЛЯ ОГРАНИЧЕНИЙ

20 REM ВВЕСТИ КОЛИЧЕСТВО ОГРАНИЧЕНИЙ И ПЕРЕМЕННЬК

30 READ M,N 40 М1=М+ 50 DIM A(M1,N),BS(M),NB(N),V(M1)

60 PRINT “ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ”

100 REM ВВЕСТИ КОЭФФИЦИЕНТЫ ДЛЯ ОГРАНИЧЕНИЙ И ЦЕЛЕВОЙ

105 REM ФУНКЦИИ ПОСТРОЧНО 110 FOR I=1 ТО M1:FOR J=l ТО N 120 READ A(I,J) 130 NEXT J:NEXT I

150 REM ВВЕСТИ НАЧАЛЬНЬЕ ЗНАЧЕНИЯ БАЗИСНЫХ ПЕРЕМЕННЫХ И

155 REM ЦЕЛЕВОЙ ФУНКЦИИ В МАССИВ А(1,0) 160 FOR I=1 ТО M1:READ A(I,0):NEXT I

200 REM ВВЕСТИ БАЗИСНЬЕ ПЕРЕМЕННЫЕ;BS - МЕТКА БАЗИСНОЙ

205 REM ПЕРЕМЕННОЙ В ОГРАНИЧЕНИИ I

210 FOR I=1 ТО M:READ BS(I):NEXT I 250 REM ПОМЕТИТЬ НЕБАЗИСНЬЕ ПЕРЕМЕННЬЕ;ЕСЛИ ] – 255 REM НЕБАЗИСНАЯ ПЕРЕМЕННАЯ,ТО NB(J)= 260 FOR I=1 ТО M:NB(BS(I))=1:NEXT I 290 НАПЕЧАТАТЬ ТАБЛИЦУ 300 PRINT “ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА”: PRINT “ИТЕРАЦИЯ” К 310 GOSUB 3000:STOP 400 ZERO =1E-

490 REM НАЙТИ НАИМЕНЬШИЙ КОЭФФИЦИЕНТ В СТРОКЕ Z (Т.Е.

495 REM СТРОКУ Ml) 500 MIN=-ZERO:S=0:PV= 510 FOR J=1 ТО N 520 IF NB(J)=1 THEN GOTO 530 IF A(M1,J)>=MIN THEN GOTO 540 MIN =A(M1,J):S=J 550 NEXT J

560 REM ЕСЛИ S=0,TO ВСЕ КОЭФФИЦИЕНТЫ ПОЛОЖИТЕЛЬНЫ И

565 REM МИНИМУМ НАЙДЕН 570 IF S=0 THEN GOTO

740 REM НАЙТИ СТРОКУ ПЕРЕМЕННЫХ,КОТОРУЮ СЛЕДУЕТ

745 REM ИСКЛЮЧИТЬ ИЗ БАЗИСА ПО УСЛОВИЮ МИНИМУМА BI/A(IS)

750 MIN =1E20:R= 760 FOR I=1 ТО М 770 IF A(I,S)=MIN THEN GOTO 800 R=I:MIN=A(I,0)/A(I,S) 810 NEXT I

890 REM ЕСЛИ R=0,TO ИМЕЕТ МЕСТО РЕШЕНИЕ БЕЗ ОГРАНИЧЕНИЙ

900 IF R=0 THEN GOTO 910 PRINT “ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ” ;R; “СТОЛБЦА”;S 920 PRINT “”

990 REM РАЗДЕЛИТЬ ВЕДУЩУЮ СТРОКУ НА ВЕДУЩИЙ ЭЛЕМЕНТ

1000 PV=A(R,S) 1010 FOR J=0 TO N:A(R,J)=A(R,J)/PV:NEXT J

1040 REM ВЫЧИСЛИТЬ НОВУЮ КАНОНИЧЕСКУЮ ФОРМУ, ЗАПОМНИВ

1045 REM ВЕДУЩИЙ СТОЛБЕЦ ДО ЕГО ИЗМЕНЕНИЯ

1050 FOR I=1 ТО M1:V(I)=A(I,S):NEXT I 1070 FOR I=1 ТО M 1080 IF I=R THEN GOTO 1090 FOR J=0 TO N 1100 A(I,J)=A(I,J)-V(I)*A(R,J) 1110 NEXT J 1120 NEXT I

1150 REM ПЕРЕНАЗНАЧИТЬ И ПОВТОРНО ПОМЕТИТЬ БАЗИСНЬЕ

1155 REM И НЕБАЗИСНЬЕ ПЕРЕМЕННЬЕ 1160 NB(BS(R))=0:NB(S)=1:BS(R)=S 1170 REM СЧЕТЧИК ИТЕРАЦИЙ 1180 К=К+ 1190 REM НАПЕЧАТАТЬ НОВУЮ ТАБЛИЦУ 1200 PRINT “ИТЕРАЦИЯ”К 1210 GOSUB 3000:STOP

1240 REM ПОВТОРИТЬ ИТЕРАЦИОННУЮ ПРОЦЕДУРУ

1250 GOTO 1800 PRINT “HEPEMEHHAЯ “S” НЕ ИМЕЕТ ОГРАНИЧЕНИЙ” 1810 GOSUB 3000:STOP 1820 GOTO 2000 PRINT “ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ” 2010 PRINT “ОГРАНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ” 2020 РВ= 2030 FOR I=1 ТО М 2050 PA=A(I,0):GOSUB 9000:PRINT “” 2060 NEXT I 2090 PRINT “МИНИМУМ ФУНКЦИИ Z РАВЕН ”;-A(М1,0) 2100 GOSUB 2500 END 3000 PRINT “БАЗИС ЗНАЧЕНИЕ”;

3010 FOR J=l TO N:PRINT“ X”J “ ”;:NEXT J 3020 PRINT “” 3030 PB= 3040 FOR I=1 TO Ml 3050 IF I=M1 THEN PRINT"-Z";:GOTO 3060 PRINT BS(I);

3080 FOR J=0 TO N 3090 PA=A(I,J):GOSUB 3100 NEXT J 3110 PRINT “” 3120 NEXT I:PRINT “” 3200 RETURN 4000 DATA 2, 4010 DATA 3,4,1,0,2,5,0,l,-2,-4,0, 4020 DATA 1700,1600, 4030 DATA 3, 9000 PC=INT(PB/100) 9010 P$= “ 9020 IF PC=0 THEN PRINT “”:GOTO 9030 PRINT LEFT$(P$,PC)' 9040 PC=PB-100*PC 9050 PD=INT(PC/10):PC=PC-10*PD 9060 IF PD=0 THEN P0=l 9070 IF PA=10^PD THEN PRINT PA;:RETURN 9110 P$=P$+MID$(STR$(INT(PE)),2,PD) 9120 PRINT RIGHT$(P$,PD+1) 9130 IF PC=0 THEN RETURN 9140 PRINT “.”;

9150 PE=INT((PE-INT(PE))*10^PC) 9160 P$="000000000" 9170 P$=P$+MID$(STR$(PE),2,РС) 9180 PRINT RIGHT$(P$,PC);:RETURN Полезно сделать следующие замечания по поводу этой программы. Минимум c /j, определяется в строках от 500 до 550 в предположении, что они существуют. Положив сначала переменную MIN = 10 8, можно избежать поиска ложного отрицательного значения. Следует помнить, что ЭВМ выполняет действия с конечной точностью. Симплексметод иногда требует длинных и скрупулезных вычислений, в процессе которых ошибки могут накапливаться; в частности, величины, которые должны быть нулевыми, могут принимать значения, скажем, 1, 23947 10 29. Мы хотим избежать таких ошибочных отрицательных значений.

Аналогичные предосторожности следует принять в процедуре нахождения строки переменных для исключения из базиса (строки 750-880). Проверяем, что коэффициенты a /is положительны. Отметим, что в рассматриваемой процедуре (где ищется минимальное значение b /i a /is ) это означает, что не придется делить на 0 - это вызвало бы ошибку в процессе выполнения программы.

Промежуточные таблицы могут быть распечатаны в строках 300, 310, 1200, 1210, 1810, 2100. Некоторые из них (в строке 1210) могут быть выброшены. Первый фрагмент распечатки служит для проверки того, что данные правильны. Печать в строке программы 910 определяет позицию ведущего элемента, ведущей строки и ведущего столбца.

В процедуре, начинающейся со строки 3000, производится распечатка таблицы. Хотя выводимая информация и форматирована, ясно, что для больших значений выдача на экран и на АЦПУ приведет к переполнению количества допустимых колонок печати, так что необходимы будут некоторые модификации. Однако если ограничиться иллюстративными задачами с небольшим (до 10) количеством переменных, то осложнений не будет.

Процедура, начинающаяся со строки 9000, является форматирующей. Ее значение объясняется в приложении. Форматирующие значения РВ = 144 в строке 2020 и РВ = 122 в строке 3030, конечно, могут меняться в зависимости от значений, рассматриваемых величин и от требований точности при выводе.

Приведенный образец распечатки относится к примеру 1 разд. 2.1; данные в распечатке верные. Ясно, что воспроизведена симплексная таблица этого решения.

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

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 2 СТОЛБЦА

ВЕДУИЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 1 СТОЛБЦА

ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ

ОГРАНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ

2.3. ПОРОЖДЕНИЕ НАЧАЛЬНОГО БАЗИСНОГО ДОПУСТИМОГО

РЕШЕНИЯ

Примеры, выбранные для иллюстрации симплекс-метода, были заимствованы из разд.1.2.

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

Пусть требуется решить следующую задачу.

Пример Минимизировать функцию 3x 1 4x 2 = z при ограничениях x 1, x 2 0, Это - пример 1 из разд.1.2; он решается графически без всяких затруднений. В стандартной форме с неотрицательными дополнительными переменными ограничениями принимают вид Однако при попытке применить симплекс-метод возникает определенная трудность. Дело в том, что нет очевидного базисного допустимого решения. Базисное решение, получаемое приравниванием дополнительных переменных значениям в правых частях, недопустимо.

Этим решением является точка x 1 = x 2 =0, x 3 = -10, x 4 =- 5, x 5 = 20, x 6 = 20, и в нем x 3 и x 4 оказываются отрицательны. Трудности возникают из-за ограничений в виде неравенств.

Они возникли бы и при ограничениях в виде равенств.

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

и для них базисное решение очевидно. Это решение x 1 = x 2 = x 3 = x 4 = 0 (небазисные переменные), x 7 = 10, x 8 = 5, x 5 = 20, x 6 = 20. Затем симплекс-метод используется для минимизации функции Функция w называется искусственной целевой функцией. Этап I задачи состоит в минимизации функции w.

Предположим, что ограничения (2.22) имеют допустимое решение и, следовательно, базисное допустимое решение (это не всегда так) ; тогда решение этапа I задачи закончится тем, что функция w обратится в 0 и при этом x 7 и x 8 тоже будут нулевыми. Но когда x 7 и x 8 равны нулю, измененные ограничения (2.23) равносильны исходным (2.22). Базисное допустимое решение, минимизирующее функцию w, может быть использовано как начальное базисное допустимое решение для минимизации функции z на этапе II задачи.

Начиная с этого момента, нулевые значения x 7 и x 8 игнорируются.

Разумеется, для минимизации функции w надо выразить ее в подходящем виде, т. е.

через небазисные переменные. Переменные x 7 и x 8 являются, конечно, базисными в первом решении уравнений (2.23). Из функции w легко исключить x 7 и x 8. Надо просто вычесть из выражения для функции w содержащие их строки. Эта идея применяется и в других задачах. Таким образом, получаем При решении этапа I задачи соответствующие вычисления производятся в выражении для функции z, к которому применимы те же операции, что и к ограничениям. Таким образом, по завершении этапа I получим функцию z, приведенную к данному базису. После того как функция w обратилась в 0, игнорируем ее на этапе II задачи. То же относится и к искусственным переменным.

Таблицы для этапа I задачи имеют следующий вид:

На этой стадии минимизирована функция w, переменные x 7 и x 8 небазисные и потому равны 0. Заметим, что можно было бы пренебречь x 7, еще на итерации 1 и уж точно с настоящего момента можно пренебречь и x 7, и x 8. Переменная x 7 сохранена просто для того, чтобы показать, что в оптимальное решение для функции w и x 7, и x 8 входят с коэффициентом 1, когда значение функции w равно 0( w + x 7 + x 8 = 0 ). Поскольку выражение для функции z, приведенной к данному базису, сохраняется, можно минимизировать функцию z по-настоящему. Сейчас мы находимся в точке Р (рис. 1.2).

Этап I задачи завершен, и конечная таблица без последних двух столбцов и без последней строки является входной для этапа II. Таблицы этапа II имеют следующий вид:

Последовательные таблицы 2, 3, 4 соответствуют точкам Р, Q, R (рис. 1.2). Последняя таблица оптимальна, так что минимум функции z равен -68 при x 1 = 12, x 2 =8, x 3 =2, x 4 =3.

Поскольку дополнительные переменные x 3 и x 4 принимают положительные значения при оптимальном решении, видно, что ограничения в оптимальном решении, в которые эти переменные входят, превращаются в строгие неравенства.

Пример (это - пример 4 разд 1.2).

Минимизировать функцию 2x 1 + 3x 2 = z при ограничениях x 1, x 2 0, Приведем ограничения к стандартной форме Изменим первое ограничение, введя искусственную переменную x 5 и минимизировав функцию w = x 5. В канонической форме получим x 1 x 2 + x 3 = w 10. Симплекстаблицы выглядят следующим образом:

На этой стадии функция w минимизирована. Все коэффициенты в строке w таблицы положительны. Но функция w не обратилась в 0, а x 5 = 5. Мы не можем найти допустимое решение неизмененных ограничений (2.26), что иллюстрирует и рис. 1.5. Этап I задачи завершен, но мы не можем перейти к этапу II, поскольку исходные ограничения не имеют допустимого базисного решения.

Пример Фирме требуется уголь с содержанием фосфора не более 0,03 % и с примесью пепла не более 3,25 %. Доступны три сорта угля А, В, С по следующим ценам (за 1 т) :

Как их следует смешать, чтобы удовлетворить ограничениям на примеси и минимизировать цену? (Это - упр. 8 разд. 1.6, в котором рекомендовалось свести эту задачу к двухмерной.) Используя симплекс-метод, можно решать эту задачу в той форме, в которой она поставлена.

Пусть 1 т смеси содержит x 1, x 2, x 3 угля типа А, В и С соответственно.

Тогда x 1 0, x 2 0, x 3 0. При этом должны выполняться следующие ограничения:

z = 30x 1 + 30x 2 + 45 x 3 было минимально.

Если добавить дополнительные переменные ко второму и третьему ограничению (предварительно умножив последнее на 100), получим задачу в стандартной форме.

Для неотрицательных x i ( i = 1, K, 5 ) минимизировать 30x 1 + 30x 2 + 45x 3 = z при ограничениях Базисное допустимое решение неочевидно. Будем обращаться с первым ограничением в виде равенства так же, как с ограничениями в виде неравенств в предыдущих примерах.

Добавим искусственную переменную x 6. Затем минимизируем функцию w = x 6 и используем полученное оптимальное решение в качестве начальной точки для минимизации функции z.

Таким образом, ограничения принимают следующий вид:

при этом допустимые базисные решения являются x 1 = x 2 = x 3 = 0, x 6 = 1, x 4 = 3, x 5 = 3. Выразим w через небазисные переменные, исключив x 6. Для этого надо просто вычесть первое равенство (единственное равенство, содержащее x6, причем с коэффициентом 1) из выражения для функции w, получим Последовательные вычисления таблиц приведены ниже:

Этап I задачи заканчивается после итерации 1; затем значения w и x 6 игнорируются.

Минимальное значение функции z равно 38 дол.; оно достигается при x 1 = 1/12, x 2 = 1/3, x 3 = 7/12.

2.4. ПОЛНОЕ ИЗЛОЖЕНИЕ СИМПЛЕКС-МЕТОДА Как было показано, ограничения в задачах линейного программирования могут быть заданы в разных видах. Базисное допустимое решение не всегда очевидно. Таким образом, в программе для ЭВМ должны вводиться автоматически дополнительные и искусственные переменные и должно порождаться первое базисное допустимое решение.

Предположим, что в задачу входят М ограничений и N (исходных) данных. Пусть среди них содержатся GC ограничений в виде неравенств со знаком, ЕС - в виде равенств со знаком = и LC в виде неравенств со знаком и пусть они расположены именно в таком порядке. Предположим, что правые части ограничений положительны. При этом не происходит потери общности. Исходная задача имеет следующий вид:

при ограничениях x i 0, ( i = 1, K, N ) В первые GC ограничений вводятся дополнительные переменные x N +1, K, x N+G C с коэффициентом -1. В последние LC ограничений вводятся дополнительные переменные переменные x N+MK +1, K, x N+MK +GC +EC (МК = GC + LC - количество дополнительных переменных) с коэффициентом +1 вводятся в первые GC + ЕС ограничений. Эти переменные вместе с последними LC дополнительными переменными образуют исходное базисное допустимое решение. Ими являются значения правых частей ограничений.

Искусственная целевая функция w является суммой искусственных переменных.

Выраженная через небазисные переменные, она имеет вид где коэффициент d j состоит из отрицательного значения суммы, взятой по первым GC + ЕС строкам коэффициентов при x j расширенной матрицы ограничений. Величина w 0 равна сумме правых частей, взятой с противоположным знаком. Величины w 0 и d содержатся в (М + 2)-и строке расширенной таблицы.

Итак, для этой задачи, в которой все переменные неотрицательны, a GC = 2, ЕС = 1, LC = 1 (т. е. М = 4, МК = 3) и N = 3, имеем следующие ограничения:

и функцию x 1 2x 2 3x 3 = z, которую необходимо минимизировать. Заполним первую таблицу.

Для вычислений можно использовать предыдущую программу (строки с 500-й по 1180ую). Необходимо знать, на каком этапе задачи (I или II) в настоящий момент производятся вычисления. На этапе I L = 1 (в программе); целевая функция z хранится в строке М + 2, а с выражением для функции z следует обращаться так же, как со всеми остальными ограничениями. На этапе II полагаем L = 0; целевая функция z хранится в строке М + 1, а столбцы с искусственными переменными игнорируются. Когда в конце этапа I задачи минимизирована функция w, необходимо проверить, достигло ли ее значение 0 с точностью до ошибок округления, и приравнять L 0, прежде чем переходить к этапу II задачи. Ниже приведена распечатка текста программы.

10 PRINT “РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМЛЕКС-МЕТОДОМ”

15 READ ZZ

18 REM ПРИ ZZ=+1 ПРОМЕЖУТОЧНАЯ ТАБЛИЦА ВЫВОДИТСЯ НА

19 REM ПЕЧАТЬ;ПРИ ZZ=-1 НЕ ВЫВОДИТСЯ

20 REM ВВЕСТИ КОЛИЧЕСТВО ВИДОВ ОГРАНИЧЕНИЙ И КОЛИЧЕСТВО

22 REM ПЕРЕМЕННЫХ 25 READ GC,EC,LC,N 30 MM=GC+EC:M=MM+LC:MK=GC+LC:N1=MK+N 40 P=N1+MM:M1=M+1:M2=M+2:N0=N 50 DIM A(M2,P),BS(M),V(M2),NB(P),SL(P)

55 REM ВВЕСТИ КОЭФФИЦИЭНТЫ ДЛЯ ОГРАНИЧЕНИЙ И ЦЕЛЕВОЙ ФУНКЦИИ

60 FOR I=1 TO Ml:FOR J=l TO N:READ A(I,J):NEXT J:NEXT I

90 REM ЗАДАТЬ ОСЛАБЛЕННЫЕ, ИСКУССТВЕННЫЕ ПЕРЕМЕННЫЕ,

95 REM ПОМЕСТИТЬ БАЗИС И ПРОЧИТАТЬ ПЕРЕМЕННЫЕ В НУЛЕВОЙ

98 REM СТОЛБЕЦ 100 IF GC =0 THEN GOTO 110 FOR I=1 TO GC 120 A(I,N+I)=-1:A(I,N1+I)= 130 BS(I)=N1+I:READ A(I,0) 140 NEXT I 150 IF EC=0 THEN GOTO 160 FOR I=GC+1 TO MM 170 A(I,N1+I)=1:BS(I)=N1+1:READ A(I,0) 180 NEXT I 200 IF LC=0 THEN GOTO 210 FOR I=MM+1 TO M 230 A(I,N+I-EC)=1:BS(I)=N+I-EC:READ A(I,0) 240 IF MM=0 THEN PRINT “ОТСУТСТВУЕТ ЭТАП 1 РЕШЕНИЯ ЗАДАЧИ”

250 REM ЗАДАТЬ ИСКУССТВЕННУЮ ФУНКЦИЙ ДЛЯ ЭТАПА

260 L=1:N0=P:REM N0 ЯВЛЯЕТСЯ НОМЕРОМ НУЖНОГО СТОЛБЦА 270 FOR I=1 TO MM:FOR J=0 TO N 280 A(M2,J)=A(M2,J)-A(I,J) 290 NEXT J:NEXT I 300 ML=M1+L:REM ML=M+2 ДЛЯ ЭТАПА 1;ML=M+1 ДЛЯ ЭТАПА 320 IF ZZ>=0 THEN PRINT“ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА” 325 GOSUB 3000:STOP 330 REM ПОМЕСТИТЬ НЕБАЗИСНЫЕ ПЕРЕМЕННЫЕ;NB(J)=0,ЕСЛИ 335 REM J-НЕБАЗИСНАЯ ПЕРЕМЕННАЯ 350 FOR I=1 TO M:NB(BS(I))=1:NEXT I 400 ZERO = 1E-

490 REM НАЙТИ НАИМЕНЬШИЙ КОЭФФИЦИЭНТ В СТРОКЕ ЦЕЛЕВОЙ

495 REM ФУНКЦИИ, Т.Е. СТРОКУ ML 500 МIN=-ZERO:S=0:PV=0:М1=М1+L 510 FOR J=1 ТО N 520 IF NB(J)=1 THEN GOTO 530 IF A(ML,J)>=MIN THEN GOTO 540 MIN =A(ML,J):S=J 550 NEXT J

560 REM ЕСЛИ S=0,TO ВСЕ КОЭФФИЦИЕНТЫ ПОЛОЖИТЕЛЬНЫ И

565 REM МИНИМУМ НАЙДЕН 570 IF S=0 THEN GOT

740 REM НАЙТИ СТРОКУ ПЕРЕМЕННЫХ,КОТОРУЮ СЛЕДУЕТ

745 REM ИСКЛЮЧИТЬ ИЗ БАЗИСА ПО УСЛОВИЮ МИНИМУМА BI/A(IS)

750 MIN =1E20:R= 760 FOR I=1 ТО М 770 IF A(I,S)=MIN THEN GOTO 800 R=I:MIN=A(I,0)/A(I,S) 810 NEXT I

890 REM ЕСЛИ R=0,TO ИМЕЕТ МЕСТО РЕШЕНИЕ БЕЗ ОГРАНИЧЕНИЙ

900 IF R=0 THEN GOTO 910 PRINT “ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ”;R;“CTOЛБЦА”;S:PRINT“”

990 REM РАЗДЕЛИТЬ ВЕДУЩУЮ СТРОКУ НА ВЕДУЩИЙ ЭЛЕМЕНТ

1000 PV=A(R,S) 1010 FOR J=0 ТО N0:A(R,J)=A(R,J)/PV:NEXT J

1040 REM ВЫЧИСЛИТЬ НОВУЮ КАНОНИЧЕСКУЮ ФОРМУ,ЗАПОМНИВ

1045 REM ВЕДУЩИЙ СТОЛБЕЦ ДО ЕГО ИЗМЕНЕНИЯ

1050 FOR I=1 TO ML:V(I)=A(I,S):NEXT I 1070 FOR 1=1 ТО ML 1080 IF I=R THEN GOTO 1090 FOR J=0 TO N 1100 A(I,J)=A(I,J)-V(I)*A(R,J) 1110 NEXT J 1120 NEXT I

1150 REM ПЕРЕНАЗНАЧИТЬ В ПОВТОРНО ПОМЕТИТЬ БАЗИСНЬЕ

1155 REM И НЕБАЗИСНЬЕ ПЕРЕМЕННЬЕ 1160 NB(BS(R))=0:NB(S)=1:BS(R)=S 1170 REM СЧЕТЧИК ИТЕРАЦИЙ 1180 К=К+ 1190 REM НАПЕЧАТАТЬ НОВУЮ ТАБЛИЦУ 1200 IF ZZ>=0 THEN PRINT“ИТЕРАЦИЯ”K:GOSUB 3000:STOP

1240 REM ПОВТОРИТЬ ИТЕРАЦИОННЫЙ ПРОЦЕСС

1250 GOTO 1800 PRINT “ПЕРЕМЕННАЯ “S” НЕ ИМЕЕТ ОГРАНИЧЕНИЙ” 1810 GOSUB 3000:STOP 1820 GOTO 1900 IF L=0 THEN GOTO

1905 REM ДЛЯ ЭТАПА 2 ЭТА ТОЧКА ЯВЛЯЕТСЯ МИНИМУМОМ.ЕСЛИ

1908 REM МЫ НАХОДИМСЯ НА ЭТАПЕ 1,ТО ПЕРЕЙТИ К ЭТАПУ 1910 REM ПРОВЕРИТЬ,ЧТО W СТАЛО РАВНО 1920 IF ABS(A(ML,0))>=lE-08 THEN GOTO 1930 PRINT “ЭТАП 1 УСПЕШНО ЗАВЕРШЕН” 1940 L=0:N0=N1:REM ЗАДАТЬ L И НОМЕР СТОЛБЦА ДЛЯ ЭТАПА 1950 GOTO

1960 PRINT “ОГРАНИЧЕНИЯ НЕ ИМЕЮТ ДОПУСТИМОГО РЕШЕНИЯ”

1970 PRINT “СУММА ИСКУССТВЕННЫХ ПЕРЕМЕННЫХ РАВНА”;:PRINT -A(ML,0) 1980 GOSUB 3000:STOP 2000 PRINT “ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ” 2010 PRINT “ОГРАНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ” 2020 РВ= 2030 FOR I=1 ТО M:SL(BS(I))=A(I,0) 2040 PRINT" ";I;" ":BS(I);

2050 PA=A(I,0):GOSUB9000:PRINT “” 2060 NEXT I 2090 PRINT “МИНИМУМ ФУНКЦИИ Z РАВЕН ”;-А(М1,0)

2100 PRINT “ОГРАНИЧЕНИЕ СОСТОЯНИЕ ДОПОЛНИТЕЛЬНЫЕ ПЕРЕМЕННЬЕ”

2120 FOR 1=1 TO M 2130 PRINT“”;I;“”;

2140 IF IMM THEN GOTO 2150 PRINT“УPABHEHHE HE РЕШЕНО”:GOTO 2160 IF NB(N+1)=1 THEN PRINT“ДОПОЛ.ПЕРЕМ.”;

2165 PA=SL(N+1):GOSUB 9000:PRINT“”:GOTO 2170 PRINT “OГPAHHHEHHE 0” 2180 NEXT I 2300 GOSUB 2500 END 3000 PRINT “БАЗИС ЗНАЧЕНИЕ”;

3010 FOR J=1 TO N:PRINT“ X”J“ ”;:NEXT J 3020 PRINT“” 3030 PB= 3050 IF I=M1 THEN PRINT“–Z”;:GOTO 3060 PRINT BS(I);

3090 PA=A(I,J):GOSUB 3110 PRINT“” 3120 NEXT I:PRINT“” 3200 RETURN 4010 DATA 2,0,2, 4020 DATA 1,0,0,1,1,1,-1,4,-3,- 4030 DATA 10,5,20, 9000 PC=INT(PB/100) 9020 IF PC=0 THEN PRINT“”:GOTO 9030 PRINT LEFT$(P$,PC);

9040 PC=PB-100*PC 9050 PD=INT(PC/10):PC=PC-10*PD 9060 IF PD=0 THEN PD= 9070 IF PA=10^PD THEN PRINT PA;:RETURN 9110 P$=P$+MID$(STR$(INT(PE)),2,PD) 9120 PRINT RIGHT$(P$,PD+1) 9130 IF PC=0 THEN RETURN 9140 PRINT“.”;

9150 РЕ=INT((РЕ-INT(РЕ))*10^РС) 9160 P$=“000000000” 9170 P$=P$+MID$(STR$(PE),2,PC) 9180 PRINT RIGHT$(P$,PC);:RETURN Если учесть все замечания, а также комментарии в тексте программы, то будет понятно, каким способом программа вводит дополнительные и искусственные переменные (строки с 100-й по 230-ую) и при необходимости - искусственную целевую функцию (строки с 250-й по 290-ю). Фактически вычисления симплекс-методом этапов I и II задачи следуют приведенной выше программе, которую теперь можно заменить на более проработанную версию. Когда все коэффициенты целевой функции положительны, следует позаботиться о том, чтобы программа не закончила работу, если вычисления осуществляются на этапе I. В этом случае переходим к этапу II, просто заменив L с 1 на 0, что изменит ML в строке 500 с М + 2 на М+1 и NO с Р (количество столбцов, соответствующих исходным, дополнительным и искусственным переменным) на N1 (количество столбцов, соответствующих исходным и дополнительным переменным). При этом следует удостовериться, что все искусственные переменные обратились в 0.

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

Снова используется форматирующая процедура 9000 (см. приложение). Форматные переменные в строках 2020 - 3030 могут быть изменены. При работе с большим количеством переменных оператор печати в строке 3000 следует изменить. Ее, конечно, можно подавить, скажем присвоив значение -1 первой величине ZZ из области данных.

Пример (это - пример 1 разд.2.3) Найти такие неотрицательные x 1, x 2, что и минимизировать функцию 3x 1 4x 2 = z.

В этом примере GC = 2, ЕС = О, LC = 2, N = 2. Соответствующие данные содержатся в строках 4000-4030. В распечатке приводятся вычисленные ранее таблицы:

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦЙ

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 1 СТОЛБЦА

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 2 СТОЛБЦА

ЭТАП 1 УСПЕШНО ЗАВЕРЕН

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 4 СТОЛБЦА

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 3 СТОЛБЦА

ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ

ОГРАНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ

МИНИМУМ ФУНКЦИИ РАВЕН -

ОГРАНИЧЕНИЕ СОСТОЯНИЕ ДОПОЛНИТЕЛЬНЫЕ ПЕРЕМЕННЫЕ

2.5. ПРОБЛЕМЫ ВЫРОЖДЕНИЯ В рассмотренных выше примерах все базисные переменные были ненулевыми. Ясно, что все небазисные переменные равны 0 по определению. Однако нет никаких препятствий к тому, чтобы одна или несколько переменных обратились в 0. В этом случае базис называют вырожденным и могут возникнуть трудности.

Предположим, что одна из. базисных переменных обратилась в О ( b /r = 0). Если x s свободная переменная, которая должна быть введена в базис, то, если переменная a /rs положительна, она должна быть ведущей; тогда b /r a /rs =0 и поэтому Следовательно, x s войдет в базис со значением 0 и новый базис тоже будет вырожден.

Значение функции z останется без изменений. Таким образом, если на следующем шаге итерации x s можно было бы обратно заменить на x r, то образовался бы замкнутый цикл и дальнейшие итерации не приводили бы к уменьшению функции z.

Пример Найти такие неотрицательные x 1, x 2, что Графическое решение (рис. 2.2) показывает, что точка минимума - это точка (3,2), где z = -7. Вырожденность возникает, поскольку прямые, соответствующие ограничениям, пересекаются в одной точке (2, 0). Обычно вершина является пересечением всего двух прямых (в двухмерном случае). В данном При использовании симплекс-метода первая таблица имеет следующий вид:

Переменная x 1 входит в базис. Но какую переменную исключить из базиса: x 3 или x 4 ?

В точке минимума имеет место совпадение 4/2 = 2/1 (поэтому в таблице звездочкой обозначены два коэффициента). Какую переменную ни выберешь, другая на следующей итерации обратится в 0, и базис будет вырожден. Пусть выбрана переменная x 3. Тогда получаем следующую таблицу:

Итак, минимум функции z равен -7 и достигается при x 1 = 3, x 2 =2.

Предположим, что для исключения из базиса на итерации 0 выбрана переменная x 4.

Полученные таблицы приведены ниже. Окончательное решение то же, что и выше.

В этом случае вырожденный базис на итерации 1 меняется на вырожденный базис на итерации 2. Переменная z не меняет значения. Затем происходит перемещение в точку минимума В. Один из способов избежать вырожденности - слегка изменить ограничения, что позволит изменить положение точки А. Данциг предлагает заменять их на следующие ограничения:

где - малая величина. Так мы избегаем вырожденности, поскольку ограничения в точке А не будут выполняться одновременно. Окрестность точки А примет вид, изображенный на рис. 2.3.

окончательное решение будет входить. Затем следует обратить в 0. Таким образом можно обойти связанные с вырожденностью трудности. Все это может показаться очень сложным, но пусть читатель не волнуется: ниже этот вопрос будет детально рассмотрен.

Если вырожденности нет, то симплекс-методом задача линейного программирования решается за конечное число шагов (разумеется, в предположении, что решение существует).

Это можно легко показать. На любой итерации, как видно из уравнения (2.20), значение целевой функции меняется от z /0, скажем, на z /0 + c /s b +, где c /s - коэффициент при переменной, которая только что была включена в базис, соответствующий предыдущей целевой функции; b + - значение, которое она принимает. Далее коэффициент c /s строго отрицателен, а значение b /r положительно. Таким образом, функция z убывает на каждом шаге. Поэтому никогда не происходит возвращения к предыдущему множеству базисных переменных (иначе целевая функция приняла бы то же значение, что и раньше). Поскольку имеется не более допустимых решений, минимум будет найден не более чем за итераций.

Если значение b + обращается в 0, то возвращение к предыдущему базису возможно и приведенное выше рассуждение не применимо. Это называется зацикливанием.

Зацикливание встречается редко, и его, вероятно, можно избежать при вычислениях вручную благодаря правильному выбору3. В программах должна быть предусмотрена возможность решить эту проблему. Мы вернемся к этому позже.

Пример Этот пример иллюстрирует зацикливание. Он был построен И. М. Л. Билом.

Найти такие неотрицательные x 1, x 2, x 3, x 4, что и минимизировать функцию При решении этой задачи на ЭВМ случайно произошло зацикливание. Это свидетельствует о том, что для создания достаточно мощной программы необходимы некоторые изменения. На итерации производится выбор переменной для превращения ее в небазисную переменную (это может быть x 5 или x 6 ). Была выбрана переменная x 5. На итерации 2 была выбрана переменная x 1, а не x 2. На итерации 4 была выбрана переменная x 3, а не x 4. Таблица на итерации 6 совпадает с начальной таблицей. ЭВМ будет продолжать вычисления, не уменьшая значения функции z. При вычислении вручную можно выбрать другие переменные. Читателю предлагается сделать это.

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

Минимум для функции z достигается при x 1 = 1, x 3 = 1, x 6 = 0,75 и остальных x i = 0.

Минимальное значение функции z = -1,25.

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

ОТСУТСТВУЕТ ЭТАП 1 РЕШЕНИЯ ЗАДАЧИ

ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ СТРОКЕ 1 СТОЛБЦА

Автор, по-видимому, имеет в виду выбор небазисных переменных. - Прим. ред.

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 2 СТОЛБЦА

ИТЕРАЦИЯ

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 1 СТОЛБЦА

ИТЕРАЦИЯ

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 2 СТОЛБЦА

ИТЕРАЦИЯ

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 1 СТОЛБЦА

ИТЕРАЦИЯ

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 2 СТОЛБЦА

ИТЕРАЦИЯ

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

ОТСУТСТВУЕТ ЭТАП 1 РЕШЕНИЯ ЗАДАЧИ

ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 1 СТОЛБЦА

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 3 СТОЛБЦА

ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ

ОГРАНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ

МИНИМУМ ФУНКЦИИ Z РАВЕН -1.

ОГРАНИЧЕНИЕ СОСТОЯНИЕ ДОПОЛНИТЕЛЬНЫЕ ПЕРЕМЕННЬЕ

2.6. УПРАЖНЕНИЯ 1. Используйте симплекс-метод для максимизации функции 3x 1 + 6x 2 + 2x 3 при ограничениях x 1, x 2, x 3 0, Найдите такие x 1, x 2, x 3 0, что для них справедливы неравенства и минимизируйте функцию 2x 1 2x 2 + 4x 3 = z.

3. Фирма производит три вида продукции (А, В, С), для выпуска каждого из которых требуется определенное время обработки на всех четырех устройствах I, II, III, IV.

I II III IV

Пусть время работы на устройствах - соответственно 84, 42, 21 и 42 ч. Определите, какую продукцию и в каких количествах следует производить. (Можете предположить, что рынок сбыта для каждого продукта неограничен; временем, требуемым для переключения устройства в зависимости от вида продукции, можно пренебречь; рассмотрите только задачу максимизации прибыли.) 4. Производитель безалкогольных напитков располагает двумя разливочными машинами А и В. Машина А спроектирована для пол-литровых бутылок, а машина В - для литровых, но каждая из них может использоваться для обоих типов бутылок с некоторой потерей эффективности в соответствии с приведенными в таблице сведениями о работе машин.

Каждая из машин работает ежедневно по 6 ч при пятидневной рабочей неделе. Прибыль от пол-литровой бутылки составляет 4 цента, а от литровой - 10 центов. Недельная продукция не может превосходить 50 000 л; рынок принимает не более 44 000 пол-литровых бутылок и 30 000 литровых.

Производитель хочет максимизировать свою прибыль при имеющихся средствах.

Сформулируйте задачу в виде задачи линейного программирования и найдите оптимальное решение.

5. Минимизируйте функцию z = 50x 1 + 25x 6. Максимизируйте функцию w = 8y 1 + 19y 2 + 7y 3, при ограничениях 7. Производитель элементов центрального отопления изготовляет радиаторы четырех моделей. Ограничения на производство обусловлены количеством рабочей силы и количеством стальных листов, из которых изготовляются радиаторы.

Необходимое количество рабочей силы, человеко-часы 0,5 1,5 2 1, Решите эту задачу с максимизацией прибыли в качестве целевой функции, используя симплекс-метод.

8. Небольшая фирма производит два типа подшипников А и В, каждый из которых должен быть обработан на трех станках, а именно на токарном, шлифовальном и сверлильном. Время, требуемое для каждой из стадий производственного процесса, приведено в таблице.

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

9. Минимизируйте функцию z = 4x 1 5x 2 9x 3 11x 10. Фирма рекламирует свою продукцию с использованием четырех средств: телевизора, радио, газет и афиш. Из различных рекламных экспериментов, которые проводились в прошлом, известно, что эти средства приводят к увеличению прибыли соответственно на 10, 3, 7 и 4 дол. в расчете на 1 дол., затраченный на рекламу.

Распределение рекламного бюджета по различным средствам подчинено следующим ограничениям:

а) полный бюджет не должен превосходить 500 000 дол.;

б) следует расходовать не более 40 % бюджета на телевидение и не более 20 % бюджета на афиши;

в) вследствие привлекательности для подростков радио на него следует расходовать по крайней мере половину того, что планируется на телевидение.

Сформулируйте задачу распределения средств по различным источникам как задачу линейного программирования и используйте симплекс-метод для ее решения.

11. Найдите такие x 1 0, x 2 0, что выполняются ограничения и функция x 1 + x 2 = z минимальна.

12. Фирма занимается составлением диеты, содержащей по крайней мере 20 единиц белков, 30 единиц углеводов, 10 единиц жиров и 40 единиц витаминов. Как дешевле всего достичь этого при указанных в таблице ценах на 1 кг (или 1 л) пяти имеющихся продуктов?

13. Нефтяная компания закупает необработанную нефть из нескольких источников W, X, Y и Z и занимается ее очисткой, вырабатывая различные виды А, В и С, смазочных масел, готовых к продаже. Имеются также ограничения при продаже на количество каждого вида смазочных масел.

Цены (в условных единицах) 1 галлона сырья и смазочных масел приведены ниже.

X Y Z W A B C

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

14. Ткацкая фабрика должна работать 24 ч в сутки согласно следующей таблице:

количество ткачей Каждый ткач должен работать подряд 8 ч в день. Найдите минимальное необходимое количество ткачей, удовлетворяющее перечисленным требованиям. Покажите, что расписание работ подчинено ограничениям, имеющим следующий вид:

Объясните физический смысл каждой переменной и покажите, что переменные x 1, x 2, x 3, x 4, x 5, x 7, x 12 образуют допустимый базис. Приведите эту задачу линейного программирования к канонической форме и найдите оптимальное решение, используя симплекс-метод.

15. Минимизируйте 3x 1 4x 2 5x 3 = z 16. Измените приведенные программы так, чтобы переменная, выбранная для включения в базис на очередной итерации, была первой из имеющих отрицательный коэффициент переменных. Проверьте полученную программу на задачах, приведенных в упражнениях.

Приводит ли это изменение к заметному увеличению времени вычислений?

17. Условия неотрицательности линейного программирования могут быть обобщены к виду l j x j u j, где l j и u j - нижняя и верхняя границы для переменной x j. Ясно, что такие условия могут быть введены как дополнительные ограничения.

Однако имеется укороченная процедура, основанная на модификации симплекс-метода.

Она рассматривается в монографии У. У. Гарвина [ 8].

Обратитесь к этой работе и попытайтесь внести необходимые изменения в программы.

Сравните, что лучше: введение условий как дополнительных ограничений или использование укороченной процедуры?

ГЛАВА 3 АНАЛИЗ УСТОЙЧИВОСТИ РЕШЕНИЯ

3.1. ОБРАЩЕНИЕ БАЗИСА И СИМПЛЕКС-МНОЖИТЕЛИ

Относительно уравнения (2.7) выше было указано, что канонический вид для некоторого базиса может быть получен умножением вектора исходных ограничении на матрицу, полученную обращением этого базиса. Таким образом, если для общей задачи линейного программирования с m ограничениями и n неотрицательными переменными вида через В обозначена подматрица А, состоящая из m столбцов, соответствующих базисным переменным, так что А можно записать в виде где В - матрица из базисных переменных m * m, a R — матрица небазисных переменных m * (n — m ), то каноническая форма для базиса получается умножением уравнения на матрицу В. Тогда получим соотношение что соответствует канонической форме для ограничений.

Симплекс-метод не состоит в непосредственном вычислении обратной матрицы. Этот метод — итеративный; по существу, он обращает базис, и это обращение может быть найдено из таблиц вычислений симплекс-методом.

Если аj — столбец из коэффициентов при переменной хj в первом ограничении в форме неравенства, то представляет собой столбец из коэффициентов при хj в канонической форме. Если хj дополнительная переменная из ограничений в виде неравенств со знаком, то а a j — р-й столбец матрицы В-1. Если хК— дополнительная переменная из ограничения в виде неравенств со знаком, то а а k - q-й столбец матрицы B-1, взятый с противоположным знаком.

В качестве иллюстрации рассмотрим первую и последнюю таблицы примера 1 разд.2.1.

Итерация Базис Значение x Это - первая таблица.

Итерация Базис Значение x А это — конечная оптимальная таблица.

Оптимальный базис — (x1, x2). Матрица коэффициентов этого базиса для ограничений на итерации 0 имеет вид В первой канонической форме матрица коэффициентов при (х3,х4) В конечной таблице она принимает вид и легко проверить, что эта матрица - действительно матрица В-1.

Таким же образом рассмотрим первую и последнюю таблицы примера 1 разд.2.3.

Дополнительным переменным x3, x4, x5, x6 соответствует матрица из коэффициентов первой таблицы, т. е.

Окончательному базису (x1, x2, x3, x4) соответствует матрица из коэффициентов первой таблицы, т. е.

В окончательной таблице дополнительным переменным x3, x4, x5, x6 соответствует матрица поэтому (обратите внимание на изменение в первых двух столбцах) матрица В-1 представляет собой матрицу что легко проверяется.

Читателю рекомендуется вернуться к другим примерам и получить обращения базисов.

Значения базисных переменных вычисляются по формуле b/=B-1b, что также можно проверить.

В каждой канонической форме относящиеся к ней базисные переменные были исключены из целевой функции z. В симплекс-методе это делается итеративно, например на каждой стадии с использованием исходного вида ограничений. Задача общего вида формулируется следующим образом:

минимизировать функцию с1 х1 + с2 х2 +.... + сп хп = z

Можно умножить ограничения на 1, 2, …., m прибавить к выражению для функции z и получить соотношение Значения i можно выбрать так, что коэффициенты при базисных переменных в уравнениях (3.7) станут нулевыми. Значения i. называются симплекс-множителями. Если x1, x2,…,xmбазисные переменные (при этом не происходит потери общности), то i определяются из системы уравнений где В матрица из коэффициентов при базисных переменных, а с В = (с1,..., ст ) — коэффициенты при базисных переменных в исходном виде для функции z. Так как Однако может быть, что значения 1, …, m легче получить, просматривая симплекстаблицы.

Пусть хj — дополнительная переменная, которая не входила в целевую функцию в исходном виде. Если переменная х. появилась из p-го ограничения в виде неравенств со знаком, то коэффициент при ней 1(если задача задана в стандартной форме) равен +1. Переменная хj никуда больше не входит. Поэтому ясно, что коэффициент при ней в оптимальном виде для функции z будет p. Подобным образом если хk — новая переменная в q-м ограничении типа, то коэффициент при ней в оптимальном виде для функции z будет p.

Рассмотрим снова таблицу примера 1 разд.2.1. Коэффициенты при x3 и x4 в оптимальном виде для функции z равны соответственно 2/7 и 4/7; это и есть симплекс-множители для оптимального базиса.

Ограничения и целевая функция имеют следующий исходный вид:

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

Далее из уравнения (3.7) для функции z в окончательном виде ясно, что коэффициенты при базисных переменных будут нулевыми благодаря выбору i, а коэффициенты при небазисных переменных будут положительны. При этом (так как небазисные элементы равны 0) каждое слагаемое в левой части уравнения (3.7) равно 0; либо переменная, либо коэффициент при ней равны 0. Следовательно, оптимальное значение для функции z определяется формулой Для только что рассмотренного примера это очевидно (см. уравнение (3.10)).

Для примера 2 разд 2.3 коэффициенты при x3, х4, x5, x6 в конечной таблице равны (0, 0, 16/5, 1/5), а симплекс-множители равны (-0, -0, 16/5, 1/5) (заметим, что в первых двух случаях поменялся знак; в рассматриваемом случае это не имеет значения).

Проверьте, что умножение ограничений в виде равенств (2.22) на (0, 0, 16/5, 1/5) с последующим прибавлением к выражению для функции z, как указано в (2.22), действительно приводит к канонической форме для функции т. и что -(-0*10 + 0*5 + 16/5* + 1/5*20) = -68.

Читателю рекомендуется проверить также другие примеры. Это улучшит понимание того, что происходит на самом деле.

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

3.2. ЧТО ПОЛУЧАЕТСЯ ПРИ ИЗМЕНЕНИИ ЗАДАЧИ

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

Коэффициенты целевой функции могут выражать прибыль при коммерческих операциях.

Значения, входящие в правые части ограничений, могут выражать ограниченность доступных ресурсов. Можно ожидать, что в подобных случаях эти значения будут меняться, что, в свою очередь, приведет к изменению формулировок математических задач. Например, благодаря повышению производительности труда может увеличиться доступное производительное время станков; пожар на складе может снизить поставки сырья;

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

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

Однако этот способ может быть весьма неэффективен; он не учитывает полезную работу, проведенную при решении задачи до изменений.

Давайте последовательно рассмотрим:

1) изменения в bi (значения правых частей);

2) изменения в сj (коэффициенты целевой функции);

3) включение дополнительных переменных;

4) включение дополнительных ограничений.

1) Изменения в bi Пусть исходные ограничения заданы в виде Ax=b и функция z=cTx должна быть минимизирована.

Пусть новая задача формулируется так:

с той же целевой функцией z=c x Предположим, что исходная задача решена. Пусть в оптимальном базисе соответствующая подматрица матрицы В имеет обратную матрицу B-1. Пусть 1, 2,…., m являются симплексмножителями, а значения базисных переменных исходной задачи задаются формулой Из уравнения (3.7) значение целевой функции выражается следующим образом:

причем все (коэффициенты при базисных переменных равны 0, при небазисных переменных 0).