Шведский бриз
Место проведения:
Петербургское шоссе, 2, лит. А, город Пушкин, Санкт-Петербург, 196601
Актовый зал
Институт магистратуры приглашает
всех желающих, имеющих высшее образование,
студентов, обучающихся по программам бакалавриата и специалитета СПбГАУ
и других вузов принять участие в ярмарке магистерских программ.
Во время мероприятия вы сможете
ознакомиться с презентациями магистерских программ,
лично пообщаться с руководителями программ
и задать им интересующие вас вопросы.
Приезжайте, чтобы почувствовать атмосферу
учебного заведения и сделать, возможно, главный выбор
в своей жизни — решиться подать документы
на образовательные программы магистратуры СПбГАУ!
ВАШ СЛЕДУЮЩИЙ ШАГ – МАГИСТРАТУРА!
Информация: т. +7(812) 451-70-82 (Институт магистратуры), E-mail: magistr@spbgau.ru
Шаг 1
| ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
| | Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута. (ui + vj = cij, где cij - тариф клетки AiBj) Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
| | |
| v2 + u1 = c12
| v2 + u1 = 3
| u1 = 3 - 0 = 3
|
| v2 + u2 = c22
| v2 + u2 = 4
| u2 = 4 - 0 = 4
|
| v2 + u3 = c32
| v2 + u3 = 3
| u3 = 3 - 0 = 3
|
| v3 + u3 = c33
| v3 + u3 = 3
| v3 = 3 - 3 = 0
|
| v4 + u3 = c34
| v4 + u3 = 4
| v4 = 4 - 3 = 1
|
| v1 + u1 = c11
| v1 + u1 = 2
| v1 = 2 - 3 = -1
| | | Поставщик
| Потребитель
| U j
| | B 1
| B 2
| B 3
| B 4
| | A 1
| | | | | u 1 = 3
| | A 2
| | | | | u 2 = 4
| | A 3
| | | | | u 3 = 3
| | V i
| v 1 = -1
| v 2 = 0
| v 3 = 0
| v 4 = 1
| | | | Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
| |  13 = c13 - (u1 + v3) = 5 - (3 + 0) = 2
|
| 14 = c14 - (u1 + v4) = 7 - (3 + 1) = 3
|
| 21 = c21 - (u2 + v1) = 6 - (4 + (-1)) = 3
|
| 23 = c23 - (u2 + v3) = 8 - (4 + 0) = 4
|
| 24 = c24 - (u2 + v4) = 2 - (4 + 1) = -3
|
| 31 = c31 - (u3 + v1) = 5 - (3 + (-1)) = 3
| | | Поставщик
| Потребитель
| U j
| | B 1
| B 2
| B 3
| B 4
| | A 1
| | | | | u 1 = 3
| | A 2
| | | | | u 2 = 4
| | A 3
| | | | | u 3 = 3
| | V i
| v 1 = -1
| v 2 = 0
| v 3 = 0
| v 4 = 1
| | | | Оценка свободной ячейки A2B4 (незадействованного маршрута) отрицательная ( 24 =-3), следовательно решение не является оптимальным.
| | Построим цикл для выбранной ячейки A2B4:
| | Поставьте курсор мыши в выбранную свободную ячейку A2B4. Используя горизонтальные и вертикальные перемещения курсора, соедините непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку A2B4. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.
| | Ячейки образующие цикл для свободной ячейки A2B4:
| | Пусть ячейка A2B4, для которой мы строили цикл, имеет порядковый номер один.
| | Поставщик
| Потребитель
| Запас
| | B 1
| B 2
| B 3
| B 4
| | A 1
| | | | |
| | A 2
| | | | |
| | A 3
| | | | |
| | Потребность
|
|
|
|
| | | Среди ячеек цикла A2B2, A3B4, номера которых четные, найдем ячейку, обладающую найменьшим значением.
| | В данном случае, это ячейка A3B4.
| | Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A3 к потребителю B4, по которому доставляется меньше всего (2) единиц продукции. Данный маршрут мы исключим из схемы доставки продукции.
| | Поставщик
| Потребитель
| Запас
| | B 1
| B 2
| B 3
| B 4
| | A 1
| | | | |
| | A 2
| | | | |
| | A 3
| | | | |
| | Потребность
|
|
|
|
| | | От ячеек цикла с четными номерами отнимает 2. К ячейкам с нечетными номерами прибавляем 2.
| | Мы вводим новый маршрут доставки продукции от поставщика A2 к потребителю B4. По данному маршруту доставим 2 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 2 ден. ед.
| | Сократим поставку от поставщика A2 к потребителю B2 на 2 единиц продукции, по цене доставки 4 за единицу продукции. Общие затраты уменьшатся на 4 * 2 ден. ед.
| | От поставщика A3 к потребителю B2 дополнительно поставим 2 единиц продукции, по цене доставки 3 за единицу продукции. Общие затраты увеличатся на 3 * 2 ден. ед.
| | По маршруту от поставщика A3 к потребителю B4 мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 4 * 2 ден. ед.
| | Данные преобразования не изменят баланс между поставщиками и потребителями. Все поставщики израсходуют все свои запасы, а все потребители получат необходимое им количество продукции.
| | Поставщик
| Потребитель
| Запас
| | B 1
| B 2
| B 3
| B 4
| | A 1
| | | | |
| | A 2
| | | | |
| | A 3
| | | | |
| | Потребность
|
|
|
|
| | | Общие расходы на доставку продукции от поставщиков к потребителям изменятся на
| | 2 * 2 - 4 * 2 + 3 * 2 - 4 * 2 = (2 - 4 + 3 - 4) * 2 = -3 * 2 ден. ед.
| | Выражение, стоящее в скобках, равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл.
| | ГЛАВНОЕ: В тот момент, когда мы нашли ячейку с наименьшим значением (среди ячеек, номера которых четные в цикле), мы уже могли сказать, что общие затраты изменятся на 24 * 2 = -3 * 2 = -6 ден. ед.
| | Общие затраты на доставку всей продукции, для данного решения, составляют S0 = 62 + (- 6) = 56 ден. ед..
| | Если оценки всех свободных ячеек (незадействованных маршрутов) неотрицательные, то снизить общую стоимость доставки всей продукции невозможно.
| | Ячейка A3B4 выйдет из базиса, мы перестали доставлять продукцию от поставщика A3 к потребителю B4
| | Ячейка A2B4 станет базисной, мы ввели новый маршрут доставки продукции от поставщика A2 к потребителю B4.
| | Поставщик
| Потребитель
| Запас
| | B 1
| B 2
| B 3
| B 4
| | A 1
| | | | |
| | A 2
| | | | |
| | A 3
| | | | |
| | Потребность
|
|
|
|
| |
Шаг 2
| ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
| | Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута. (ui + vj = cij, где cij - тариф клетки AiBj) Поскольку, число базисных клеток - 6, а общее количество потенциалов равно 7, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
| | |
| v2 + u1 = c12
| v2 + u1 = 3
| u1 = 3 - 0 = 3
|
| v2 + u2 = c22
| v2 + u2 = 4
| u2 = 4 - 0 = 4
|
| v4 + u2 = c24
| v4 + u2 = 2
| v4 = 2 - 4 = -2
|
| v2 + u3 = c32
| v2 + u3 = 3
| u3 = 3 - 0 = 3
|
| v3 + u3 = c33
| v3 + u3 = 3
| v3 = 3 - 3 = 0
|
| v1 + u1 = c11
| v1 + u1 = 2
| v1 = 2 - 3 = -1
| | | Поставщик
| Потребитель
| U j
| | B 1
| B 2
| B 3
| B 4
| | A 1
| | | | | u 1 = 3
| | A 2
| | | | | u 2 = 4
| | A 3
| | | | | u 3 = 3
| | V i
| v 1 = -1
| v 2 = 0
| v 3 = 0
| v 4 = -2
| | | | Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
| | | 13 = c13 - (u1 + v3) = 5 - (3 + 0) = 2
|
| 14 = c14 - (u1 + v4) = 7 - (3 + (-2)) = 6
|
| 21 = c21 - (u2 + v1) = 6 - (4 + (-1)) = 3
|
| 23 = c23 - (u2 + v3) = 8 - (4 + 0) = 4
|
| 31 = c31 - (u3 + v1) = 5 - (3 + (-1)) = 3
|
| 34 = c34 - (u3 + v4) = 4 - (3 + (-2)) = 3
| | | Поставщик
| Потребитель
| U j
| | B 1
| B 2
| B 3
| B 4
| | A 1
| | | | | u 1 = 3
| | A 2
| | | | | u 2 = 4
| | A 3
| | | | | u 3 = 3
| | V i
| v 1 = -1
| v 2 = 0
| v 3 = 0
| v 4 = -2
| | | | Все оценки свободных ячеек положительные, следовательно, найдено оптимальное решение.
|
| X опт =
| 
|
|
|
|
| 
| |
|
|
|
| |
|
|
|
|
Smin = 2 * 3 + 3 * 4 + 4 * 1 + 2 * 2 + 3 * 5 + 3 * 5 = 56
| | Общие затраты на доставку всей продукции, для оптимального решения, составляют 56 ден. ед.
| |
