Анализ результатов моделирования

⇐ ПредыдущаяСтр 6 из 7Следующая ⇒

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

4. Подведение итогов урока.

Урок 2

Тема: Метод Северо-Западного угла. Метод минимальной стоимости.

Тип урока: формирование навыков и умений.

Количество уроков: 2

Цели урока: Дать понятие метод Северо-Западного угла, метод минимальной стоимости.

Оборудование: доска, компьютер

План урока:

1. Организационный момент.

2. Изучение нового материала.

3. Применение нового материала на практике.

4. Подведение итогов урока.

Продолжительность урока: 80 минут.

Тип урока: урок изучения нового материала и его закрепление.

Ход урока:

1. Организационный момент.

2. Изучение нового материала.

Распределительный метод

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

Тарифы в клетках, находящихся в нечетных вершинах цикла, берем со знаком плюс, а в четных - со знаком минус. По каждому циклу подсчитываем алгебраическую сумму S ij тарифов.

Если замкнутый цикл имеет вид: (i, j) - > (k, j) - > (k, l) - > (t, l) - >... -> (u, v) - > (i, v), то S_ij =C_ij - C_kj+ C_kl - C_tl +... + C_uv - C_iv, где (i, j) - свободная клетка.

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

Вычисления при решении транспортной задачи распределительным методом ведутся по следующему алгоритму:

Строят исходный опорный план по правилу «северо-западного угла», или по правилу «минимального элемента»; при этом должны оказаться занятыми r=m+n-1 клеток. Однако, если опорный план является вырожденным, то это условие не соблюдается. Для сохранения числа занятых клеток r=m+n-1 неизменным проделывают следующие шаги: в таблице отыскивают клетку, имеющую минимальный тариф и не образующую цикла с занятыми клетками, помещают в нее базисный нуль и считают ее в дальнейшем занятой. Процесс поиска таких клеток продолжается до тех пор, пока число занятых клеток не станет равным m+n-1;

Производят оценку первой свободной клетки путем построения замкнутого цикла и вычисления по этому циклу величины S_ij. Если S_ij < 0, то переходят к следующему пункту алгоритма;

Перемещают по циклу количество груза, равное наименьшему из чисел, размещенных в четных клетках цикла (в клетках со знаком минус). Далее возвращаются к пункту с. Если S_ij > =0, то оценивают следующую свободную клетку, и т.д., пока не обнаружат клетку с отрицательной оценкой. Среди всех клеток с oценкой меньше нуля нужно найти клетку с наибольшим нарушением оптимальности, т.е. клетку с наименьшей оценкой. Если, наконец, оценки всех свободных клеток окажутся неотрицательными, то оптимальное решение найдено.

Допустимый план методом северо-западного угла

Сущность его состоит в следующем. Будем распределять груз, начиная с загрузки левой верхней, условно называемой северо-западной, клетки (1; 1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1; 1) занесем меньшее из чисел a 1, b 1, т.е. x 11 =min (a 1, b 1). Если а 1 > b 1, то x 11 =b 1 и первый потребитель В 1 будет полностью удовлетворен. В дальнейшем 1-й столбец таблицы в расчет не принимается; в нем переменные. Двигаясь вправо по первой строке таблицы, заносим в соседнюю клетку (1; 2) меньшее из чисел (a 1 - b 1) и b 2, т.е. x 12 = min ((a 1 - b 1), b 2). Если (a 1 - b 1) < b 2, то запасы первого поставщика исчерпаны и первая строка таблицы в дальнейшем в расчет не принимается. Переходим к аналогичному распределению запаса груза второго поставщика. Если b 1 > a 1 то х 11 =min (a 1, b 1) =а 1. При этом запас первого поставщика будет исчерпан, а потому. Первая строка из дальнейшего рассмотрения исключается. Переходим к распределению запасов второго поставщика. В клетку (2; 1) заносим наименьшее из чисел (a 2, b 1 - а 1). Заполнив таким образом клетку (1; 2) или (2; 1), переходим к загрузке следующей клетки по второй строке либо по второму столбцу. Процесс распределения по второй, третьей и последующим строкам (столбцам) производится аналогично распределению по первой строке или первому столбцу до тех пор, пока не исчерпаются ресурсы.

Ai* - излишек нераспределенного груза от поставщика Ai

Bj* - недостача в поставке груза потребителю Bj

Помещаем в клетку (1, 1) меньшее из чисел A1*=21 и B1*=25

Так как запасы поставщика A1 исчерпаны, то строка 1 в дальнейшем в расчет не принимается

Помещаем в клетку (2, 1) меньшее из чисел A2*=26 и B1*=4

Так как спрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем в расчет не принимается

Помещаем в клетку (2, 2) меньшее из чисел A2*=22 и B2*=19

Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшем в расчет не принимается

Помещаем в клетку (2, 3) меньшее из чисел A2*=3 и B3*=24

Так как запасы поставщика A2 исчерпаны, то строка 2 в дальнейшем в расчет не принимается

Помещаем в клетку (3, 3) меньшее из чисел A3*=25 и B3*=21

Так как спрос потребителя B3 удовлетворен, то столбец 3 в дальнейшем в расчет не принимается

Помещаем в клетку (3, 4) меньшее из чисел A3*=4 и B4*=28

Так как запасы поставщика A3 исчерпаны, то строка 3 в дальнейшем в расчет не принимается

Помещаем в клетку (4, 4) меньшее из чисел A4*=24 и B4*=24

Пункт назначения	1	2	3	4	Запасы
Пункт отправления
1		------	------	-------
2	------			------
3	------	------	------
4		------
Потребности

(1, 2) = c1, 2-c1, 1+c4, 1-c4, 3+c2, 3-c2, 2 = 2 (1, 3) = c1, 3-c1, 1+c4, 1-c4, 3 = - 2 (1, 4) = c1, 4-c1, 1+c4, 1-c4, 4 = 1 (2, 1) = c2, 1-c2, 3+c4, 3-c4, 1 = 10 (2, 4) = c2, 4-c2, 3+c4, 3-c4, 4 = 3 (3, 1) = c3, 1-c3, 4+c4, 4-c4, 1 = 4 (3, 2) = c3, 2-c3, 4+c4, 4-c4, 3+c2, 3-c2, 2 = 0 (3, 3) = c3, 3-c3, 4+c4, 4-c4, 3 = 4 (4, 2) = c4, 2-c4, 3+c2, 3-c2, 2 = - 2

наименьшая перевозка 17, делаем сдвиг

Пункт назначения	1	2	3	4	Запасы
Пункт отправления
1		------		-------
2	------			------
3	------	------	------
4		------	-----
Потребности

(1, 2) = c_{1, 2}-c_{1, 3}+c_{2, 3}-c_{2, 2}= 4 (1, 4) = c_{1, 4}-c_{1, 1}+c_{4, 1}-c_{4, 4} = 1 (2, 1) = c_{2, 1}-c_{2, 3}+c_{1, 3}-c_{1, 1} = 8 (2, 4) = c_{2, 4}-c_{2, 3}+c_{1, 3}-c_{1, 1}+c_{4, 1}-c_{4, 4} = 1 (3, 1) = c_{3, 1}-c_{3, 4}+c_{4, 4}-c_{4, 1} = 4 (3, 2) = c_{3, 2}-c_{3, 4}+c_{4, 4}-c_{4, 1}+c_{1, 1}-c_{1, 3}+c_{2, 3}-c_{2, 2} = 2 (3, 3) = c_{3, 3}-c_{3, 4}+c_{4, 4}-c_{4, 1}+c_{1, 1}-c_{1, 3} = 6 (4, 2) = c_{4, 2}-c_{4, 1}+c_{1, 1}-c_{1, 3}+c_{2, 3}-c_{2, 2} = 0 (4, 3) = c_{4, 3}-c_{4, 1}+c_{1, 1}-c_{1, 3} = 2

Урок 3

Тема: Метод потенциалов. Симплексный метод.

Тип урока: формирование навыков и умений.

Количество уроков: 2

Цели урока: Дать понятие метод Северо-Западного угла, метод минимальной стоимости. и изучить их методы решения задач.

Оборудование: доска, компьютер

План урока:

1. Организационный момент.

2. Изучение нового материала.

3. Применение нового материала на практике.

4. Подведение итогов урока.

Продолжительность урока: 80 минут.

Тип урока: урок изучения нового материала и его закрепление.

Ход урока:

1. Организационный момент.

2. Изучение нового материала.

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

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

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

Для нахождения циклов с отрицательной ценой вводится система

платежей

и определяются величины

называемые " псевдостоимостями" перевозки единицы груза из пункта i

в пункт j. При этом цена цикла пересчета для каждой свободной клетки

равна

если платежи

для всех базисных клеток (i, j)

⇐ Предыдущая 1 2 3 4 567 Следующая ⇒