Учебное пособие подготовлено в соответствии с требованиями Государственного образовательного стандарта.
Рассматриваются следующие темы: построение математических моделей задач линейного программирования, графическое решение задач с двумя переменными, симплекс-метод, теория двойственности, метод потенциалов решения транспортной задачи, паросочетания, потоки в сетях, венгерский алгоритм решения задач о назначениях и транспортной задачи. Изложение теоретического материала сопровождается большим количеством подробно разобранных примеров решения задач, что облегчает усвоение доказательств теорем и работы алгоритмов.
Для студентов технических и социально-экономических специальностей вузов всех форм обучения.
Author(s): Палий И.А.
Series: Техническое образование
Publisher: Эксмо
Year: 2008
Language: Russian
Pages: 257
City: М.
Введение......Page 8
1.1. Математическая модель задачи линейноrо проrраммировавия......Page 10
1.2. Примеры построения математических моделей задач линейного программирования......Page 11
1.3. Задачи......Page 22
2.1. Графическое решение ЗЛП с двумя переменными......Page 37
2.2. Понятие об анализе на чувствительность......Page 44
2.3. Задачи......Page 56
3.1. Определение канонической формы ЗЛП......Page 65
3.2. Приведение произвольной ЗЛП к каноническому виду......Page 66
3.3. Решение системы линейных уравнений по методу Гаусса (методу исключения неизвестных)......Page 70
3.4. Опорные решения......Page 73
3.5. Переход от одного опорного решения к другому......Page 74
3.6. Вырожденные и невырожденные опорные решения......Page 77
3.7. Выражение целевой функции Z через свободные переменные. Оценки свободных переменных......Page 78
3.8. Анализ значений целевой функции Z, выраженной через свободные переменные. Признак неограниченности целевой функции в допустимой области......Page 82
3.9. Анализ значений целевой функции Z, выраженной через свободные переменные. Признак оптимальности опорного решения......Page 86
3.10. Теорема о достижимости оптимального значения целевой функции ЗЛП на опорном решении......Page 91
3.11. Задачи......Page 98
4.1. Описание симплекс-метода......Page 102
4.2. Получение исходного ОР. Метод искусственного базиса......Page 103
4.3. Об альтернативных оптимальных решениях ЗЛП......Page 107
4.4. Об анализе на чувствительность......Page 109
4.5. Задачи......Page 115
5.1. Определение пары двойственных задач......Page 119
5.2. Несколько замечаний об умножении матриц......Page 123
5.4. Теоремы двойственности......Page 125
5.5. Двойственный симплекс-метод......Page 137
5.6. Двойственность и анализ на чувствительность......Page 140
Включение в исходную модель дополнительных переменных......Page 143
Включение дополнительных ограничений......Page 144
5.7. Задачи......Page 145
6.1. Математическая модель транспортной задачи......Page 163
6.2. Методы получения исходного допустимого решения ТЗ......Page 166
6.3. Задача, двойственная к ТЗ. Соотношения двойственности и описание метода потенциалов......Page 168
6.4. Циклы в матрице......Page 174
6.5. Описание метода потенциалов......Page 183
6.6. Еще один пример (блокирование перевозок)......Page 184
6.7. Задачи......Page 187
7.1. Определения и примеры......Page 202
7.2. Основная теорема о наибольших паросочетаниях......Page 204
7.3. Наибольшее паросочетание в двудольном графе......Page 206
7.4. Алгоритм отыскания увеличивающей цепи для паросочетания в двудольном графе......Page 209
7.5. Задача об оптимальных назначениях......Page 214
8.1. Потоки в сетях......Page 222
8.2. Разрезы......Page 224
8.3. Теорема Форда-Фалкерсона о максимальном потоке и минимальном разрезе......Page 227
8.4. Алгоритм Форда-Фалкерсона решения задачи о максимальном потоке (метод расстановки пометок)......Page 231
8.5. Алгоритм Форда-Фалкерсона для транспортной сети, имеющей вид двудольного графа......Page 235
8.6. Венгерский алгоритм решения транспортной задачи......Page 241
8.7. Задачи......Page 252
Литература......Page 256
