Лабораторная работа 5 Телешовой Елизаветы, гр. 726, Транспортные задачи линейного программирования. 1. Постановка задачи. В некотором царстве, некотором государстве жил-был кот Василий, который очень любил мышей на обед. А обедал он исключительно в амбаре своего хозяина, да так хорошо, что бедные мыши и носу не могли высунуть из своих нор. Но всю жизнь в норе не просидишь, есть то хочется, и стали мыши думать и гадать, как им провести кота Василия и до заветных пищевых ресурсов амбара добраться.
В амбаре было 4 мышиных норы в первой проживало 15 мышей, во второй 20, в третьей 10 мышей, а в четвертой 25 мышей, а также 5 источников пищи, от которых и кормилась вся эта орава мышей у окорока 5 мышей, у мешка крупы 18 мышей, у мешка муки 17 мышей, у мешка картошки 22 мыши и у стопки старых газет и журналов эротического содержания 8 мышей. И тут мыши вспомнили, что когда-то в стопке журналов лежала книжка по математическому программированию.Конечно мыши давным-давно успели ее сгрызть, но кое-что из нее они, пока грызли, прочитать успели, в частности, как решать транспортные задачи.
Считая что количество мышей из -той норы, питающихся у -того источника пищи, количество мышей, проживающих в -той норе, количество мышей, питающихся у -того источника пищи, мыши определили, что для того, чтобы были все они были сыты, необходимо выполнение 2 условий 1 2 ну и конечно Исходя из этих условий они составили математическую модель процесса своего питания Ну, и для наглядности нарисовали ее в виде таблицы Пища Норыокорокмешок крупымешок мукимешок картошкижурналы51817228нора нора нора нора В левом верхнем углу каждой ячейки таблицы мыши указали число попавших в лапы кота в процентах по отношению к общему числу мышей из -той норы, питающихся у -того источника пищи. Эти данные они также записали в виде матрицы в относительных единицах . Безусловно, цель мышей добраться до еды с минимальными потерями по дороге, то есть . Таким образом 2. Двойственая задача. Необходимо, конечно, оценить и выгодность передвижения из каждой норы к каждому пищевому ресурсу.
Для этого мыши оценили так называемые потенциалы нор и источников пищи . Так как их цель минимизировать потери, то сумма потенциалов в каждом случае не должна превышать затрат, т.е. необходимо выполнение следующих условий 1. Система 1 и будет служить в дальнейшем критерием оптимальности плана.
Запишем подробно двойственную задачу на основе этого ограничения Критерием двойственной задачи будет максимизация выгодности 3. Метод последовательной максимальной загрузки выбранных коммуникаций. Первое, что пришло на ум мышам использовать те источники пищи, доступ к которым легче, и они решили построить начальный опорный план по методу максимальной загрузки, исходя из формулы 2. т.е. выбираются те варианты, которые могут обеспечить едой максимальное количество мышей, и эти варианты будут использоваться в соответствии с 2. Поскольку хотят есть все мыши во всех норах, то модель закрытая, т.е Общая схема построения начального опорного плана по методу максимальной загрузки такова 1 Выбираем коммуникацию, которую можно больше всего загрузить. 2 Максимально ее загружаем в соответствии с 3 Корректируем объемы производства и потребления на величину выбранной перевозки, вычисляя остатки производства и потребления 4 Вычеркиваем в транспортной таблице строку или столбец с нулевым объемом производства или потребления если вычеркиваем -тую строку если вычеркиваем -тый столбец 5 Повторяем этот процесс с пункта 1 по 4, пока не будут перечеркнуты все строки или столбцы В нашем случае это выглядит следующим образом Пища Норыокорокмешок крупымешок мукимешок картошкижурналы5 2 018 017 2 022 08 0нора 115 нора 220 2 нора 310 2 нора 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 018 8 017 5 022 17 08 0нора 115 10 нора 220 12 нора 310 5 нора 8 Получили следующий опорный план Те же самые 13 мышей, и даже хуже предыдущего опорного плана если учитывать сотые.Пришлось мышам использовать метод минимальных затрат. 5. Метод минимальных затрат. В этом методе в первую очередь загружаются те коммуникации, в которых затраты на перевозку минимальные.
В нашем случае, это те пути, мышиные потери на которых минимальны. Пища Норыокорокмешок крупымешок мукимешок картошкижурналы5 018 017 022 20 18 15 08 0нора 115 нора 220 3 нора 310 2 нора 425 7 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 уравнений, то для нахождения какого-либо решения этой системы необходимо первому из потенциалов придать произвольное значение например . Далее последовательно находим значения всех потенциалов. Распишем подробно эту процедуру.Пища Норыокорокмешок крупымешок мукимешок картошкижурналы51817228нора нора нора нора Таким образом, после того, как все потенциалы найдены, можно искать Видно, что и меньше нуля, значит существующий опорный план можно улучшить.
Поскольку , нужно ввести в базис вектор, соответствующий клетке 2 1, для чего загрузить ее некоторым количеством единиц груза мышей.Но, так как мы, увеличивая загрузку 2 1, нарушаем баланс строк и столбцов распределительной таблицы, то следует изменить объемы поставок в ряде других занятых клеток. А чтобы число базисных переменных осталось прежним, необходимо вывести из базиса одну переменную.
Выводится обычно та переменная, у которой загрузка в цикле минимальна. Строим цикл 2 1 начальная точка цикла Что характерно, для этой точки впрочем как и для других мы можем построить только один цикл. Каждой клетке цикла приписываем определенный знак 2 1 , 4 1 4 4 2 4 Пища Норыокорокмешок крупымешок мукимешок картошкижурналы51817228нора нора нора нора В клетках с увеличиваем загрузку, а в клетках с - уменьшаем.Величина, на которую увеличиваем или уменьшаем всегда одна и она определяется из условия , где содержимое клеток с Таким образом получаем , а значит из базиса будет выведена 2 4, где в процессе реализации цикла загрузка уменьшится до 0. Перейдем к новому опорному плану Пища Норыокорокмешок крупымешок мукимешок картошкижурналы51817228нора нора нора нора Определяем Все больше 0, следовательно план оптимальный Целевая функция при этом плане М-да, незначительное улучшение для мышей.
Целых 6 мышей и еще один мышиный хвостик такова ежедневная дань коту Василию.
Но делать нечего, и стали мыши действовать по этому плану. 7. Открытая модель. И все было бы хорошо, но в 3 норе появился дополнительный приплод 10 мышей, следовательно в ней стало проживать 20 мышей, а количество мышей, питающихся у источников пищи, осталось тем же. Получилась так называемая открытая модель, где 3 и ее необходимо сбалансировать.Для этого нужно ввести фиктивный пункт потребления с объемом потребления и дополнительные переменные приводящие ограничение-неравенство 3 к виду равенств и понимание как фиктивные перевозки из пунктов производства в фиктивный пункт потребления.
Новая математическая модель При этом во 2 и 3 норах все мыши должны быть накормлены во второй самые умные мыши, а в третьей большой приплод, поэтому второе и третье ограничения уравнения. В первое и четвертое ограничения добавим новые переменные R1 и R4 для уравновешивания системы.А так как этих источников пищи на самом деле нет, то и затраты потери по дороге на них нулевые.
В транспортной таблице в последнем столбце введем еще 2 переменные в 2 5 и 3 5 R2 и R3 , чтобы столбец был полностью заполнен, а так как перевозки в этих коммуникациях не должны быть, то наложим на них очень большие штрафы М и включим все новые переменные в целевую функцию Так как критерий стремится к минимуму, то в оптимальном плане перевозки с самыми большими затратами не должны осуществляться т.е Напишем новую транспортную таблицу и найдем начальный опорный план методом минимальных затрат.
Пища Норыокорокмешок крупымешок мукимешок картошкижурналыR5 018 15 017 022 10 08 010 5 0нора 115 нора 220 3 нора 320 12 нора 425 10 5 Определяем . меньше 0, поэтому существующий опорный план можно улучшить. Поскольку наибольший, то мы будем вводить в базис вектор, соответствующий клетке 4 4. Строим цикл и переходим к новому опорному плану.Пища Норыокорокмешок крупымешок мукимешок картошкижурналыR5181722810нора нора нора нора Определяем меньше 0, поэтому существующий опорный план можно также улучшить.
Теперь мы будем вводить в базис вектор, соответствующий клетке 2 1. Строим цикл и переходим к новому опорному плану. Пища Норыокорокмешок крупымешок мукимешок картошкижурналыR5181722810нора нора нора нора Определяем Все больше 0, следовательно план оптимальный Целевая функция при этом плане Этот план чуть хуже предыдущего, к тому же 10 мышей из первой норы остаются голодными.Во всяком случае питаются раз в три дня. 8. Запрещенные перевозки.
Но кот Василий тоже не дремал, и, произведя те же операции, что и мыши в свое время, определил оптимальный план их передвижений см. пункт 6. Посмотрев на него, он сразу решил взять под особый контроль путь от второй норы к мешку муки и от четвертой норы к мешку крупы.Вскоре мыши это на себе почувствовали, а почувствовав, кинулись составлять новый оптимальный план, пометив эти два маршрута как чрезвычайно опасные буквой М Пища Норыокорокмешок крупымешок мукимешок картошкижурналы51817228Нора Нора Нора Нора Видно, что этот план уже является оптимальным.
Целевая функция . Как зыбко мышиное счастье. Стоило коту взяться за дело всерьез, и потери возросли чуть ли не в два раза.