Лабораторные работы по Основам теории систем
Пища
Норы


15



18
2


2



8
3


22

Римскими цифрами пронумерован порядок итераций.
I.
;
;
;
– 4 столбец
исключен.
II.
;
;
;
– 2 столбец
исключен.
III.
;
;
;
– 1 строка
исключена.
IV.
;
;
;
– 5 столбец
исключен.
V.
;
;
;
– 4 строка
исключена.
VI.
;
;
;
– 3 строка
и 1 столбец
исключены.
VII.
;
;
;
– 2 строка
и 3
столбец исключены.
Порассуждав таким образом, мыши получили следующий начальный опорный план:
;
.
По этому опорному плану коту достанется аж 13 мышей (0,18 часть мыши отдельно вряд ли выживет). “Жирно ему будет”-, подумали мыши и стали составлять другой опорный план методом северо-западного угла.
4. Метод северо-западного угла.
Данный метод
очень прост,
пункты 1 и 2 в методе
максимальной
загрузки заменяются
на следующий:
очередная
загружаемая
коммуникация
выбирается
в левой верхней
клетке сохраненной
части таблицы,
т.е. в северо-западном
углу таблицы.
Математически
это выражается
следующим
образом:
,
I – множество
номеров пунктов
производства;
,
J – множество
номеров пунктов
потребления;
Последовательно по итерациям метода получаем:
I.
;
;
;
– 1 столбец
исключен.
II.
;
;
;
– 1 строка
исключена.
III.
;
;
;
– 2 столбец
исключен.
IV.
;
;
;
– 2 строка
исключена.
V.
;
;
;
– 3 столбец
исключен.
VI.
;
;
;
– 3 строка
исключена.
VII.
;
;
;
– 4 столбец
исключен.
VIII.
;
;
;
– 4 строка
и 5 столбец
исключены.
|
окорок | мешок крупы | мешок муки | мешок картошки | журналы | |
| 5 0 | 18 8 0 | 17 5 0 | 22 17 0 | 8 0 | ||
| нора 1 | 15 10 0 |
|
|
|
|
|
| нора 2 | 20 12 0 |
|
|
|
|
|
| нора 3 | 10 5 0 |
|
|
|
|
|
| нора 4 | 25 8 0 |
|
|
|
|
|
Получили следующий опорный план:
.
.
Те же самые 13 мышей, и даже хуже предыдущего опорного плана (если учитывать сотые). Пришлось мышам использовать метод минимальных затрат.
5. Метод минимальных затрат.
В этом методе в первую очередь загружаются те коммуникации, в которых затраты на перевозку минимальные. В нашем случае, это те пути, мышиные потери на которых минимальны.
|
окорок | мешок крупы | мешок муки | мешок картошки | журналы | |
| 5 0 | 18 0 | 17 0 | 22 20 18 15 0 | 8 0 | ||
| нора 1 | 15 0 |
|
|
|
|
|
| нора 2 | 20 3 0 |
|
|
|
|
|
| нора 3 | 10 2 0 |
|
|
|
|
|
| нора 4 | 25 7 2 0 |
|
|
|
|
|
I.
;
;
;
– 2 столбец
исключен.
II.
;
;
;
– 1 столбец
исключен.
III.
;
;
;
– 4 строка
исключена.
IV.
;
;
;
– 5 столбец
исключен.
V.
;
;
;
– 3 строка
исключена.
VI.
;
;
;
– 3 столбец
исключен.
VII.
;
;
;
– 2 строка
исключена.
VIII.
;
;
;
– 1 строка
и 4 столбец
исключены.
Опорный план:

Целевая функция:

Этот опорный план понравился мышам значительно больше, но все равно потери достаточно велики (7 мышей). Теперь требовалось решить эту задачу и найти оптимальный план. И сделать они это собрались самым точным методом – методом потенциалов.
6. Решение задачи методом потенциалов.
Если план действительно оптимален, то система (1) будет выполняться, т.е.:
1) для каждой
занятой клетки
транспортной
таблицы сумма
потенциалов
должна быть
равна
для этой клетки;
2) для каждой
незанятой
клетки сумма
потенциалов
не больше (меньше
или равно)
.
Построим
для каждой
свободной
переменной
плана числа
и они должны
быть положительны.
Так как число
потенциалов
равно 9, а система
состоит из 8
уравнений, то
для нахождения
какого-либо
решения этой
системы необходимо
первому из
потенциалов
придать произвольное
значение (например:
).
Далее последовательно
находим значения
всех потенциалов.
Распишем подробно
эту процедуру.




|
окорок | мешок крупы | мешок муки | мешок картошки | журналы | ||
| 5 | 18 | 17 | 22 | 8 | |||
| нора 1 | 15 |
|
|
|
|
|
|
| нора 2 | 20 |
|
|
|
|
|
|
| нора 3 | 10 |
|
|
|
|
|
|
| нора 4 | 25 |
|
|
|
|
|
|
|
|
|
|
|
|
|||
Таким образом,
после того, как
все потенциалы
найдены, можно
искать
:






Видно, что
и
меньше
нуля, значит
существующий
опорный план
можно улучшить.
Поскольку
,
нужно ввести
в базис вектор,
соответствующий
клетке (2; 1), для
чего загрузить
ее некоторым
количеством
единиц груза
(мышей). Но, так
как мы, увеличивая
загрузку (2; 1),
нарушаем баланс
строк и столбцов
распределительной
таблицы, то
следует изменить
объемы поставок
в ряде других
занятых клеток.
А чтобы число
базисных переменных
осталось прежним,
необходимо
вывести из
базиса одну
переменную.
Выводится
обычно та переменная,
у которой загрузка
в цикле минимальна.
Строим цикл:
(2; 1) – начальная точка цикла;
Что характерно, для этой точки (впрочем как и для других) мы можем построить только один цикл. Каждой клетке цикла приписываем определенный знак:
(2; 1) – “+”, (4; 1) – “-”, (4; 4) – “+” (2; 4) – “-”.
Пища
Пища






