Банди Б. Основы линейного программирования: Пер. сангл. — М.: Радио и связь, 1989. - 176 с: ил.
В книге английского автора освещены основные положения и методы линейного программирования. Рассмотрены симплекс-метод и его реализация на ЭВМ, проблема вырожденности, анализ чувствительности и двойственный симплекс-метод, транспортная задача, задача о назначении, двойственность в линейном программировании и др. Алгоритмы решения различных задач линейного программирования реализованы на языке Бейсик, причем программы несложно перевести на такие языки, как Фортран или Паскаль.
Для инженерно-технических работников, связанных с применением линейного программирования.
ОГЛАВЛЕНИЕ
Предисловие редактора перевода............................S
Дополнительный список литературы...........................
Предисловие..........................................
Глава 1. ОСНОВНЫЕ ИДЕИ................................8
1.1. Введение......................................8
1.2. Графическое решение двухмерных задач..................11
1.3. Стандартная форма задач линейного программирования........15
1.4. Обобщение на случай и переменных.....................17
1.5. Основные результаты линейного программирования.......... 18
1.6. Упражнения....................................22
Глава 2. СИМПЛЕКС-МЕТОД..............................25
2.1. Симплекс-метод при заданном начальном допустимом базисном решении......................................2 5
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
