Xreferat.com » Рефераты по математике » Лабораторные работы по Основам теории систем

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

CELLSPACING=0 RULES=GROUPS>

Пища

Норы

окорок мешок крупы мешок муки мешок картошки журналы 5 2 0 18 0 17 2 0 22 0 8 0 нора 1 15 0

15

нора 2 20 2 0

18

2

нора 3 10 2 0

2

8

нора 4 25 3 0

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

5

10

нора 2 20 12 0

8

12

нора 3 10 5 0

5

5

нора 4 25 8 0

17

8

Получили следующий опорный план:

.

.

Те же самые 13 мышей, и даже хуже предыдущего опорного плана (если учитывать сотые). Пришлось мышам использовать метод минимальных затрат.

5. Метод минимальных затрат.

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

Пища

Норы

окорок мешок крупы мешок муки мешок картошки журналы
5 0 18 0 17 0 22 20 18 15 0 8 0
нора 1 15 0

15

нора 2 20 3 0

17

3

нора 3 10 2 0

2

8

нора 4 25 7 2 0

5

18

2

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

15

нора 2 20

17

3

нора 3 10

2

8

нора 4 25

5

18

2




Таким образом, после того, как все потенциалы найдены, можно искать :

Видно, что и меньше нуля, значит существующий опорный план можно улучшить. Поскольку , нужно ввести в базис вектор, соответствующий клетке (2; 1), для чего загрузить ее некоторым количеством единиц груза (мышей). Но, так как мы, увеличивая загрузку (2; 1), нарушаем баланс строк и столбцов распределительной таблицы, то следует изменить объемы поставок в ряде других занятых клеток. А чтобы число базисных переменных осталось прежним, необходимо вывести из базиса одну переменную. Выводится обычно та переменная, у которой загрузка в цикле минимальна.

Строим цикл:

(2; 1) – начальная точка цикла;

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

(2; 1) – “+”, (4; 1) – “-”, (4; 4) – “+” (2; 4) – “-”.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: