Книга: Черников Ю. Г. «Системный анализ и исследование операций»

Серия: "Высшее горное образование"

Изложено введение в системный анализ и методологию исследования операций. Рассмотрены основные разделы исследования операций: линейное, целочисленное и динамическое программирование, теория игр и транспортные задачи линейного программирования. Приведены примеры решения задач с использованием современных пакетов прикладных программ, Java Applets и без их применения. Дано решение задач линейного программирования с использованием языка моделирования AMPL.
Для студентов, обучающихся по направлениям 552800 и 230100 «Информатика и вычислительная техника» по специальности 230102 «Автоматизированные системы обработки информации и управления».

Содержание:

Предисловие...... 5 Гпава 1. Введение в системный анализ...... 9 1. 1. Понятия и определения системного анализа...... 11 1. 2. Классификация систем...... 19 1. 3. Определение понятий «управление» и «система управления». Структура системы управления...... 24 1. 4. Этапы системного анализа и их детализация...... 26 Контрольные вопросы и задания...... 36 Глава 2. Методология исследования операций...... 37 2. 1. Общая характеристика исследования операций. Предмет, цели и задачи исследования операций...... 39 2. 2. Основные понятия исследования операций...... 41 2. 3. Структура математической модели операции...... 45 2. 4. Этапы исследования операций...... 53 Контрольные вопросы и задания...... 53 Глава 3. Линейное программирование...... 55 3. 1. Определения и допущения линейного программирования...... 57 3. 2. Задача оптимального распределения ресурсов (сырья). Экономическая интерпретация...... 58 3. 3. Математическая модель общей задачи линейного программирования и формы ее постановки...... 60 3. 4. Симплексный метод решения задачи линейного программирования...... 63 3. 5. Содержательная и математическая постановки конкретной задачи оптимального распределения ресурсов (сырья)...... 72 3. 6. Решение конкретной задачи оптимального распределения ресурсов (сырья)...... 75 3. 7. Решение задачи линейного программирования с использованием пакета прикладных программ...... 84 3. 8. Математическая постановка расширенной задачи линейного программирования. Метод искусственного базиса (М-метод)...... 98 3. 9. Двойственный симплексный метод...... 101 3. 10. Модифицированный симплексный метод...... 102 3. 11. Методы внутренней точки...... 102 3. 12. Модели параметрического линейного программирования...... 111 3. 13. Модели дробно-линейного программирования...... 113 3. 14. Многокритериальные задачи линейного программирования...... 113 3. 15. Классы и примеры задач, решаемых методами линейного программирования...... 113 Контрольные вопросы и задания...... 122 Глава 4. Двойственность в линейном программировании...... 125 4. 1. Содержательная и математическая постановки задачи, двойственной к общей задаче оптимального распределения ресурсов (сырья). Экономическая интерпретация...... 127 4. 2. Математическая постановка общей двойственной ЗЛП. Правила перехода от прямой ЗЛП к двойственной...... 128 4. 3. Составление модели задачи, двойственной к конкретной задаче оптимального распределения ресурсов (сырья)...... 130 4. 4. Решение двойственной ЗЛП...... 133 Контрольные вопросы и задания...... 137 Глава 5. Tpанспортные задачи линейного программирования (ТЗЛП)...... 139 5. 1. Содержательная и математическая постановки ТЗЛП. Экономическая интерпретация. Ее особенности...... 141 5. 2. Методы определения опорного плана...... 145 5. 3. Метод потенциалов...... 146 5. 4. Открытая модель...... 148 5. 5. Математическая модель двойственной ТЗЛП...... 150 5. 6. Решение тестовой ТЗЛП...... 151 5. 7. Решение ТЗЛП с помощью пакета прикладных программ Lindo...... 162 5. 8. Примеры ТЗЛП...... 166 Контрольные вопросы и задания...... 170 Глава 6. Целочисленное линейное программирование...... 171 6. 1. Математическая постановка целочисленной задачи линейного программирования (ЦЗЛП). Геометрическая интерпретация...... 173 6. 2. Методы отсечения...... 177 6. 3. Комбинаторные методы...... 180 6. 4. Решение ЦЗЛП методом отсечения...... 185 6. 5. Решение ЦЗЛП методом ветвей и границ (решение ЦЗЛП на базе пакета прикладных программ Lindo)...... 189 6. 6. Решение ЦЗЛП с булевыми переменными методом ветвей и границ на базе пакета прикладных программ Lindo...... 196 6. 7. Решение задачи о выборе инвестиционного проекта...... 197 6. 8. Решение задачи о назначении (выборе)...... 203 6. 9. Содержательная и математическая постановки задачи о коммивояжере...... 205 6. 10. Примеры содержательной постановки задач, решаемых методами целочисленного программирования...... 207 Контрольные вопросы и задания...... 210 Глава 7. Динамическое программирование...... 213 7. 1. Характеристика метода динамического программирования...... 215 7. 2. Основные положения динамического программирования...... 219 7. 3. Принцип оптимальности. Основное функциональное уравнение Беллмана...... 222 7. 4. Свойства задач, решаемых методом динамического программирования...... 225 7. 5. Этапы решения задач методом динамического программирования. Алгоритм обратной прогонки...... 226 7. 6. Содержательная и математическая постановки задачи оптимального распределения финансовых ресурсов...... 228 7. 7. Составление уравнения Беллмана для задачи определения кратчайшего расстояния...... 230 7. 8. Решение задачи определения кратчайшего расстояния...... 233 7. 9. Решение задачи определения кратчайшего расстояния на базе Java Applet...... 237 7. 10. Решение задачи об инвестициях методом динамического программирования...... 242 7. 11. Задача о рюкзаке...... 252 Контрольные вопросы и задания...... 254 Глава 8. Задачи в сетевой постановке...... 255 8. 1. Постановка и алгоритм решения задачи о максимальном потоке на сети...... 258 8. 2. Алгоритм Форда и Фалкерсона...... 258 8. 3. Решение задачи определения максимального потока на сети...... 260 Контрольные вопросы и задания...... 266 Глава 9. Теория игр...... 267 9. 1. Стратегические матричные игры...... 269 9. 2. Статистические игры...... 297 9. 3. Кооперативные игры...... 314 Контрольные вопросы и задания...... 323 Глава 10. Программное обеспечение задач линейного программирования...... 325 10. 1 Характеристика зарубежных библиотек программ по вычислительной математике и оптимизации...... 327 10. 2. Характеристика отечественных библиотек по оптимизации...... 332 10. 3. Решение задач линейного программирования с использованием языка моделирования AMPL...... 335 Контрольные вопросы и задания...... 365 Список литературы...... 366

Издательство: "Московский государственный горный университет" (2006)

ISBN: 5741804241