Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология Образование Политология Производство Психология Стандартизация Технологии |
Первоначальное распределение поставок методом «Северо–западного угла» ⇐ ПредыдущаяСтр 6 из 6
Заполнение начинается с первой верхней клетки (1.1), спускаясь ступеньками по диагонали вниз. Сначала заполняют клетку (1.1): . Если M1 не полностью использована в (1.1), то заполняют клетку (1.2): и так далее пока не будет полностью использована мощность M1. Оставшиеся незаполненные клетки в первой строке мысленно вычеркиваются. Затем переходят ступенькой к распределению мощности M2 по второй горизонтали и так далее пока не дойдут до клетки в m -й строке. После распределения поставок необходимо сделать проверку условий: 1) - весь объем продукции у поставщиков должен быть вывезен; 2) - все заказы удовлетворены; 3) - имеем закрытую модель ТЗ; 4) количество заполненных поставками клеток должно равняться , где m – число строк, n – число столбцов. Пример 3. Распределить поставки по методу «Северо – западного угла» в транспортной задаче: - вектор поставщиков, - вектор потребителей, - матрица тарифов. Решение. 1. Составим таблицу.
2. Распределим поставки по методу «Северо–западного угла». Для этого в клетку (1; 1) запишем груз . Так как спрос потребителя В1 выполнен, мысленно вычеркиваем клетки (2; 1) и (3; 1). У первого поставщика осталось 20 единиц груза. В клетку (1; 2) запишем груз . Так как мощность первого поставщика выбрана вся, то клетки (1; 3) и (1; 4) мысленно вычеркиваем. Переходим на вторую горизонталь. Спрос второго потребителя не удовлетворен. В клетку (2; 2) запишем груз . Так как спрос второго потребителя выполнен, то мысленно вычеркнем клетку (3; 2). У второго поставщика осталось еще 30 единиц груза. В клетку (2; 3) запишем груз . Так как мощность второго поставщика выбрана полностью, то мысленно вычеркнем клетку (2; 4). Переходим на третью горизонталь. Спрос третьего потребителя не удовлетворен. В клетку (3; 3) запишем поставку: . Спрос третьего потребителя удовлетворен. Мысленно вычеркиваются клетки в третьем столбце под клеткой (3; 3). У третьего поставщика осталось 40 единиц груза. Четвертому потребителю требуется 40 единиц груза. В клетку (3; 4) запишем поставку . Спрос четвертого потребителя удовлетворен. Мысленно вычеркиваются клетки в четвертом столбце после клетки (3; 4). Вся мощность третьего потребителя выбрана – мысленно вычеркиваются клетки в третьей строке после клетки (3; 4). Распределение поставок закончили. Сделаем проверку баланса по строкам и столбцам. Подсчитаем количество заполненных клеток . Получили опорный план: Вычислим суммарные затраты всех поставок:
Первоначальное распределение поставок методом учета наименьших затрат Заполнение начинается с клеток, имеющих минимальный тариф. Пример 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. Число заполненных клеток: 5 – условие не выполнено. В этом случае в произвольную клетку, например, (2; 2) дадим поставку равную 0. Тогда число заполненных клеток поставками будет равно 6, то есть столько, сколько должно быть. Ответ: опорный план
Нахождение оптимального плана распределения поставок Методом потенциалов Метод потенциалов служит для определения оптимальности полученного распределения поставок. Потенциалы – это числа Vi и Uj. Потенциалы вводят для поставщиков: Vi и для потребителей: Uj. Всего потенциалов будет m+n. Для вычисления значений потенциалов используется понятие оценка клетки. Оценка клетки это сумма потенциала поставщика, потенциала потребителя и тарифа. Потенциалы находятся из условия: оценка заполненной клетки равна нулю. Для нахождения значений потенциалов дополняют таблицу 1 горизонтальной строкой снизу для Uj и вертикальным столбцом справа - для Vi. Так как количество потенциалов , а число заполненных клеток , то одно значение Uj или Vi берут равным нулю. Выбирают то, против которого наибольшее число заполненных клеток. Продемонстрируем решение по условию примера 3. Построим таблицу.
Положим значение 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, или в виде матрицы . Игрок В выбирает стратегию с вероятностью . Аналогично смешанные стратегии игрока В записываются в виде вектора , причем , или в виде матрицы . Основная теорема теории игр Каждая конечная игра имеет, по крайней мере, одно решение, возможно, в области смешанных стратегий. Применение оптимальной стратегии позволяет получить выигрыш, равный цене игры: . Применение игроком А оптимальной стратегии обеспечивает ему выигрыш не менее цены игры V, то есть . Применение игроком В оптимальной стратегии обеспечивает ему проигрыш, не превышающий цены игры V, то есть . |
Последнее изменение этой страницы: 2017-03-14; Просмотров: 738; Нарушение авторского права страницы