Первоначальное распределение поставок методом учета наименьших затрат

Заполнение начинается с клеток, имеющих минимальный тариф.

Пример 4. распределить поставки с учетом наименьших затрат по условию примера 3.

1. Составим таблицу.

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

Выберем клетки с наименьшими тарифами. Такими клетками являются – одна клетка (3; 3), с тарифом 1. Заполним ее поставкой: . Так как спрос третьего потребителя удовлетворен, то клетки (1; 3) и (2; 3) мысленно вычеркиваем. У третьего поставщика осталось 10 единиц груза. Далее выбираем клетки с тарифами 2. Таковыми являются клетки (1; 2) и (3; 1). Поставки: в клетку (1; 2): ; в клетку (3; 1): . Спрос второго потребителя выполнен, значит, мысленно вычеркиваем клетки (2; 2) и (2; 3). Мощности первого и третьего поставщиков изъяты полностью, значит, мысленно вычеркиваем клетки (1; 1), (1; 4) и (3; 4). Далее выбираем клетку (2; 1) с оставшимся наименьшим тарифом в 4 - . Спрос первого потребителя удовлетворен, у второго поставщика осталось еще 40 единиц груза. Невычеркнутой осталась клетка (2; 4) с тарифом 7. В нее заполним поставку четвертому потребителю от второго поставщика - .

Потребители   Поставщики В1 В2 В3 В4
  А1 – 70 - - -
  А2 – 80 -
  А3 – 50 - -

Сделаем проверку условий.

1. Баланс сохранен.

2. Число заполненных клеток: 5 – условие не выполнено. В этом случае в произвольную клетку, например, (2;2) дадим поставку равную 0. Тогда число заполненных клеток поставками будет равно 6, то есть столько, сколько должно быть.

Ответ: опорный план

 

Нахождение оптимального плана распределения поставок

Методом потенциалов

Метод потенциалов служит для определения оптимальности полученного распределения поставок. Потенциалы – это числа Vi и Uj.

Потенциалы вводят для поставщиков: Vi и для потребителей: Uj. Всего потенциалов будет m+n.

Для вычисления значений потенциалов используется понятие оценка клетки.

Оценка клетки это сумма потенциала поставщика, потенциала потребителя и тарифа.

Потенциалы находятся из условия: оценка заполненной клетки равна нулю.

Для нахождения значений потенциалов дополняют таблицу 1 горизонтальной строкой снизу для Uj и вертикальным столбцом справа - для Vi. Так как количество потенциалов , а число заполненных клеток , то одно значение Uj или Vi берут равным нулю. Выбирают то, против которого наибольшее число заполненных клеток.

Продемонстрируем решение по условию примера 3.

Построим таблицу.

Bj Ai В1 В2 В3 В4 Vi
  А1 – 70 (-1) (-2)  
  А2 – 80 (-2) (-2)   -1
  А3 – 50 (0) (5)  
Uj -5 -2 -4 -8  

Положим значение V1 равными нулю, т.е. . Тогда согласно выше указанному условию, найдем оценку заполненной клетки (1; 1):

отсюда U1 = -5,

оценка заполненной клетки (1; 2) равна:

отсюда U2 = -2.

Аналогично находят значения остальных потенциалов:

По найденным потенциалам находят оценки свободных клеток по формуле:

.

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

Проверяем критерий оптимальности: опорный план оптимальный, если оценки всех свободных клеток неотрицательны.

Опорный план, построенный по методу «Северо-западного угла» не является оптимальным, так как есть оценки клеток меньше нуля. Для получения оптимального плана следует выполнить перераспределение поставок. Для этого строят цикл для клетки с наименьшей отрицательной оценкой.

Циклом называется замкнутый многоугольник, стороны которого вертикальные или горизонтальные отрезки; одна вершина, для которой строится цикл, свободна, а все остальные вершины – заполнены поставками.

Вершине, для которой строится цикл, присваивается номер 1, а остальные нумеруются порядковыми числами 2, 3 и так далее по часовой или против часовой стрелки. По построенному циклу перемещаем минимальный груз из четных клеток в нечетные.

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

Матричные игры. Основные понятия

Теория игр – это математическая теория конфликтных ситуаций.

Математическая модель конфликтной ситуации называется игрой, стороны конфликта – игроками, исход конфликта – выигрышем.

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

Чтобы найти решение игры, каждый игрок должен выбрать стратегию, удовлетворяющую условию оптимальности. Стратегии считаются оптимальными, если один из игроков получает максимальный выигрыш, а другой минимальный проигрыш.

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

Целью теории игр является определение оптимальной стратегии для каждого игрока.

В ходе игры каждый игрок выбирает ту или иную стратегию.

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

Простейший вид стратегической игры есть игра двух лиц А и В (парная игра) с нулевой суммой.

Игра состоит из двух ходов: игрок А выбирает одну из своих возможных стратегий ; игрок В выбирает одну из своих возможных стратегий . При этом игрок А получает выигрыш, который обозначим через , а игрок В получает выигрыш, который обозначим через .

Так как сумма выигрышей должна быть равна 0, то .

Тогда, если обозначить , то .

Парная игра с нулевой суммой формально задается платежной матрицей

,

элементы aij которой определяют выигрыш первого игрока (лица А) и соответственно проигрыш второго (лица В), если первый игрок выбирает i – ю строку (Аi стратегию), а второй игрок выбирает j – й столбец (Вj стратегию).

В каждой i – й строке игроку А гарантирован минимальный выигрыш, то есть . Игрок А стремится максимизировать свой минимальный выигрыш, то есть получить

(2)

Величина - гарантированный выигрыш игрока А называется нижней ценой игры или максимином, а соответствующая стратегия , обеспечивающая получение , называется максиминной.

Игроку В в каждом j – м столбце гарантирован максимальный проигрыш, то есть . Он стремится минимизировать свой проигрыш, то есть получить

(3)

Величина гарантированный проигрыш игрока В называется верхней ценой игры или минимаксом, а соответствующая выигрышу стратегия - минимаксной.

Отметим что всегда .

Если , то имеем в матрице М элемент который является максимальным в j – м столбце и минимальным в i – й строке. Этот элемент называется седловой точкой.

Его индексы: - указывает оптимальную стратегию игрока А, - указывает оптимальную стратегию игрока В.

Значит, в этом случае матричная игра решается в чистых стратегиях: игрок А получает оптимальную стратегию , игрок В получает оптимальную стратегию , цена игры .

Если , то матричная игра решается в смешанных стратегиях. Это значит, что игрок А выбирает стратегию с вероятностью . Смешанные стратегии игрока А записываются в виде вектора , причем , сумма вероятностей появления стратегий равна 1, или в виде матрицы

.

Игрок В выбирает стратегию с вероятностью . Аналогично смешанные стратегии игрока В записываются в виде вектора , причем , или в виде матрицы

.