- •Министерство образования Украины
- •Лазорин Анатолий Иванович
- •Лабораторная работа.
- •Тема: Распределительные задачи
- •Задача о назначении
- •(Экстремальная задача комбинаторного вида)
- •2.2. Общие положения
- •2.1. Постановка задачи.
- •2.2. Построение математической модели и критерий оптимизации.
- •2.3.Алгоритм метода решения – решение венгерским методом.
- •З. Подготовка и расчет контрольного примера.
- •3.1.Исходные данные и постановка задачи.
- •3.3. Построение исходной таблицы и расчет.
- •4. Подготовка и расчет варианта задания.
- •5. Отчет должен содержать.
- •6.Список используемых источников.
- •Лабораторная работа. Транспортная задача линейного программирования
- •1. Постановка задачи.
- •2. Математическая формулировка задачи.
- •3 Методы определения начального опорного плана.
- •3.1 Метод северо-западного (с-з) угла
- •3.2 Метод наименьшей стоимости.
- •3.3 Метод Фогеля.
- •4 Нахождение оптимального решения транспортной задачи методом потенциалов.
- •5. Решение транспортных задач при помощи программы "Transpo"
- •Введение исходных данных по запросам программы
- •7. Последовательность выполнения работы.
- •8. Состав отчета к лабораторной работе.
- •Лабораторная работа. Тема Задачи линейного программирования
- •Графический метод решения задач лп.
- •Симплексный метод решения задач лп.
- •Для этого в случае необходимости задача (1.1) поиска минимума сводится к задаче на поиск максимума (1.7) путем изменения знаков коэффициентов Сj
- •Правило прямоугольника
- •Пример. Решить задачу лп:
- •Метод искусственного базиса.
- •Поэтому новая таблица имеет четыре строки и шесть столбцов:
- •Лабораторная работа. Тема: Задачи упорядочения и согласования. Алгоритм Джонсона.
- •2.Общие положения
- •2.1.Постановка задачи.
- •2.2Построение математической модели и критерий оптимизации.
- •Таким образом требуется определить такую последовательность обработки, при которой
- •Например, пусть имеем порядок обработки изделий на 1-ой машине
- •3.Подготовка и расчёт контрольного примера.
- •Пример составления таблицы значений времени обработки для 3-х машин:
- •4.Подготовка и расчёт варианта задания .
- •4.2. Исходные данные контрольного примера.
- •5.Отчёт должен содержать.
- •6.Список используемых источников.
- •Лабораторная работа Задачи управления запасами. Управление запасами при случайном спросе.
- •2.Общие положения.
- •2.1.Постановка задачи и основные особенности.
- •2.2.Построение математической модели и критерий оптимизации.
- •2.3.Алгорим метода решения.
- •3.Подготовка и расчёт контрольного примера.
- •Вычисленное значение
- •4. Подготовка и расчет варианта задания.
- •5. Отчет должен содержать :
- •6. Список используемых источников
- •Лабораторная работа Тема: Состязательные задачи.
- •2.Общие положения.
- •2.1 Постановка задачи и краткие теоретические положения.
- •2.2 Построение математической модели и критерий оптимизации.
- •3.Подготовка и расчёт контрольного примера.
- •3.1 Исходные данные и постановка задачи.
- •3.2.Построение математической модели и критерия оптимизации.
- •3.3.Снижение размерности игровой матрицы и анализ на наличие седловой точки.
- •3.4.Поиск оптимального решения.
- •3.3.Анализ вариантов исследований.
- •4.Подготовка и расчёт варианта задания.
- •5.Отчёт должен содержать.
- •6.Список используемых источников.
- •Лабораторная работа. Тема: Задачи массового обслуживания Задача анализа и синтеза детерминированной одноканальной замкнутой системы массового обслуживания с ожиданием
- •Краткая характеристика объекта.
- •2.Постанавка задачи. Постановку задачи разделим на две части. В первой части выполним анализ заданной смо и расчет ее характеристик, а во второй – определим оптимальную структуру системы.
- •Очередь
- •3.Основные положения расчетов.
- •4.Построение и исследование математической модели смо.
- •Первое слагаемое критерия обозначить:
- •5.Подготовка и расчет контрольного примера.
- •6.Подготовка и расчет варианта задания.
- •7. Отчет по работе должен содержать:
- •Содержание
2.2 Построение математической модели и критерий оптимизации.
Для смешанной стратегии вероятности выигрыша стороны А и проигрыша стороны В будут:
(2.11)
Выигрыш сторона А определяется как математическое ожидание выигрыша, которое максимизирует средний выигрыш:
Y= max
т.е критерий оптимизации:
Y= max (2.12)
где Cij - значения элементов матрицы выигрышей стороны А.
2.3 Алгоритм метода решения.
Для получения оптимальных вероятностей использования стратегий A1,......, Ai,....,An (или для соответственно B1,...,Bj,....,Bm), необходимо взять соответствующие частные произведения от целевой функции, приравнять их нулю и решить систему уравнений:
(i=1,2,...,n)
(2,13)
(j=1,2,3...,m)
относительно и .
Например, дана игровая матрица в таблице 2.2
Таблица 2.2
Ai Bj |
B1 |
B2 |
A1 |
C11 |
C12 |
A2 |
C21 |
C22 |
Требуется определить оптимальные смешанные стратегии, т.е. выигрыш стороны А обеспечивается стратегией.
При этом наименьший проигрыш стороны В будет:
Математическая модель этой задачи
Y= max (2.14)
При этом : ;
а критерий оптимизации:
Y= max
Взяв частные производные и составив систему:
(2.15)
определим значения:
Подставим эти значения в (2.14) и получим максимальный средний выигрыш Ymax.
Для случая приведенного в таблице 2.2 обозначим:р1=р, тогда р2=1-р. Подставим эти значения в (2.14), взяв частные производные и решив систему уравнений получим:
= ; =
Подставим эти значения
в целевую функцию Y и получим максимальный средний выигрыш стороны А:
Ymax= (2.16)
Анализ этой формулы показывает, что при
игра становится безобидной, т.е. беспроигрышной, при этом необходимо:
(2.17)
Найденное значение Ymax составляет цену игры S, т.е.
S=Ymax, при этом a<=S<= в
т.е. применение оптимальной стратегии стороной А обеспечивает ей выигрыш при любых действиях стороны В, не меньше цены игры, поэтому:
j=1,2,...,n (2.18)
Аналогично для стороны В оптимальная стратегия должна обеспечить при любых стратегиях игрока А, проигрыш, не превышающий величину S, поэтому
i=1,2,....,m (2.19)
Таким образом, задача определения оптимальной стратегии стороны А имеет следующие ограничения:
(2. 20)
Разделим левую и правую части системы (2.20) на S, обозначим Pi/S=ti и получим:
(2. 21)
Выражение (2.9а) разделим на S и получим:
=1/S (2.22)
В результате решения игровой задачи необходимо получить для стороны А максимальное значения S, тогда выражение (2.22) можно представить в виде
Z= min (2.23)
при этом необходимо ti>=0.
Таким образом игровая задача приведена к задаче линейного программирования с целевой функцией (2.23) и ограничениях (2.21). Решая последнюю, находим значения которые составляют вектор оптимальных значений для стратегии (2.9) выигрышной стороны А.
Аналогично с (2.19) и (2.20) получим для стратегии проигрышной стороны В:
(2. 24)
Разделим левую и правые части системы (2.24) на S, обозначим /S=Uj и получим:
(2. 25)
Аналогично с (2.22) и (2.23) на основании (2.10а) получим:
U1+U2+......+Un=1/S (2.26)
W max (2.27)
Решая, находим =UjS вектор Анализируя системы ограничений (2.21) и (2.25), которые получены на основе матрицы (2.1), можно показать, что система (2.25) является двойственной по отношению к системе(2.21).
Таким образом, для нахождения оптимального решения игры получено две двойственных симметричных задачи линейного программирования:
первая задача с системой (2.21) и критерием (2.23);
вторая задача с системой (2.25) и критерием (2.27).
Используя свойство симметричности можно решить одну из них, где будет меньше вычислений, а решение другой найти на основании оптимального плана двойственной:
(2.28) где i=1,2,...,m ; j=1,2,....,n
Цену игры S определим из последнего, оптимального плана симплекс - таблицы, учитывая
Wmax=1/S или Zmin=1/S (2.29)
Значения переменных - по значениям переменных, введенных в базис оптимального плана, а значения переменных двойственной задачи - по значениям, полученным в столбцах переменных, введенным в базис начального опорного плана, в строке целевой функции.