Банда Б. Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. - 176 с.: ил. ISBN 5-256-00186-8. В книге английского автора освещены основные положения и методы линейного программирования. Рассмотрены симплекс-метод и его реализация на ЭВМ, проблема вырожденности, анализ чувствительности и двойственный симплекс-метод, транспортная задача, задача о назначении, двойственность в линейном программировании и др. Алгоритмы решения различных задач линейного программирования реализованы на языке Бейсик, причем программы несложно перевести на такие языки, как Фортран или Паскаль. Для инженерно-технических работников, связанных с применением линейного программирования. Предисловие редактора перевода
Линейное программирование как. раздел исследования операций имеет почти сорокалетнюю историю. Внедрение вычислительной техники дало значительный толчок исследованиям в этой области математики. Был разработан ряд алгоритмов решения задач линейного программи-''•' рования, а в последующие годы были созданы программы и пакеты программ преимущественно для больших ЭВМ. Основная масса литературы по линейному программированию в нашей стране выпущена в 60 — 70-е годы. Исследования в этой области (как теоретические, так .- и прикладные) продолжаются и в настоящее время. Однако книг по >' приложениям линейного программирования, учитывающих появление s новых алгоритмических языков, а также микроЭВМ и персональных | ЭВМ, практически нет. Предлагаемая читателям книга восполнит этот
| пробел.
| Книга Б. Банда состоит из семи глав, в которых рассмотрены симп-» лекс-метод и улучшенный симплекс-метод, решение транспортной задачи и задачи о назначениях. Кроме того, в ней обсуждаются вопросы устойчивости и двойственности. Книга написана в расчете на читателя, не знакомого с линейным программированием. Для ее понимания требуются только знание языка Бейсик и знакомство с теорией матриц.
Отличительной особенностью книги является ее прикладной характер. Автор не только подробно описывает математический аппарат решения задачи, но и предлагает строгий алгоритм решения, а затем приводит программу на языке Бейсик с описанием ее особенностей. Такая форма изложения удобна и для обучения, и для получения справочного материала. Все более широкое распространение персональных ЭВМ, для которых основным языком программирования является Бейсик, будет способствовать росту интереса к программам, приведенным в книге. Большое количество примеров значительно упрощает усвоение мате-* риала. Приведенные в конце каждой главы упражнения дают возможность самостоятельно опробовать программы, приведенные в книге, и получить практические навыки решения задач линейного программирования. Результаты, полученные на разных ЭВМ, могут несколько отличаться от приведенных в книге из-за различий в разрядности машин и программном обеспечении.
ДОПОЛНИТЕЛЬНЫЙ СПИСОК ЛИТЕРАТУРЫ
1. Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование. Теория, методы и приложения. - М.: Наука, 1969. - 424 с.
2. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. - М.:Наука, 1976. - 191 с.
3. Булавский В. А., Звягина Р. А., Яковлева М. А. Численные методы линейного программирования/ Под ред. Л. В. Канторовича. - М.: Наука, 1977. - 367 с.
4. Раскин Л. Г., Кириченко И. О. Многоиндексные задачи линейного программирования. Теория, методы,приложения.- М.: Радио и связь, 1982. - 239 с.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода............................5
Дополнительный список литературы..........................5
Предисловие.........................................6
Глава 1. ОСНОВНЫЕ ИДЕИ................................8
1.1. Введение......................................8
1.2. Графическое решение двухмерных задач..................11
1.3. Стандартная форма задач линейного программирования........15
1.4. Обобщение на случай л переменных.....................17
1.5. Основные результаты линейного программирования..........18
1.6. Упражнения....................................22
Глава 2. СИМПЛЕКС-МЕТОД..............................25
2.1. Симплекс-метод при заданном начальном допустимом базисном решении......................................25
2.2. Реализация симплекс-метода на ЭВМ....................32
2.3. Порождение начального базисного допустимого решения.......38
2.4. Полное изложение симплекс-метода....................43
2.5. Проблемы вырождения............................50
2.6. Упражнения....................................55
Глава 3. АНАЛИЗ УСТОЙЧИВОСТИ РЕШЕНИЯ..................60
3.1. Обращение базиса и симплекс-множители.................60
3.2. Что получается при изменении задачи....................64
3.3. Двойственный симплекс-метод........................70
3.4. Упражнения....................................77
Глава 4. ТРАНСПОРТНАЯ ЗАДАЧА..........................82
4.1. Постановка задачи и ее решение.......................82
4.2. Алгоритм последовательного улучшения плана..............88
4.3. Дисбаланс и вырожденность в транспортной задаче...........92
4.4. Постановка транспортной задачи на ЭВМ..................97
4.5. Упражнения.........,.........................108
Глава 5. ЗАДАЧА О НАЗНАЧЕНИЯХ........................ 112
5.1. Введение.................................... 112
5.2. Метод решения Мака............................. 113
5.3. Реализация метода Мака на ЭВМ...................... 119
5.4. Упражнения................................... 123
Глава 6. УЛУЧШЕННЫЙ СИМПЛЕКС-МЕТОД................... 126
6.1. Улучшенный симплекс-алгоритм......................126
6.2. Инициализация алгоритма..........................133
6.3. Еще раз о вырожденности..........................135
6.4. Программа для улучшенного симплекс-метода.............139
6.5. Упражнения...................................148
Глава 7. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ ... 152
7.1. Прямая и двойственная задачи....................... 152
7.2. Теоремы двойственности.......................... 156
7.3. Анализ полученных результатов с точки зрения двойственности . . 162
7.4. Упражнения................................... 167
Рекомендации для дальнейшего чтения....................... 168
Список литературы................................... 168
Приложение....................................... 169
Ответы к упражнениям................................ 170