Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)Считая что
   Безусловно, цель мышей – добраться до еды с минимальными потерями по дороге, то есть:  Таким образом:  2. Двойственая задача.
Необходимо, конечно, оценить и выгодность передвижения из каждой норы к каждому пищевому ресурсу. Для этого мыши оценили так называемые потенциалы нор ( Запишем подробно двойственную задачу на основе этого ограничения: Первое, что пришло на ум мышам – использовать те источники пищи, доступ к которым легче, и они решили построить начальный опорный план по методу максимальной загрузки, исходя из формулы:
    – 4 столбец исключен. II.     – 2 столбец исключен. III.     – 1 строка исключена. IV.     – 5 столбец исключен. V.     – 4 строка исключена. VI.     – 3 строка и 1 столбец исключены. VII.     – 2 строка и 3 столбец исключены.
Порассуждав таким образом, мыши получили следующий начальный опорный план: Данный метод очень прост, пункты 1 и 2 в методе максимальной загрузки заменяются на следующий: очередная загружаемая коммуникация Математически это выражается следующим образом:
  Те же самые 13 мышей, и даже хуже предыдущего опорного плана (если учитывать сотые). Пришлось мышам использовать метод минимальных затрат. 5 . Метод минимальных затрат. В этом методе в первую очередь загружаются те коммуникации, в которых затраты на перевозку минимальные. В нашем случае, это те пути, мышиные потери на которых минимальны.
    – 2 столбец исключен. II.    – 1 столбец исключен. III.     – 4 строка исключена. IV.    – 5 столбец исключен. V.     – 3 строка исключена. VI.     – 3 столбец исключен. VII.     – 2 строка исключена. VIII.     – 1 строка и 4 столбец исключены.
Опорный план:
             Видно, что  и   Строим цикл: (2 ; 1) – начальная точка цикла; Что характерно, для этой точки (впрочем как и для других) мы можем построить только один цикл.
Каждой клетке цикла приписываем определенный знак: (2 ; 1) – “+”, (4; 1) – “-”, (4; 4) – “+” (2; 4) – “-”.
Величина, на которую увеличиваем или уменьшаем всегда одна и она определяется из условия:
        Определяем    Все больше 0, следовательно план оптимальный.  Целевая функция при этом плане:  М-да, незначительное улучшение для мышей. Целых 6 мышей и еще один мышиный хвостик – такова ежедневная дань коту Василию. Но делать нечего, и стали мыши действовать по этому плану. 7. Открытая модель. И все было бы хорошо, но в 3 норе появился дополнительный приплод – 10 мышей, следовательно в ней стало проживать 20 мышей, а количество мышей, питающихся у источников пищи, осталось тем же.
Получилась так называемая открытая модель, где:
       Определяем              меньше 0, поэтому существующий опорный план можно улучшить.
Поскольку
   Определяем         меньше 0, поэтому существующий опорный план можно также улучшить.
Теперь мы будем вводить в базис вектор, соответствующий клетке (2; 1). Строим цикл и переходим к новому опорному плану.
     Все больше 0, следовательно план оптимальный.  Целевая функция при этом плане:  Этот план чуть хуже предыдущего, к тому же 10 мышей из первой норы остаются голодными. Во всяком случае питаются раз в три дня. 8 . Запрещенные перевозки. Но кот Василий тоже не дремал, и, произведя те же операции, что и мыши в свое время, определил оптимальный план их передвижений (см. пункт 6). Посмотрев на него, он сразу решил взять под особый контроль путь от второй норы к мешку муки и от четвертой норы к мешку крупы.
|
Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)
количество мышей, проживающих в 
; 2) 
ну и конечно 
Исходя из этих условий они составили математическую модель процесса своего питания: 
; 
; 
Ну, и для наглядности нарисовали ее в виде таблицы: 
Пища Норы 
(1). Система (1) и будет служить в дальнейшем критерием оптимальности плана.
; 
; 
; 
; 
Критерием двойственной задачи будет максимизация выгодности: 
3 . Метод последовательной максимальной загрузки выбранных коммуникаций.
(2). т.е. выбираются те варианты, которые могут обеспечить едой максимальное количество мышей, и эти варианты будут использоваться в соответствии с (2). Поскольку хотят есть все мыши во всех норах, то модель закрытая, т.е. 
Общая схема построения начального опорного плана по методу максимальной загрузки такова: 1) Выбираем коммуникацию, которую можно больше всего загрузить. 2) Максимально ее загружаем в соответствии с (2). 3) Корректируем объемы производства и потребления на величину выбранной перевозки, вычисляя остатки производства и потребления: 
; 
4) Вычеркиваем в транспортной таблице строку или столбец с нулевым объемом производства или потребления: если 
– вычеркиваем 
– вычеркиваем 
Пища Норы 
2 
; 
. По этому опорному плану коту достанется аж 13 мышей (0,18 часть мыши отдельно вряд ли выживет). “ Жирно ему будет ”-, подумали мыши и стали составлять другой опорный план методом северо-западного угла. 4. Метод северо-западного угла.
выбирается в левой верхней клетке сохраненной части таблицы, т.е. в северо-западном углу таблицы.
I – множество номеров пунктов производства ; 
, J – множество номеров пунктов потребления ; Последовательно по итерациям метода получаем: I. 
– 1 столбец исключен. II. 
– 1 строка исключена. III. 
– 2 столбец исключен. IV. 
– 2 строка исключена. V. 
– 3 столбец исключен. VI. 
– 3 строка исключена. VII. 
– 4 столбец исключен. VIII. 
– 4 строка и 5 столбец исключены. 
Пища Норы 
Целевая функция: 
Этот опорный план понравился мышам значительно больше, но все равно потери достаточно велики (7 мышей). Теперь требовалось решить эту задачу и найти оптимальный план. И сделать они это собрались самым точным методом – методом потенциалов. 6. Решение задачи методом потенциалов. Если план действительно оптимален, то система (1) будет выполняться, т.е.: 1) для каждой занятой клетки транспортной таблицы сумма потенциалов должна быть равна 
для этой клетки; 2) для каждой незанятой клетки сумма потенциалов не больше (меньше или равно) 
и они должны быть положительны. Так как число потенциалов равно 9, а система состоит из 8 уравнений, то для нахождения какого-либо решения этой системы необходимо первому из потенциалов придать произвольное значение (например: 
Пища Норы 
Пища Норы 
; 4), где в процессе реализации цикла загрузка уменьшится до 0 . Перейдем к новому опорному плану 
Пища Норы 
(3) и ее необходимо сбалансировать. Для этого нужно ввести фиктивный пункт потребления 
с объемом потребления: 
; и дополнительные переменные 
приводящие ограничение-неравенство (3) к виду равенств и понимание как фиктивные перевозки из пунктов производства в фиктивный пункт потребления. Новая математическая модель: 
; 
; 
Так как критерий стремится к минимуму, то в оптимальном плане перевозки с самыми большими затратами не должны осуществляться (т.е. 
Пища Норы 
5 
и переходим к новому опорному плану. 
Пища Норы 
Пища Норы 