- •Математические методы исследования операций и теории иГр
- •Введение
- •Глава 1. Задачи линейного программирования
- •1. Постановка задачи линейного программирования (злп)
- •2. Графический метод решения злп
- •3. Симплекс – метод решения злп
- •Метод искусственного базиса
- •Двойственные злп
- •Двойственный симплекс-метод
- •Алгоритм двойственного симплекс-метода.
- •Метод ветвей и границ решения задачи цлп
- •Алгоритм метода ветвей и границ
- •Оптимальность по Парето
- •Множество Парето
- •Постановка задачи
- •Метод идеальной точки
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 2. Теория игр
- •1. Основные понятия теории игр
- •Принцип доминирования
- •2. Задачи теории игр и линейное программирование
- •3. Игры с природой
- •Применение матричных игр в прикладных задачах
- •Переговоры о заключении контракта между профсоюзом и администрацией
- •Локальный конфликт
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 3. Имитационное моделирование
- •Основные понятия
- •Типы имитационных моделей.
- •Принципы построения дискретных имитационных моделей
- •Метод Монте-Карло (метод статистических испытаний)
- •Применение имитационных моделей в системах массового обслуживания
- •Вопросы для повторения.
- •Глава 4. Сетевое планирование
- •1. Сетевой график
- •Оптимизация пути на сети
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Заключение
- •Библиографический список
- •Оглавление
- •3 94026 Воронеж, Московский просп., 14
Вопросы для повторения.
Линейное программирование. Математическая модель.
Общая задача линейного программирования. Управляющие переменные. Целевая функция. Решение задачи линейного программирования.
Основная (каноническая) задача линейного программирования. Допустимое решение. Область допустимых решений. Оптимальное решение задачи линейного программирования.
Графический метод решения задачи линейного программирования.
Симплекс-метод решения задачи линейного программирования, его геометрический смысл. Правила перехода к канонической форме. Стандартная форма задачи линейного программирования. Опорный план задачи линейного программирования, признак его оптимальности. Вырожденный и невырожденный план.
Устройство симплекс-таблицы. Разрешающий элемент, разрешающие строка и столбец. Правила перехода к новой симплекс-таблице.
Метод искусственного базиса. Расширенная ЗЛП. Искусственный базис. Искусственные переменные. Алгоритм метода искусственного базиса.
Двойственная задача линейного программирования. Двойственная пара задач линейного программирования. Правила составления двойственной задачи по отношению к исходной. Связь между решениями прямой и двойственной задач. Теоремы двойственности. Геометрическая интерпретация двойственных задач.
Соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи. Нахождение симплекс-методом оптимального решения двойственной задачи.
Двойственный симплекс-метод. Псевдоплан. Теоремы о псевдоплане. Алгоритм двойственного симплекс-метода.
Целочисленное (дискретное) линейное программирование (ЦЛП). Математическая модель задачи ЦЛП. Алгоритм метода Гомори. Дробная часть числа. Геометрическая интерпретация метода Гомори (метод отсечения).
Алгоритм метода ветвей и границ решения задачи ЦЛП.
Внутренние и граничные точки множества и их классификация. Граница множества. Граница (множество) Парето.
Точка утопии. Метод идеальной точки.
Задачи для самостоятельного решения.
Мебельная фабрика выпускает стулья двух типов. На изготовление одного стула 1-го типа, стоящего 8 денежных единиц расходуется 2м. досок стандартного сечения, 0,5м2 обивочной ткани и 2 человека – часа рабочего времени. Аналогичные данные для стульев 2-го типа даются цифрами: 12 денежных единиц, 4м., 0,25 м2. и 2,5 человеко-часа. В наличии имеются: 440м. досок, 65м2. обивочной ткани, 320 человеко-часов рабочего времени. Какие стулья и в каком количестве нужно выпустить, чтобы стоимость продукции была максимальной? Решить задачу графическим методом.
При переработке некоторого лекарственного сырья возможно использование одной из двух технологий. При переработке сырья по 1-ой технологии выход полезного продукта составляет 150/0, на производство 1кг продукта затрачивается 8 человеко-часов и 12 денежных единиц. При переработке сырья по 2-ой технологии выход полезного продукта составляет 100/0, на производство 1кг продукта затрачивается 14 человеко-часов и 9 денежных единиц. Фонд заработной платы не превышает 3960 денежных единиц, трудовые ресурсы 4480 человеко-часов. Масса лекарственного сырья 440кг. Какое количество сырья надо переработать, чтобы получит максимальный выход полезного продукта? Решить задачу графическим методом.
На звероферме могут выращиваться чёрно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется 3 вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в таблице. В ней же указано общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.
Вид корма
|
Количество единиц корма, которое ежедневно должны получать |
Общее количество корма |
|
лисица |
песец |
||
I II III |
2 4 6 |
3 1 7 |
180 240 426 |
Прибыль от реализации одной шкурки (д. е.) |
16 |
12 |
Определить графическим методом, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.
Решить задачу 1 симплекс-методом.
Решить задачу 2 симплекс-методом.
Предприятие рекламирует свою продукцию с использованием четырёх источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что эти средства приводят к увеличению прибыли соответственно на 10, 5, 7 и 4 у. е., в расчёте на 1 у. е., затраченную на рекламу. На рекламу выделено 50000 у. е. Администрация предприятия не намерена тратить на телевидение более 40 %, на радио и газеты – более 50 % от общей суммы выделенных средств. Как следует предприятию организовать рекламу, чтобы получить максимальную прибыль? Решить задачу симплекс-методом.
Решить задачу симплекс-методом. Предприятие электронной промышленности выпускает две модели радиоприёмников, причём каждая модель производится на отдельной технологической линии. Суточный объём производства первой линии – 75 изделий. На радиоприёмник первой модели расходуется 10 однотипных элементов электронных схем, на радиоприёмник второй модели – 8 таких же элементов. Максимальный суточный запас используемых элементов равен 800 единицам. Прибыль от реализации одного радиоприёмника первой и второй модели равна 30 и 20 ден. ед. соответственно. Определите оптимальные суточные объёмы производства первой и второй моделей, чтобы прибыль была максимальной.
Используя метод искусственного базиса, найдите решение задачи линейного программирования:
Для задачи, состоящей в определении максимального значения функции при условиях
составить двойственную задачу и найти решение обеих задач графическим способом.
Методом Гомори найти максимальное значение функции при условиях
Дать геометрическую интерпретацию решения задачи.
Методом ветвей и границ найти максимальное значение функции при условиях
На множестве
заданы две линейные функции:
Требуется найти решение задачи и , при условии, что точка утопии M*имеет координаты (5,7).