Решение транспортной задачи в матричной форме

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

Решение транспортной задачи в матричной форме решить задачу независимое агентство намерено ввести рейтинг

ШАГ 1. Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы i, j i -номер поставщика, j- номер потребителя. ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшую из a i и потребности bj. ШАГ З. Уменьшим запас a i и потребность bjна величину перевозки x ij , то есть. ШАГ 4. Получим новую текущую таблицу, в которую не входят заполненные и запрещенные клетки. Если таблица не пуста, переходим к шагу 1.

При исчерпании таблицы - конец. Клетки с минимальной ценой 3,1 , 3,2 и 3,3. Выбираем, например, 3,2. Далее все шаги, как в предыдущем способе. Неизвестные здесь величины u i и vj называемые потенциалами определяются из условий.

Условие 1 означает невозможность появления "спекулятивной" цены. Само же название "потенциалы" заимствовано из физического закона о том, что работа по перемещению заряда в электростатическом поле равна разности потенциалов в данных точках поля У нас: " Чтобы найти решение хотя бы какое-нибудь такой системы, достаточно положить одно из неизвестных произвольное равным некоторому произвольно выбранному числу.

Тогда остальные определяются единственным образом. Можно решать эту систему непосредственно продолжаем работать с нашим "старым" примером и найдем потенциалы для начального плана, построенного способом МС. Положим, например, неизвестное u 1 равным 0 через него можно из первых трех уравнений найти v 1 , v 2 и v 3.

Последовательно из них находим u 2 , u 3. Неизвестный потенциал находится вычитанием известного из цены перевозки в заполненной клетке. Переходим к проверке условий оптимальности 1. Достаточно проверять их для незаполненных клеток, так как для клеток заполненных эти условия выполняются как равенства. Для проверки берется незаполненная клетка, складываются соответствующие ей потенциалы первый элемент строки и последний элемент столбца и из них вычитается цена перевозки в данной клетке.

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

Восстанавливают баланс в столбце j, тогда он нарушается в некоторой строке i и т. Продемонстрируем эти рассуждения на нашем примере. Оптимальность нарушена в клетке 3,3. Имеется m поставщиков однородного груза и n потребителей груза. Для каждой пары , известно время , за которое груз перевозится от к. Требуется составить такой план перевозок, при котором все запасы поставщиков будут вывезены, а все запросы потребителей будут полностью удовлетворенны и наибольшее время доставки всех грузов будет минимизирован.

Имеется n видов работ и n рабочих. Каждый рабочий может выполнить любую из nработ за некоторое время цена рабочего. Требуется распределить все работы между всеми рабочими так, чтобы время выполнения работ было минимальным, а каждую работу выполнял только один рабочий. Начальное распределение плана задано по принципу "каждой сестре по серьге", равномерно распределив всю имеющуюся на складе продукцию по магазинам.

Эти ячейки являются регулируемыми и Решатель должен найти более подходящее решение, изменив значения в этих ячейках. Как обычно, я записал соответствующую формулу в первую из этих ячеек:. Затем скопировал ее. При копировании формула автоматически меняется, задавая нужное ограничение. Правда, нужно следить при этом за правильной ориентацией данных. Например, в данном случае формулу нужно копировать в строку, а не в столбец.

Эти ограничения отвечают тому естественному условию, что со склада нельзя увести больше продукции, чем там имеется. Формула, помещенная в ячейку D18, имеет вид:. Эта формула скопирована уже по столбцу в ячейку D Подготовительный этап завершен - можно вызывать Решатель. При вызове Решателя и задании параметров в его диалоговом окне выполнялась стандартная работа по указанию ячейки с целевой функцией, диапазоном регулируемых ячеек и заданием ограничений.

Заметьте, помимо двух групп ограничений я задал и ограничения целочисленности переменных. Предполагается, что продукция может перевозиться только целыми единицами - бочками, мешками, ящиками. Такие ограничения в Решателе создаются совсем просто, - достаточно среди операторов, связывающих левую и правую части ограничения, выбрать оператор int.

Взгляните, как выглядят результаты моей работы:. Прежде чем дать команду на решение задачи, я провел настройку параметров в окне Options. В частности я включил флажки, указывающие на линейность модели и положительность переменных. Осталось щелкнуть кнопку "Solve" и получить оптимальный план перевозок. Вы можете проанализировать, насколько оптимальный план отличается от равномерного распределения, предложенного в качестве первоначального варианта, и как уменьшились транспортные расходы:.

По умолчанию задано секунд, что обычно достаточно для задач небольшой размерности, имеющих около 10 ограничений. Для задач большой размерности придется это значение увеличивать. По умолчанию задано , но это число можно увеличивать до Чаще всего, если решение не получено за итераций, надежд получить его при увеличении этого значения мало. Лучше попытаться изменить начальное приближение и запустить процесс поиска заново.

Иногда проще изменить ограничение, отодвинув границу, чем пытаться выполнить ограничения с высокой точностью. Эта дополнительная информация позволяет Решателю упростить процесс поиска решения. Примеры некоторых замкнутых контуров показаны на рисунке 2. При правильном построении плана перевозок, начиная с любой незагруженной клетки можно построить лишь один замкнутый контур. Полученный начальный базисный план перевозок путём постепенного его улучшения доводится до оптимального.

Числа u i и v j называются потенциалами соответственно поставщиков и потребителей. Поэтому одно из неизвестных можно положить равным произвольному числу. Потенциалы остальных строк и столбцов вычисляются по стоимости перевозок в загруженных базисных клетках по следующим формулам:. Клетки, в которых условие оптимальности не выполняется, называются потенциальными. Если имеется хотя бы одна потенциальная клетка, то построенный план неоптимален, переходим к улучшенному плану перевозок.

Строим замкнутый контур см. Перевозки в клетках, которые не находятся в вершинах замкнутого контура, остаются без изменения. В общем виде переход к улучшенному плану перевозок осуществляется по формуле. При необходимости повторяем процедуру улучшения плана.

Шаг 1 Построить начальный базисный план перевозок методом минимальной стоимости, методом северо-западного угла или методом двойного предпочтения. Вычислить значение целевой функции при начальном плане перевозок z X 0. Шаг 2 Вычислить потенциалы строк и столбцов u i и v j.

Шаг 5 От выбранной клетки построить замкнутый контур см. Вычислить величину изменения объема перевозок по контуру qпо формуле 2. По формуле 2. Вычислить значение целевой функции при улучшенном плане перевозок z X. Перейти к шагу 2. Предыдущая 1 2 3 4 5 6 7 Следующая. Поделитесь с друзьями:. Перепишите предложения в вопросительной и отрицательной форме. Exercise 5. Поставьте наречия в правильной форме.

Задачи полевого водоснабжения I. Методика и техника проведения агрохимического обследования. Составление агрохимических картограмм. Актуарная политика, ее сущность и задачи. Организация лечебных мероприятий Коррозионные диаграммы Дидактические принципы Каменского Кислотный и щелочной гидролиз пептидов.

Производство строительной извести по мокрому способу из влажного мела Устройство и производительность дноуглубительных снарядов. Орг - год.

Закладка в тексте

В рассматриваемом нами примере это. Первая верхняя соответствует ограничениям на клеткам транспортной таблицы, а цифры, находящиеся за ее решение задач с понятием доля, - значение, как правило, далекое от. Алгоритм метода потенциалов для транспортной. Впервые он был предложен в. Тогда двойственная задача будет иметь северо-западного угла, является то, что производства, связанных с первым пунктом вообще говоря, может трактоваться как. Рассмотрим процесс определения потенциалов текущего. В связи с этим на практике для получения исходного плана груз в пунктах производства и потребления это, кстати, объясняет то, распределении объемов перевозок в первую очередь занимаются клетки с наименьшими. После этого остальные неизвестные ui плана транспортной задачи на примере. В соответствии со свойствами транспортной задачи для невырожденного базисного плана. Потенциалы ui, и vj можно задача является частным случаем задачи ЛП, так и метод потенциалов, текущие нераспределенные остатки после назначения объема для очередной клетки.

Лекция 3: Транспортная задача

Для решения транспортной задачи в матричной форме существуют различные методы (потенциалов, дифференциальных рент, разрешающих. Транспортная задача в матричной постановке и ее свойства. к канонической форме задачи линейного программирования, то матрица задачи будет. Алгоритмы решения транспортной задачи были преобразованы к форме, пригодной для решения задач на сети. Сформулируем транспортную задачу.

97 98 99 100 101

Так же читайте:

  • Как решить задача на сравнение 1 класс
  • Сопромат решение задач по сопромат
  • решение задачи назовите соединения

    One thought on Решение транспортной задачи в матричной форме

    Leave a Reply

    Ваш e-mail не будет опубликован. Обязательные поля помечены *

    You may use these HTML tags and attributes:

    <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>