- •Введение
- •1.Основные понятия и принципы моделирования Определение моделирования
- •1.1. Принципы построения математических моделей
- •Обобщенная математическая модель
- •1.2. Оценка эффективности стратегий
- •1.3. Классификация задач исследования операций
- •1.4. Модели выбора решений в условиях определенности
- •2. Математическое программирование
- •Формы записи задач линейного программирования
- •2.1. Постановка задачи линейного программирования.
- •Решение задачи лп графическим методом :
- •Геометрическая интерпретация и графический метод решения задачи линейного программирования
- •3. Геометрическая интерпретация задач линейного программирования
- •2.1.1 Симплексный метод решения задач линейного программирования
- •2.1.2Алгоритм симплекс метода отыскания оптимального решения задачи линейного программирования
- •2.1.3Примеры решения задач симплексным методом Пример 1. Найти максимум целевой функции
- •§4. Решение задачи лп двухфазным симплекс-методом
- •2.1.4 Задачи для закрепления полученных знаний
- •2.1.5. Двойственная задача
- •2.1.6Основные теоремы двойственности
- •2.1.7. Транспортная задача
- •2.1.8. Первоначальное распределение поставок
- •2.1.9. Правило "Северо-западного угла"
- •2.1.11. Метод потенциалов.
- •2.2. Модели динамического программирования
- •2.2.1. Постановка задачи динамического программирования
- •2.2.2. Принцип оптимальности и математическое описание динамического процесса управления
- •2.2.3. Оптимальное распределение инвестиций
- •2.2.3. Выбор оптимальной стратегии обновления оборудования
- •2.3. Сетевое моделирование. Методы и модели теории графов и сетевого моделирования
- •2.3.1. Элементы теории графов
- •2.3.2. Сетевое планирование и управление
- •2.3.3. Основные понятия и терминология, используемые в сетевом планировании
- •2.3.4. Порядок построения сетевых графиков
- •2.3.5. Правила построения сетевого графика.
- •2.3.6. Основные понятия сетевого графика
- •2.3.7. Временные параметры сетевых графиков
- •3. Задачи в условиях неопределенности
- •3.1. Системы массового обслуживания
- •3.1.1. Структура простейшей системы массового обслуживания.
- •3.1.2. Система массового обслуживания с отказом. Одноканальная система.
- •3.1.3. Системы массового обслуживания с ожиданием.
- •Имитационное моделирование
- •3.2.1. Основы имитационного моделирования
- •3.2.2. Метод статистических испытаний
- •3.2.3. Формирование случайных чисел на эвм
- •3.3. Модели прогнозирования. Задачи управления запасами
- •3.3.1.Основные понятия управления запасами
- •3.3.2. Классификация моделей управления запасами
- •3.3.3. Складская система
- •3.3.4. Спрос на товары
- •3.3.5. Возможность пополнения запасов
- •3.3.6. Затраты на функционирование системы управления запасами
- •3.3.7. Стратегия управления запасами
- •3.3.8. Основные детерминированные модели. Простейшая модель управления запасами ( модель 1)
- •3.3.9. Модель с учетом дефицита (модель 2)
- •С помощью этих соотношений исключим т1, т2, т и получим
- •Оптимальное значение
- •График зависимости уровня запаса на складе от времени
- •Методы и модели теории игр
- •3.4.1. Основные понятия теории игр
- •3.4.2. Постановка игровых задач
- •3.4.3. Методы решения игровых задач
- •3.4.4. Метод линейного программирования
- •Литература
2.1.3Примеры решения задач симплексным методом Пример 1. Найти максимум целевой функции
F =-5Х1+4Х2-2Х3
При ограничениях:
3Х1+2Х2-4Х3 <=5
-2Х1+Х2-Х3 <=2
4Х1+3Х2-3Х3<=7
Х1>=0, Х2>=0, Х3>=0
Решение
Преобразуем систему неравенств в систему уравнений, добавив в левую часть дополнительные переменные.
3Х1+2Х2-4Х3 +Х4=5
-2Х1+Х2-Х3 +Х5=2
4Х1+3Х2-3Х3+Х6 =7
Построим первое базисное решение в виде симплекс-таблицы (см. табл. 1):
Таблица 1. Таблица 2.
|
-Х1 |
-Х2 |
-Х3 |
С. ч. |
|
|
-Х1 |
-Х5 |
-Х3 |
С. ч. |
Х4 |
3 |
2 |
-4 |
5 |
Х4 |
7 |
-2 |
-2 |
1 |
|
Х5 |
-2 |
1 |
-1 |
2 |
Х2 |
-2 |
1 |
-1 |
2 |
|
Х6 |
4 |
3 |
-3 |
7 |
Х6 |
10 |
-3 |
0 |
1 |
|
F |
5 |
-4 |
2 |
0 |
F |
-3 |
4 |
-2 |
8 |
Перерасчет таблиц производится в соответствии с вышеизложенными правилами, а именно:
В таблице 1 в F строке находится отрицательный элемент «-4». Ему соответствует разрешающий столбец.
В этом столбце находится элемент по принципу минимальная величина из (5 /2, 2/1, 7/3). Этому элементу соответствует разрешающая строка.
В таблице 2:
эта строка остается без изменений;
элементы столбца меняют знаки на противоположные;
остальные элементы таблицы 2 получаются по формуле (4).
Таблица 3.
|
-Х6 |
-Х5 |
-Х3 |
С. ч. |
Х4 |
-7 |
1 |
-20 |
3 |
Х2 |
2 |
4 |
-10 |
22 |
Х1 |
1 |
-3 |
0 |
1 |
F |
5 |
31 |
-20 |
83 |
Так как разрешающий столбец не имеет положительных элементов, то значение целевой функции стремится к бесконечности (F->∞).
Пример 2.
Найти максимальное значение функции:
F =Х1-Х2
При ограничениях:
-Х1+Х2<=2
Х1-3Х2 <=3
Х1+Х2 <=5
Х1>=0, Х2>=0
Решение
Преобразуем систему неравенств в систему уравнений, добавив в левую часть дополнительные переменные.
-Х1+Х2+ Х3 =2
Х1-3Х2 +Х3 =3
Х1+Х2 +Х5=5
Таблица 1. Таблица 2
|
-Х1 |
-Х2 |
С.ч. |
|
|
-Х4 |
-Х2 |
С.ч |
Х3 |
-1 |
1 |
2 |
Х3 |
1 |
-2 |
5 |
|
Х4 |
1 |
-3 |
3 |
Х1 |
1 |
-3 |
3 |
|
Х5 |
1 |
1 |
5 |
Х5 |
-1 |
4 |
2 |
|
F |
-1 |
1 |
0 |
F |
1 |
-2 |
3 |
Таблица 3. Таблица 4.
|
-Х4 |
-Х5 |
С.ч. |
Разделим на 4 |
|
-Х4 |
-Х5 |
С.ч |
Х3 |
2 |
2 |
24 |
Х3 |
1/2 |
1/2 |
6 |
|
Х1 |
1 |
3 |
18 |
Х1 |
1/4 |
3/4 |
9/2 |
|
Х2 |
-1 |
1 |
2 |
Х2 |
-1/4 |
1/4 |
1/2 |
|
F |
2 |
2 |
16 |
F |
1/2 |
1/2 |
4 |
Результат Х1=9/2, Х2=1/2, Х3=6, Х4= Х5=0
Максимальное значение F=4
Проверка:
Подставим значения переменных в исходный вид функции:
F =4,5-0,5=4