Костевич Л. С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л.С. Костевич. — Мн.: , 2003. — 424 с.
Доступно изложено применение линейных, целочисленных, динамических, параметрических, игровых методов и алгоритмов оптимизации в информационных технологиях управления. Рассмотрены вопросы эффективного сетевого планирования, построения оптимальных маршрутов и т.д. Теоретический материал сопровождается примерами решения конкретных задач. Некоторые решения реализованы с помощью электронных таблиц Microsoft Excel.
Для студентов вузов, обучающихся по экономическим специальностям, экономистов, менеджеров.
ОГЛАВЛЕНИЕ
Введение.................................................................................. 3
Раздел I. Предмет н задачи математического программирования
1. Предмет, метод и задачи математического программирования в среде информационных технологий.............. 7
1.1. Основные понятия информационных технологий........................................... 7
1.2. Предмет, метод и примеры задач математического программирования......... 9
1.3. Некоторые элементы информационных технологий Microsoft Excel 2000............14
1.3.1. Запуск и основные компоненты Microsoft Excel............................................14
Запуск и компоненты экрана........................................................................14
Панели инструментов...............................................................................17
Рабочий лист, ячейки..................................................................18
1.3.2. Краткие сведения о справочной системе Excel..............................................19
Вызов справки..............................................................................19
Получение подсказки с помощью команды «Что это такое?».......................................20
Отображение полезных советов......................................................................20
Всплывающие подсказки.............................................................................21
Автоматическое получение справки........................................................21
1.3.3. Работа с файлами.........................................................................21
Создание файла....................................................................21
Сохранение рабочей книги............................................21
Закрытие рабочей книги........................................................................22
Открытие рабочей книги...................................................................22
Удаление рабочей книги...............................................................................22
Защита файлов, их открытие и снятие защиты.............................................22
1.3.4. Ввод, форматирование, редактирование и копирование информации..........23
Выделение ячеек....................................................................23
Ввод информации............................................................................24
Ввод формул и функций..........................................................................25
Использование функций Microsoft Excel.....................................................................25
Форматирование......................................................................................26
Редактирование....................................................................................27
Копирование и перенос информации....................................................................28
1.3.5. Вывод информации на печать..................................................................29
Подбор шрифта............................................................................29
Цвет фона............................................................................29
Выравнивание текста..........................................................................29
Параметры страницы..........................................................................30
Печать документа..............................................................................30
1.4. Применение Excel в математических основах оптимальных решений........................30
1.4.1. Математические основы оптимальных решений....................................................30
1.4.2. Решение прикладных задач средствами Excel...........................................................38
Раздел II. Методы оптимальных решений в информационных технологиях управления
2. Математические методы линейной оптимизации................................................................47
2.1. Общая задача линейной оптимизации и методы ее решения......................................................47
2.1.1. Формы записи задач линейной оптимизации............................................. 47
2.1.2. Геометрическая интерпретация и графический метод решения задач линейной оптимизации..................... 49
2.1.2.1. Геометрическая интерпретация задачи линейной оптимизации.................. 50
2.1.2.2. Графический метод решения...................................................................... 52
2.1.3. Симплекс-метод решения задач линейной оптимизации........................... 54
2.1.3.1. Алгоритм нахождения опорного решения...................................................... 56
2.1.3.2. Алгоритм нахождения оптимального решения.............................................. 60
2.1.3.3. Вырожденные задачи линейной оптимизации............................................... 66
2.1.3.4. Решение общей задачи линейной оптимизации............................................ 69
2.1.4. Информационные технологии линейной оптимизации............................. 73
2.2. Двойственность в линейной оптимизации........................................................ 78
2.2.1. Постановка и правила построения двойственной задачи........................... 78
2.2.2. Основные теоремы двойственности............................................................. 84
2.2.3. Двойственный симплекс-метод.................................................................... 93
2.2.4. Анализ решения задач линейной оптимизации........................................... 98
2.2.5. Информационные технологии экономико-математического анализа
решений оптимизационных задач...............................................................103
Информационные технологии Simplex в послеоптимизационном анализе............. 103
Информационные технологии Excel в линейной оптимизации................................ 107
2.3. Транспортная задача................................................................111
2.3.1. Постановка и математическая модель транспортной задачи......................111
2.3.2. Транспортная задача с нарушенным балансом............................................114
2.3.3. Методы построения исходного опорного решения.....................................115
2.3.3.1. Метод минимальной стоимости............................................... 117
2.3.3.2. Метод Фогеля.................................................................... 118
2.3.4. Метод потенциалов нахождения оптимального решения...........................119
2.3.5. Дополнительные условия в транспортных задачах......................................123
2.3.5.1. Запрет перевозок от i-го поставщика j-му потребителю............................. 123
2.3.5.2. Фиксированная поставка......................................................... 124
2.3.5.3. Нижние границы на поставки......................................................................... 124
2.3.5.4. Верхние границы на поставки......................................................................... 124
2.3.5.5. Максимизация функции в моделях транспортного типа............................... 124
2.3.6. Экономический смысл двойственных оценок.............................................125
2.3.7. Информационные технологии оптимизации перевозок.............................125
Применение информационных технологий пакета QSB (Quantitative System for Business)................................... 125
Применение информационных технологий Excel..................................................... 127
3. Целочисленная оптимизация...............................................................................132
3.1. Постановка задачи..............................................................................................132
3.2. Метод Гомори решения задач целочисленной линейной оптимизации.........133
3.3. Метод ветвей и границ решения задач целочисленной линейной оптимизации.......................................................................................................138
3.4. Информационные технологии нахождения целочисленных оптимальных решений задач.............................................................................142
4. Задача коммивояжера (построение кольцевых маршрутов)....................................148
4.1. Постановка задачи..............................................................................................148
4.2. Метод ветвей и границ решения задачи коммивояжера...................................150
4.3. Информационные технологии построения кольцевых маршрутов.................158
5. Параметрическое программирование...................................................................162
5.1. Постановка и геометрическая интерпретация задачи......................................162
5.2. Графическое решение задачи.............................................................................164
5.3. Аналитическое решение задачи.........................................................................166
6. Динамическое программирование........................................................................173
6.1. Многошаговые процессы в динамических задачах...........................................173
6.2. Принцип оптимальности и рекуррентные соотношения.................................174
6.3. Вычислительная схема........................................................................................177
6.4. Планирование производственной программы..................................................181
6.5. Применение информационных технологий...................................................... 186
Раздел IIІ. Информационные технологии в элементах теории графов
и сетевом управлении
7. Некоторые сведения из теории графов.................................................................193
7.1. Понятия и определения......................................................................................193
7.2. Способы задания графа......................................................................................196
7.2.1. Матрицы смежности и инцидентности........................................................196
7.2.2. Задание орфафа с помощью списка вершин и информации о том,
с какими вершинами они соединены дугами..............................................199
7.2.3. Задание орфафа с помощью дуг и информации о том, на какие дуги
они опираются...............................................................................................199
7.3. Разбиение элементов орграфа по рангам...........................................................200
7.3.1. Отношение строгого порядка в орграфе......................................................200
7.3.2. Нахождение рангов вершин на чертеже орграфа.........................................200
7.3.3. Метод Демукрона нахождения рангов вершин орграфа.............................201
7.3.4. Нахождение рангов дуг орграфа...................................................................204
7.4. Применение информационных технологий Excel............................................206
8. Информационные технологии сетевого планирования и управления......................208
8.1. Сетевой график комплекса операций и правила его построения....................208
8.2. Расчет временных параметров сетевого графика..............................................213
8.3. Вероятностные сети............................................................................................216
8.4. Оптимизация комплекса операций....................................................................222
8.4.1. Оптимизация комплекса операций по времени..........................................222
8.4.2. Оптимизация комплекса операций по стоимости.......................................234
8.4.3. Оптимизация комплекса операций по ресурсам.........................................250
8.5. Информационные технологии расчета параметров и оптимизации сетевых графиков....................................263
Информационная технология расчета проектов — PERT......................................... 263
Информационные технологии системы анализа проектов — СРМ.......................... 264
9. Потоки в сетях..................................................................................................266
9.1. Постановка задачи о максимальном потоке......................................................266
9.2. Алгоритм решения задачи о максимальном потоке..........................................267
9.2.1. Теорема Форда-Фалкерсона........................................................................267
9.2.2. Алгоритм Форда нахождения максимального потока.................................269
9.2.3. Сведение задачи с несколькими источниками и стоками к задаче
с одним источником и одним стоком..........................................................274
9.3. Задача о потоке минимальной стоимости.........................................................275
9.3.1. Постановка задачи.........................................................................................275
9.3.2. Задача о кратчайшем маршруте....................................................................276
9.3.3. Алгоритм Басакера-Гоуэна нахождения оптимального потока.................278
9.4. Информационные технологии сетевой оптимизации....................................281
Раздел IV. Игровые методы в информационных технологиях оптимальных решений
10. Методы решения матричных игр........................................................................287
10.1. Предмет и основные понятия теории игр........................................................287
10.2. Решение матричных игр с нулевой суммой.....................................................290
10.2.1. Принцип минимакса и максимина............................................................290
10.2.2. Решение игр без седловых точек.................................................................293
10.2.3. Упрощение игр............................................................................................294
10.2.4. Сведение матричной игры к задаче линейной оптимизации....................296
10.3. Решение матричных игр с применением информационных технологий......301
11. Игры с природой...............................................................................................307
11.1. Понятие и постановка задачи игры с природой..............................................307
11.2. Анализ матрицы выигрышей игры с природой и построение матрицы рисков......................................308
11.3. Критерии для принятия решений в играх с природой без эксперимента......309
11.4. Целесообразность эксперимента в условиях неопределенности...................315
11.5. Информационные технологии Excel в играх с природой...............................317
Раздел V. Методы нелинейной стохастической и векторной оптимизации в информационных технологиях управления
12. Нелинейное программирование..........................................................................325
12.1. Постановка задачи и некоторые особенности ее решения.............................325
12.2. Графическое решение задачи...........................................................................332
12.3. Метод множителей Лагранжа...........................................................................335
12.4. Квадратичное программирование....................................................................337
12.5. Градиентные методы................................................................................341
12.5.1. Метод Франка-Вулфа.................................................................................342
12.5.2. Метод штрафных функций Эрроу-Гурвица..............................................345
12.6. Информационные технологии Excel решения задач нелинейного программирования..............................351
13. Стохастическое программирование....................................................................356
13.1. Характеристика задач стохастического программирования...........................356
13.2. Некоторые математические модели задач стохастического программирования................................357
13.2.1. E-постановка задачи....................................................................................357
13.2.2. Р-постановка задачи....................................................................................360
13.3. Информационные технологии решения задач стохастического программирования...............................361
13.3.1. Определение количественных характеристик и функций случайной величины..................................361
Вероятностные распределения случайных величин................................................ 362
Построение графиков............................................................................................... 363
Построение функции и графика для нормального стандартного распределения.... 366
13.3.2. Формирование исходных данных для детерминированного эквивалента задачи в Е-постановке......................368
13.3.3. Решение задачи............................................................................................372
13.3.4. Решение стохастических задач в Р-постановке.........................................373
Решение задачи с вероятностными ограничениями и заданным значением P[f(x)]...................................... 374
Решение задачи с вероятностными ограничениями и P[f(x)] max.................... 374
13.4. Стохастическая транспортная задача...............................................................377
13.4.1. Некоторые подходы к решению задачи......................................................377
14. Векторная оптимизация....................................................................................389
14.1. Методы векторной оптимизации.....................................................................389
14.1.1. Метод последовательных уступок...............................................................389
14.1.2. Метод ведущего критерия...........................................................................390
14.1.3. Метод равных и наименьших относительных отклонений.......................390
14.1.4. Метод минимакса........................................................................................395
14.2. Информационные технологии оптимизации решений по векторному критерию...................................397
Ответы........................................................................................................412
Литература..............................................................................................419
Костевич Л. С. Математическое программирование: Информационные технологии оптимальных решений
