СКАЧАТЬ:  lr313.zip [52,21 Kb] (cкачиваний: 32)

Лабораторная работа №2

по дисциплине: «Структура и математическое обеспечение

систем управления»

на тему: «Потоковые модели»

Вариант №13

Цель и содержание работы

Изучение потоковых моделей.

Основные сведения из теории

Потоковые модели объединяют ряд разнородных задач, общей чертой которых является наличие потоков, циркулирующих между пунктами производства и потребления. Например, потоки продукции, потоки товаров, финансовые потоки, информационные потоки. Наиболее удобной формой представления этих моделей является графовая форма.

Рассмотрим типичный пример потоковой модели - задачу, получившую название в классике «Транспортная задача».

Транспортная задача представляет собой частный распространенный вариант задачи линейного программирования, но специфичная формой своих ограничений.

Пусть в р пунктах отправления находятся соответственно а₁, а₂, … , а_р единиц однородного груза, который должен быть доставлен q потребителям в количествах b₁, b₂, …, b_q единиц.

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

Метод решения транспортной задачи состоит из двух этапов: составление первоначального опорного плана перевозок (методы северо-западного угла, наименьшей стоимости, Фогеля) и перераспределение  поставок,  пока план не станет оптимальным (метод потенциалов).

Метод минимальной стоимости

Построение плана начнем с клетки с наименьшей стоимостью  перевозок. Пусть это будет клетка с координатами (i; j). При наличии нескольких клеток с одинаковыми стоимостями выберем любую из них. Запишем в эту клетку элемент x_ij = min(a_i, b_j). Если a_i < b_j, то запасы поставщика A_i исчерпаны, а потребителю B_j требуется еще b_j = b_j-a_i единиц груза. Поэтому, исключая i-ю строку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей. В случае a_i > b_j из рассмотрения исключается j-й столбец, а запасы A_i полагаются равными a_i = a_i-b_j. Продолжаем этот процесс до тех пор, пока все запасы не будут исчерпаны, а все потребности удовлетворены.

Метод «северо-западного угла»

Заполним таблицу, начиная с левого верхнего угла, двигаясь далее или по строке вправо, или по столбцу вниз. В клетку (1, 1) занесем меньшее из чисел a_i и b_j, т.е. х₁₁ = min(a₁; b₁). Если a₁ > b₁ , то х₁₁ = b₁ и первый столбец закрыт, т.е. потребности первого потребителя удовлетворены полностью. Двигаемся дальше по первой строке, записывая в соседнюю клетку (1, 2) меньшее из чисел a₁-b₁ и b₂ , т.е. х₁₂ = min(a₁-b₁, b₂). Если b₂ > a₁, то аналогично закрывается первая строка и далее переходим к заполнению соседней клетки (2, 1), куда заносим х₂₁ = min(a₂ , b₁-a₁). Будем продолжать этот процесс до тех пор, пока на каком-то этапе не исчерпываются ресурсы а_m и потребности b_n. Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а пустые - свободными. План называется вырожденным, если количество базисных клеток в нем меньше, чем m+n-1. Если на каком-то этапе решения получился вырожденный план, то его необходимо пополнить, проставив в недостающем числе клеток нулевую перевозку и превратив эти клетки в базисные. Общий баланс и суммарная стоимость перевозок плана при этом не изменятся. Однако проводить пополнение плана, выбирая клетки произвольно, нельзя. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Ломаная линия может иметь точки самопересечения, но не в клетках цикла. План называется ациклическим, если его базисные клетки не содержат циклов.

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

Правила вычислений по методу потенциалов сводятся к следующему.

1. Находим потенциалы u_к и v_l всех пунктов отправления А_к и назначения В_l. Сопоставим каждому поставщику A_i и каждому потребителю B_j величины u_i и v_j соответственно так, чтобы для всех базисных клеток плана были выполнены соотношения u_i+v_j = c_ij. Поскольку число базисных клеток в плане равно m+n‑1, то для определения потенциалов получается система из m+n-1 уравнений с m+n неизвестными. Обычно для простоты полагают один из потенциалов равным нулю и затем вычисляют остальные. В транспортной таблице для потенциалов v заводится дополнительные строка, а для потенциалов u – дополнительный столбец, куда проставляются найденные значения.

2. Для каждой свободной клетки плана вычислим разности Δc_ij = c_ij-(u_i+v_j) и запишем полученные значения в левых нижних углах соответствующих клеток. План является оптимальным, если все разности Δc_ij ≥ 0. В противном случае план можно улучшить следующим способом. Найдем клетку с наибольшей по абсолютной величине отрицательной разностью Δc_ij и построим цикл, в котором, кроме этой клетки, все остальные являются базисными. В свободной клетке значение будет увеличено, проставим в ее правом нижнем углу знак +. Теперь пройдем по всей ломаной цикла, проставляя в правых нижних углах клеток поочередно знаки + и -. Груз будет перераспределен по клеткам цикла на величину Δx = min(x_ij) следующим образом. В клетках со знаком + значение перевозки нужно увеличить на величину Δx, а в клетках со знаком – уменьшить на величину Δx.

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

Расчетная часть

Задание

Найти опорный план с помощью методов минимальной стоимости (минимального элемента), "северо-западного угла"; оптимальный план с помощью метода потенциалов.

Исходные данные

Порядок выполнения работы 

1. Метод минимальной стоимости

с₃₃ = 4 - наименьшая стоимость перевозок в исходной таблице.

a₃ < b₃ => x₃₃ = 360; b₃ = b₃-a₃=140; a₃ = 0. Исключаем 3 строку.

с₄₃ = 7 - наименьшая стоимость перевозок в полученной таблице.

a₄ > b₃ => x₄₃ = 140; a₄ = a₄-b₃=40; b₃ = 0. Исключаем 3 столбец.

с₄₁ = 8 - наименьшая стоимость перевозок в полученной таблице.

a₄ < b₁ => x₄₁ = 40; b₁ = b₁-a₄=320; a₄ = 0. Исключаем 4 строку.

с₂₁ = 10 - наименьшая стоимость перевозок в полученной таблице.

a₂ < b₁ => x₂₁ = 180; b₁ = b₁-a₂=140; a₂ = 0. Исключаем 2 строку.

с₁₂ = 12 - наименьшая стоимость перевозок в полученной таблице.

a₁ > b₂ => x₁₂ = 260; a₁ = a₁-b₂=140; b₂ = 0. Исключаем 2 столбец.

с₁₁ = 16 - наименьшая стоимость перевозок в полученной таблице. 

a₁ = b₁ => x₁₁ = 140; a₁ = a₁-b₁=0; b₁ = 0. Исключаем 1 столбец. 

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

Суммарная стоимость перевозок:

2. Метод "северо-западного  угла"

Начнем заполнение таблицы с левого верхнего угла.  Клетка (1; 1).

x₁₁ = min(a₁; b₁) = 360; a₁ = a₁-b₁=40; b₁ = 0. Исключаем 1 столбец.

Переходим по столбцу вправо в клетку (1; 2).

x₁₂ = min(a₁; b₂) = 40; b₂ = b₂-a₁=220; a₁ = 0. Исключаем 1 строку.

Переходим по строке вниз в клетку (2; 2).

x₂₂ = min(a₂; b₂) = 180; b₂ = b₂-a₂=40; a₂ = 0. Исключаем 2 строку.

Переходим по строке вниз в клетку (3; 2).

x₃₂ = min(a₃; b₂) = 40; a₃ = a₃-b₂=320; b₂ = 0. Исключаем 2 столбец.

Переходим по столбцу вправо в клетку (3; 3).

x₃₃ = min(a₃; b₃) = 320; b₃ = b₃-a₃=180; a₃ = 0. Исключаем 3 строку.

Переходим по строке вниз в клетку (4; 3).

x₄₃ = min(a₄; b₃) = 180; b₃ = b₃-a₄=0; a₄ = 0. Исключаем 4 строку.

m+n-1=4+3-1=6 - соответствует числу базисных клеток.

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

Суммарная стоимость перевозок:

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

Для составления оптимального плана воспользуемся опорным планом из метода "северо-западного угла".

Найдем потенциалы v_l  и u_k (где  и ) используя базисные клетки опорного плана.

c_ij = u_i+v_j. Пусть v₃ = 0, тогда:

1) u₄ = c₄₃-v₃ = 7;

2) u₃ = c₃₃-v₃ = 4;

3) v₂ = c₃₂-u₃ = 2;

4) u₂ = c₂₂-v₂ = 9;

5) u₁ = c₁₂-v₂ = 10;

6) v₁ = c₁₁-u₁ = 6.

Заполним свободные клетки.  ∆c_ij = c_ij - (u_i+v_j), тогда:

1) ∆c₁₃ = c₁₃ - (u₁+v₃) = 4;

2) ∆c₂₁ = c₂₁ - (u₂+v₁) = -5;

3) ∆c₂₃ = c₂₃ - (u₂+v₃) = 4;

4) ∆c₃₁ = c₃₁ - (u₃+v₁) = -1;

5) ∆c₄₁ = c₄₁ - (u₄+v₁) = -5;

6) ∆c₄₂ = c₄₂ - (u₄+v₂) = 3.

∆c₂₁, ∆c₃₁, ∆c₄₁ < 0 => план не является оптимальным.

min(∆c_ij) = ∆c₄₁ = -5.

Требуется переместить часть продукции в клетку (4; 1). Для этого обозначим (4; 1) знаком "+" и компенсируем перемещение продукции в опорном плане, тогда:

1) (4; 3) - "-";

2) (3; 3) - "+";

3) (3; 2) - "-";

4) (1; 2) - "-";

5) (1; 1) - "-".

Для составления новой транспортной таблицы, освободим загруженную клетку (3; 2) с минимальным значением x₃₂ = 40 и изменим количество продукции  в таблице согласно знакам "+" или "-", получим:

1) x₁₁ = x₁₁-40 = 320;

2) x₁₂ = x₁₂+40 = 80;

3) x₃₃ = x₃₃+40 = 360;

4) x₄₃ = x₄₃-40 = 140.

Рассчитаем потенциалы для новой таблицы.

∆c₂₁, ∆c₁₃, ∆c₂₃ < 0 => план не является оптимальным.

min(∆c_ij) = ∆c₂₁ = -5.

Определим ячейки для перемещения продукции.

Для ячеек со знаком "-" min(x_ij) = x₂₂ = 180.

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

Рассчитаем потенциалы для новой таблицы.

∆c₁₃ < 0 => план не является оптимальным.

min(∆c_ij) = ∆c₁₃ = -1.

Определим ячейки для перемещения продукции.

Для ячеек со знаком "-" min(x_ij) = x₁₁ = 140.

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

Рассчитаем потенциалы для новой таблицы.

∆c_ij > 0 => план является оптимальным.

Суммарная стоимость перевозок: