Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

Считая что количество мышей, проживающих в 1) ; 2) ну и конечно Исходя из этих условий они составили математическую модель процесса своего питания: ; ; Ну, и для наглядности нарисовали ее в виде таблицы:

Пища Норы окорок мешок крупы мешок муки мешок картошки журналы
5 18 17 22 8
нора 1 15
нора 2 20
нора 3 10
нора 4 25
В левом верхнем углу каждой ячейки таблицы мыши указали число попавших в лапы кота (в процентах) по отношению к общему числу мышей из Безусловно, цель мышей – добраться до еды с минимальными потерями по дороге, то есть: Таким образом: 2. Двойственая задача.

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

Запишем подробно двойственную задачу на основе этого ограничения: ; ; ; ; Критерием двойственной задачи будет максимизация выгодности: 3 . Метод последовательной максимальной загрузки выбранных коммуникаций.

Первое, что пришло на ум мышам – использовать те источники пищи, доступ к которым легче, и они решили построить начальный опорный план по методу максимальной загрузки, исходя из формулы: (2). т.е. выбираются те варианты, которые могут обеспечить едой максимальное количество мышей, и эти варианты будут использоваться в соответствии с (2). Поскольку хотят есть все мыши во всех норах, то модель закрытая, т.е. Общая схема построения начального опорного плана по методу максимальной загрузки такова: 1) Выбираем коммуникацию, которую можно больше всего загрузить. 2) Максимально ее загружаем в соответствии с (2). 3) Корректируем объемы производства и потребления на величину выбранной перевозки, вычисляя остатки производства и потребления: ; 4) Вычеркиваем в транспортной таблице строку или столбец с нулевым объемом производства или потребления: если – вычеркиваем если – вычеркиваем ; 5) Повторяем этот процесс с пункта 1 по 4, пока не будут перечеркнуты все строки или столбцы В нашем случае это выглядит следующим образом:

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

+
+
-
-
Пища Норы
окорок мешок крупы мешок муки мешок картошки журналы
5 18 17 22 8
нора 1 15
нора 2 20
нора 3 10
нора 4 25
В клетках с “+” – увеличиваем загрузку, а в клетках с “-” – уменьшаем.

Величина, на которую увеличиваем или уменьшаем всегда одна и она определяется из условия: “-”. Таким образом получаем: ; 4), где в процессе реализации цикла загрузка уменьшится до 0 . Перейдем к новому опорному плану

Пища Норы окорок мешок крупы мешок муки мешок картошки журналы
5 18 17 22 8
нора 1 15
нора 2 20
нора 3 10
нора 4 25
Определяем Все больше 0, следовательно план оптимальный. Целевая функция при этом плане: М-да, незначительное улучшение для мышей. Целых 6 мышей и еще один мышиный хвостик – такова ежедневная дань коту Василию. Но делать нечего, и стали мыши действовать по этому плану. 7. Открытая модель. И все было бы хорошо, но в 3 норе появился дополнительный приплод – 10 мышей, следовательно в ней стало проживать 20 мышей, а количество мышей, питающихся у источников пищи, осталось тем же.

Получилась так называемая открытая модель, где: (3) и ее необходимо сбалансировать. Для этого нужно ввести фиктивный пункт потребления с объемом потребления: ; и дополнительные переменные приводящие ограничение-неравенство (3) к виду равенств и понимание как фиктивные перевозки из пунктов производства в фиктивный пункт потребления. Новая математическая модель: ; ; При этом во 2 и 3 норах все мыши должны быть накормлены (во второй – самые умные мыши, а в третьей – большой приплод), поэтому второе и третье ограничения – уравнения. В первое и четвертое ограничения добавим новые переменные R 1 и R 4 для уравновешивания системы. А так как этих источников пищи на самом деле нет, то и затраты (потери по дороге) на них нулевые. В транспортной таблице в последнем столбце введем еще 2 переменные в (2; 5) и (3; 5) – R 2 и R 3 , чтобы столбец был полностью заполнен, а так как перевозки в этих коммуникациях не должны быть, то наложим на них очень большие штрафы М и включим все новые переменные в целевую функцию: Так как критерий стремится к минимуму, то в оптимальном плане перевозки с самыми большими затратами не должны осуществляться (т.е.

VIII
I
II
III
IV
V
VI
VII
+
+
-
-
Пища Норы
окорок мешок крупы мешок муки мешок картошки журналы R
5 0 18 15 0 17 0 22 10 0 8 0 10 5 0
нора 1 15 5 10 5
нора 2 20 3 0 3 17
нора 3 2 0 12 0 12 8
нора 4 25 10 5 0 5 15 5
Определяем меньше 0, поэтому существующий опорный план можно улучшить.

Поскольку и переходим к новому опорному плану.

+
+
-
-
Пища Норы
окорок мешок крупы мешок муки мешок картошки журналы R
5 18 17 22 8 10
нора 1 15
нора 2 20 3 17
нора 3 2 0 12 8
нора 4 25 5 15
Определяем меньше 0, поэтому существующий опорный план можно также улучшить.

Теперь мы будем вводить в базис вектор, соответствующий клетке (2; 1). Строим цикл и переходим к новому опорному плану.

Пища Норы окорок мешок крупы мешок муки мешок картошки журналы R
5 18 17 22 8 10
нора 1 15
нора 2 20 17
нора 3 2 0 12 8
нора 4 25 18
Определяем Все больше 0, следовательно план оптимальный. Целевая функция при этом плане: Этот план чуть хуже предыдущего, к тому же 10 мышей из первой норы остаются голодными. Во всяком случае питаются раз в три дня. 8 . Запрещенные перевозки. Но кот Василий тоже не дремал, и, произведя те же операции, что и мыши в свое время, определил оптимальный план их передвижений (см. пункт 6). Посмотрев на него, он сразу решил взять под особый контроль путь от второй норы к мешку муки и от четвертой норы к мешку крупы.

Разное

Подобные работы

Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

echo "Данное решение является оптимальным. Изобразим это решение на графике: (2) F (4) (1) (3) X ( оп) X ( 2) X ( 3) X (4 ) "; echo ''; ech

Лабораторная работа №4 по "Основам теории систем" (Послеоптимизационный анализ задач линейного программирования)

echo "Оптимальные двойственные оценки "; echo ''; echo " Теперь найдём область устойчивости двойственных оценок к изменению свободных членов ограничений. Как известно, область устойчивости двойственны

Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)

echo "Запишем оптимальное решение: "; echo ''; echo " и оптимальное значение целевой функции: "; echo ''; echo " Экономически полученное решение интерпретируется следующим образом: для получения едини

Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

echo "Считая что "; echo ''; echo " "; echo ''; echo " "; echo ''; echo " "; echo ''; echo " количество мышей, проживающих в "; echo ''; echo " "; echo ''; echo " "; echo ''; echo " 1) "; echo ''; ech

Лабораторная работа №6 по "Основам теории систем" (Решение задачи о ранце методом ветвей и границ)

echo "Требуется выбрать города, в которых можно получить максимальную прибыль от продажи спиртного. При этом суммарное расстояние от этих портов до порта с грузом не должно превышать 1000 миль. 2. Реш

Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

echo "Сказано – сделано. Спрыгнул колобок из окошка и покатился в лес. Помогите колобку найти кратчайший маршрут его движения по лесу, если расстояния между норами лесных жителей, а также домом деда

"Принцип Максимума" Понтрягина

echo "Иногда рассматривают и более широкие классы допустимых управлений, например, класс всех ограниченных измеримых управлений, удовлетворяющих условию (1.2). Покажем, как при произвольном начальном