Палий И. А. Линейное программирование. Учебное пособие / И. А. Палий. — М., 2008. — 256 с. — (Техническое образование).
Рассматриваются следующие темы: построение математических моделей задач линейного программирования, графическое решение задач с двумя переменными, симплекс-метод, теория двойственности, метод потенциалов решения транспортной задачи, паросочетания, потоки в сетях, венгерский алгоритм решения задач о назначениях и транспортной задачи.
Изложение теоретического материала сопровождается большим количеством подробно разобранных примеров решения задач, что облегчает усвоение доказательств теорем и работы алгоритмов.
Для студентов технических и социально-экономических специальностей вузов всех форм обучения.
Оглавление
ВВЕДЕНИЕ.........................................7
ГЛАВА 1
ЧТО ТАКОЕ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.............................9
1.1. Математическая модель задачи линейного программирования..........................9
1.2. Примеры построения математических моделей задач линейного программирования...........10
1.3. Задачи...................................21
ГЛАВА 2
ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ДВУМЯ ПЕРЕМЕННЫМИ........................36
2.1. Графическое решение ЗЛП с двумя переменными..............................36
2.2. Понятие об анализе на чувствительность......43
2.3. Задачи...................................55
ГЛАВА 3
ОПОРНЫЕ РЕШЕНИЯ.............................64
3.1. Определение канонической формы ЗЛП.......64
3.2. Приведение произвольной ЗЛП
к каноническому виду......................65
3.3. Решение системы линейных уравнений по методу Гаусса (методу исключения неизвестных)..............................69
3.4. Опорные решения..........................72
3.5. Переход от одного опорного решения к другому 73
3.6. Вырожденные и невырожденные опорные решения...................................76
3.7. Выражение целевой функции Z через свободные переменные. Оценки свободных переменных .. 77
3.8. Анализ значений целевой функции Z, выраженной через свободные переменные. Признак неограниченности целевой функции
в допустимой области.......................81
3.9. Анализ значений целевой функции Z, выраженной через свободные переменные. Признак оптимальности опорного решения .... 85
3.10. Теорема о достижимости оптимального значения целевой функции ЗЛП на опорном решении.................................90
3.11. Задачи....................................97
ГЛАВА 4
СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗЛП..............101
4.1. Описание симплекс-метода.................101
4.2. Получение исходного ОР. Метод искусственного базиса...............................102
4.3. Об альтернативных оптимальных решениях ЗЛП.................................106
4.4. Об анализе на чувствительность.............108
4.5. Задачи..................................114
ГЛАВА 5
ОСНОВЫ ТЕОРИИ ДВОЙСТВЕННОСТИ...........118
5.1. Определение пары двойственных задач.......118
5.2. Несколько замечаний об умножении матриц ... 122
5.3. Несколько замечаний о свойствах скалярного произведения векторов.....................124
5.4. Теоремы двойственности................... 124
5.5. Двойственный симплекс-метод..............136
5.6. Двойственность и анализ на чувствительность.. 139
Изменение коэффициентов целевой функции .. 142
Включение в исходную модель дополнительных переменных..............................142
Включение дополнительных ограничений.....143
5.7. Задачи..................................144
ГЛАВА 6
МЕТОД ПОТЕНЦИАЛОВ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ........................162
6.1. Математическая модель транспортной задачи...................................162
6.2. Методы получения исходного допустимого решения ТЗ..............................165
6.3. Задача, двойственная к ТЗ. Соотношения двойственности и описание метода потенциалов..............................167
6.4. Циклы в матрице.........................173
6.5. Описание метода потенциалов..............182
6.6. Еще один пример (блокирование перевозок) .. 183
6.7. Задачи.................................. 186
ГЛАВА 7
ПАРОСОЧЕТАНИЯ................................201
7.1. Определения и примеры...................201
7.2. Основная теорема о наибольших паросочетаниях..........................203
7.3. Наибольшее паросочетание в двудольном графе....................................205
7.4. Алгоритм отыскания увеличивающей цепи для паросочетания в двудольном графе.......208
7.5. Задача об оптимальных назначениях ........213
ГЛАВА 8
ТРАНСПОРТНАЯ ЗАДАЧА И ВЕНГЕРСКИЙ
АЛГОРИТМ ЕЕ РЕШЕНИЯ........................222
8.1. Потоки в сетях...........................222
8.2. Разрезы.................................224
8.3. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе.............227
8.4. Алгоритм Форда-Фалкерсона решения задачи о максимальном потоке (метод расстановки пометок).................................231
8.5. Алгоритм Форда-Фалкерсона для транспортной сети, имеющей вид двудольного графа....................................235
8.6. Венгерский алгоритм решения транспортной задачи...................................241
8.7. Задачи..................................252
ЛИТЕРАТУРА.....................................255
