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