Палий И. А. Линейное программирование ОНЛАЙН


Оглавление
ВВЕДЕНИЕ…………………………………..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



Читать онлайн
скачать бесплатно


Теги:
линейное программирование, венгерский алгоритм, Палий, паросочетания, построение математических моделей, примеры решения задач

Коментарі до Палий И. А. Линейное программирование ОНЛАЙН