Практическое занятие №9.

«Задача о назначениях»

Цель работы.

Найти оптимальное распределение работников по заданным работам.

Порядок выполнения работы

1. Из приложения 3 выбрать свой вариант.

2. Решить задачу о назначениях:

§ Венгерским методом;

§ методом Мака.

Краткая теория

Венгерский метод.

1) В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки, затем в каждом столбце минимальную стоимость и отнимем ее от других элементов столбца.

2) Если допустимое решение получено, то оптимальные назначения соответствуют нулевым элементам. Завершить работу.

3) Иначе: В последней матрице провести минимальное число горизонтальных и вертикальных прямых, чтобы вычеркнуть все нулевые элементы.

Найти наименьший невычеркнутый элемент и вычесть его из всех невычеркнутых элементов и прибавить к элементам, стоящим на пересечении проведенных прямых.

Замечание. Случай максимизации целевой функции сводится к задаче минимизации для матрицы, полученной из исходной матрицы умножением каждого элемента на –1.

Метод Мака.

1. Увеличить все элементы матрицы А на выбранную на 2-м шаге минимальную разность.

2. В строке с минимальной разностью отметить пунктиром минимальный неподчеркнутый элемент

3. Столбец, содержащий отмеченный пунктиром элемент , перенести в множество С. Если в С более 2-х неподчеркнутых элементов, то перенести С из A' в А и перейти ко 2-му шагу. Иначе, перейти к 6-му шагу.

4. Отмеченный пунктиром элемент подчеркнуть.

5. Найти исходный подчеркнутый элемент в строке с минимальной разностью и убрать подчеркивание. Обозначить столбец с элементом D.

6. Если D не содержит других подчеркнутых элементов, он должен содержать элементы, отмеченные пунктиром. Обозначить этот элемент и перейти к 6-му шагу. Если D содержит еще 1 подчеркнутый элемент, то полностью подчеркнутые элементы образуют новый базис. В этом случае перейти к 1-му шагу.

 

Практическое занятие №10.

«Теория игр»

Цель работы

Определить основные понятия теории игр, свойства смешанных стратегий. Изучить метод решение матричных игр в смешанных стратегиях путем сведения к паре двойственных задач линейного программирования.

Порядок выполнения работы

1) Исходные данные взять из приложения 3. Четные числа оставить положительными, а нечетные – сделать отрицательными.

2) При решении матричной игры нужно выделить следующие этапы:

1. Проверить, имеет ли игра решение в чистых стратегиях.

2. Упростить платежную матрицу.

3. Если среди элементов платежной матрицы есть отрицательные, то ко всем элементам матрицы необходимо прибавить такое число L > 0, чтобы все элементы стали неотрицательными. При этом цена игры увеличится на L, а оптимальные смешанные стратегии не изменятся.

4. Составить пару взаимно двойственных задач ЛП, эквивалентных данной матричной игре.

5. Определить оптимальные планы двойственных задач.

6. Найти решение игры.

Список литературы.

1. Львовский Е.Н. Статистические методы построения эмпирических формул: Учебное пособие для ВТУЗов. —М.: Высшая школа, 1988.—239 с.

2. Львовский Е.Н. Статистические методы построения эмпирических формул: Учебное пособие для ВТУЗов. —М.: Высшая школа, 1988.—239 с.

3. Орлов А.И. Теория приянтия решений. [текст]: учебное пособие / А.И. Орлов. – М.: Март, 2004. – 60 с.

4. Пакет прикладных программ ОТЭКС (для анализа данных)\Н.Г.Загоруйко, В.Н. Елкина, С.В. Емельянов. —М.: Финансы и статистика, 1986. —160 с.

5. Штойер Р. Многокритериальная оптимизация. Теория, вычисления, приложения. – М.: Радио и связь, 1992, - 683 с.

Приложение 1

Приложение 1

Приложение 2

№В

потребители (B)

произв-ли(А)

Стоимости

 

 

Приложение 2

 

Приложение 3

 

Приложение 3

 

Приложение 3

123	Поделиться: