Определение оптимального плана перевозок. Решение матричной игры

Размещено на http://www.allbest.ru/

Практическое задание

по математике в экономике

Выполнила:

Студентка 2 курса, №120009

Зверева А. В.

Факультет микроэкономики и маркетинга

НИМБ 2012

Задание 1

Решить задачу линейного программирования симплекс-методом.

(x)= - x₁ -x₃ -x₅>min

Решение:

Приведем задачу к каноническому виду:

В начальный базис войдут вектора A₆ и А₇ при переменных х₆ и х₇ соответственно. Симплекс-таблица имеет вид:

Поскольку оценки при векторах А₁, А₃ и А₅ отрицательные, то полученное решение является не оптимальным, и, в базис в следующей симплекс-таблице войдет вектор А₁ вместо вектора А₇.

Так как оценки при векторах А₂, А₃, А₄ и А₅ отрицательные, то полученное решение является не оптимальным. Минимальная отрицательная оценка соответствует вектору А₃, следовательно, он войдет в базис в следующей симплекс-таблице вместо вектора А₆.

Так как оценки при векторах А₄ и А₅ отрицательные, то полученное решение является не оптимальным. Минимальная отрицательная оценка соответствует вектору А₅, следовательно, он войдет в базис в следующей симплекс-таблице вместо вектора А₁.

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

Координаты точки минимума .

Минимальное значение целевой функции .

Задание 2

Имеется 3 пункта (А₁,А₂, А₃), производства и 4 пункта (В₁, В₂, В₃, В₄), его потребления. На пункте А_j (j =1…3) находится а_j условных единиц товара. В пункте В_j (j =1…4) условных единиц товара. Стоимость перевозок между производителями и потребителями (в условных денежных единицах) задается матрицей D. Найти план перевозок, при котором затраты на перевозки были бы минимальны.

а_j= 300,а₂=450, а₃=400

b₁=310, b₂=250, b₃=150_,b₄=440

D=

Решение:

Представим транспортную задачу в виде таблицы:

Проверим, является ли транспортная задача закрытой (равна ли сумма потребностей сумме запасов).

Сумма потребностей = 310 + 250 + 150 + 440 = 1150

Сумма запасов = 300 + 450 + 400 = 1150

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

Все запасы исчерпаны, все потребности удовлетворены, следовательно, назначение полное. Выполняется условие: число заполненных клеток (клеток, имеющих поставки) должно быть равно (3+4-1=6)

Построим оптимальное решение методом потенциалов.

Для всех клеток, в которых имеются поставки, должно выполняться условие

.

Число заполненных клеток равно 6, следовательно, система включает 6 уравнений и имеет вид:

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

Проверим для каждой не заполненной клетки (в которой нет поставки) критерий оптимальности:

.

Клетка (1;1) критерий оптимальности выполнен

Клетка (1;4) критерий оптимальности выполнен

Клетка (2;2) критерий оптимальности выполнен

Клетка (2;3) критерий оптимальности выполнен

Клетка (3;2) критерий оптимальности выполнен

Клетка (3;4) критерий оптимальности выполнен

Поскольку критерий оптимальности выполнен в каждой не заполненной клетке, то полученное решение является оптимальным. Поскольку часть условий при проверке критерия оптимальности выполняются как равенства, то можно построить оптимальный план поставок несколькими различными способами (причем суммарная стоимость поставок не изменится).

Рассчитаем минимальную стоимость поставок продукции:

План перевозок можно задать матрицей:

Задание 3

Для охраны автостоянки в течение 4-х месяцев требуется, соответственно, m_1, m_2, m_3, m₄ человек, причем, перед началом работы фактически имеется m₀ человек. Администрация планирует в конце каждого месяца, кроме последнего, а также в начале работы корректировать число охранников на величину х_к, х₄=0. На прием одного работника необходимо затратить «а» у.е., а на увольнение «в» у.е. Расходы на содержание избыточного работника составляют «с» у.е., а в случае нехватки персонала приходится нести затраты в размере «d» у.е. за каждое вакантное место. Требуется найти оптимальное значение х_к изменения численности работников, при которых суммарные издержки будут минимальными.

Решение:

Обозначим через - количество работников в i-м месяце, а через - количество работников принятых () или уволенных () в конце i-го месяца.

Пусть - затраты в i-м месяце;

- минимальные затраты в i-м месяце;

- сумма затрат в i-м месяце и минимальных затрат в i+1-м месяце.

В начале решения запишем в аналитической форме функции издержек на прием-увольнение сотрудников (u), а также на содержание ненормативного штата (g). С этой целью введем функции

Оценки эффективности управления на каждом шаге имеют вид:

Поскольку в поставленной задаче задано начальное условие о*₀ = 2, ее решение начинается с конца. С технической точки зрения будет удобно на каждом шаге составлять две таблицы значений: функции издержек, получаемых начиная с текущего шага в зависимости от текущего состояния и управления,

и функции минимальных издержек в зависимости от текущего состояния

1 шаг. Полагаем k=4. Требуемое количество работников .

На данном этапе функция состояния Л₄(о) может быть найдена непосредственно, если учесть, что x₄*=0 и u(0)=0:

2 шаг. Полагаем k=3. Предварительно заполним таблицу значений функции Щ₃ (x₃, о). Требуемое количество работников .

3 шаг. Полагаем k=2. Предварительно заполним таблицу значений функции Щ₂ (x₂, о). Требуемое количество работников .

4 шаг. Полагаем k=1. Предварительно заполним таблицу значений функции Щ₁ (x₁, о). Требуемое количество работников .

5 шаг. На последней итерации, в связи с наличием начального условия о*₀ = 2, достаточно вычислить Щ₀(x₀, 2).

Число рабочих в начальный момент времени равно , в начале первого месяца на работу принимается 1 человек (). Следовательно, число рабочих в первом месяце .

В конце первого месяца на работу принимается еще один работник (). Следовательно, число рабочих во втором месяце .

В конце второго месяца никого не нанимают (). Следовательно, число рабочих в третьем месяце .

В конце третьего месяца никого не нанимают (). Следовательно, число рабочих в четвертом месяце .

Таким образом, во втором месяце предпочитают иметь издержки, связанные с нехваткой работников, чем нанимать нового сотрудника.

В четвертом месяце предпочтительнее иметь издержки, связанные с избыточным числом сотрудников, чем проводить их увольнение.

Задание 4

перевозка издержка матричная игра

Найти решение матричной игры (любым методом).

Решение:

Рассмотрим матричную игру двух лиц с платежной матрицей H:

Обозначим через - вероятность применения 1-м игроком его i-й чистой стратегии.

Обозначим через - вероятность применения 2-м игроком его j-й чистой стратегии.

Рассмотрим средний выигрыш 1-го игрока, если он применяет свои чистые стратегии, а 2-й игрок - смешанную стратегию (первый игрок стремится получить максимально возможный выигрыш в наихудших условиях).

(1)

v - чистая цена игры.

Рассмотрим средний выигрыш 2-го игрока, если он применяет свои чистые стратегии, а 1-й игрок - смешанную стратегию (второй игрок стремится минимизировать выигрыш 1-го игрока).

(2)

Рассмотрим графическую интерпретацию игры:

Учитывая, что вероятность изменяется от 0 до 1 и , построим графики прямых (относительно первых трех уравнений системы (2)).

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

Для того чтобы найти оптимальное значение вероятности и цены игры необходимо найти координаты точки пересечения прямых и .

Так как

, то .

Цена игры

.

Поскольку точку максимума образует пересечение второй и третьей прямых, то вероятность применения 1-й чистой стратегии вторым игроком равна 0 (). Вероятности и . Найдем их оптимальные значения, решив систему уравнений (1).

Учитывая, что , получим

Решением матричной игры являются смешанные стратегии игроков:

Таким образом, первому игроку необходимо применять свою 1-ю чистую стратегию с вероятностью 1/3 и 2-ю чистую стратегию с вероятностью 2/3. Второму игроку необходимо применять 2-ю чистую стратегию с вероятностью 2/9 и третью чистую стратегию с вероятностью 7/9. Цена игры при этом составит 11/30.

Размещено на Allbest.ru