Платная помощь студентам - решение задач и контрольных работ

Помощь в решении ваших задач и контрольных вы можете найти, отправив сообщение ВКонтакте, WhatsApp, Viber или электроннной почтой.
Мгновенная связь в любое время и на любом этапе заказа. Общение с автором студенческих работ без посредников. Опыт работы более 20 лет.
Высшая математика и физика, теория вероятностей, линейное программирование, статистика, эконометрика, финансовая математика, методы и модели, оптимальные решения.
На цену сильно влияет срочность решения. Онлайн-помощь на экзамене/зачете (срок решения 1,5 часа и меньше) осуществляется по предварительной записи.

Методы северо-западного угла, минимального элемента, Фогеля и двойного предпочтения

Содержание

Метод северо-западного угла

Рассмотрим метод северо-западного угла. Сущность его состоит в следующем.  Будем распределять груз в таблице, начиная с загрузки левой верхней, условно называемой «северо-западной», клетки (1,1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1,1) занесем меньшее из чисел , то есть . Если , то  и первый потребитель  будет полностью удовлетворен. В дальнейшем 1-й столбец таблицы в расчет не принимается: в нем переменные  для .

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

Если , то . При этом запас первого поставщика будет исчерпан, а потому  для . Первая строка из дальнейшего рассмотрения исключается. Переходим к распределению запасов второго поставщика. В клетку (2,1) заносим наименьшее из чисел .

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

Задача

Однородный продукт, сосредоточенный на трех  складах фирмы в количествах единиц, необходимо распределить между четырьмя магазинами, которым необходимо соответственно единиц продукта. Стоимость перевозки единицы продукта из  i-го пункта отправления      (i = 1, 2, 3) в  j-й пункт назначения (j = 1, 2, 3, 4) равна     и известна для всех маршрутов.

Вектор запасов продукта на складах 

вектор запросов продукта магазинами 

и матрица транспортных тарифов 

Построить начальный опорный план транспортной задачи методом северо-западного угла.

Решение

Стандартная транспортная задача разрешима только в том случае, когда выполняется условие баланса:

В нашем случае:

Модель транспортной задачи закрытая.

Построим начальный опорный план по правилу северо-западного угла.

Начинаем заполнение с левого верхнего угла и далее двигаемся по диагонали к правому нижнему углу.

Число занятых клеток должно быть .

В нашем случае число занятых клеток равно 6 - опорный план является невырожденным.

Найдем стоимость перевозок опорного плана:

Дальнейшее решение транспортной задачи, заключающееся в нахождении оптимального плана перевозок, производится методом потенциалов .

К оглавлению решебника по методам оптимальных решений

Метод минимального элемента

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

В процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0 – «нуль загрузка», условно считая эту клетку занятой. Однако число 0 записывается в те свободные клетки, которые не образуют циклов с ранее занятыми клетками.

Задача

На предприятиях  производится однородная продукция в количестве  единиц. Себестоимость производства одной единицы продукции на i-м предприятии равна соответственно  ден.ед. Готовая продукция поставляется потребителям , потребности которых составляют  единиц. Для полного удовлетворения потребностей необходимо увеличить выпуск продукции. Для этого освоить выпуск данной продукции на предприятии  с себестоимостью производства продукции  ден.ед.  Стоимости перевозки одной единицы продукции от каждого предприятия каждому потребителю задаются матрицей .

Требуется построить начальный опорный план транспортной задачи методом минимального элемента.

Решение

Задали объемную контрольную? Скоро важный зачет/экзамен? Нет времени на выполнение работы или подготовку к зачету/экзамену, но есть деньги? На сайте 100task.ru можно заказать решение задач, контрольных или онлайн-помощь на зачете/экзамене ⟩⟩

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

Условие баланса:

 

В нашем случае:

Вводим дополнительного поставщика , у которого имеется  2600-1800=800 единиц груза.

Составим матрицу затрат на производство и транспортировку продукции.

Построим начальный опорный план по правилу минимального элемента.

Просматривая таблицу замечаем, что наименьшие затраты соответствуют маршруту (2,4), поэтому в клетку помещаем . В этом случае 2-я строка в расчет не принимается. Просматриваем оставшиеся таблицы клетки. Наименьший тариф имеет клетка (4,3).

Далее, действуя по аналогичной схеме, получаем:

Число занятых клеток должно быть .

В нашем случае число занятых клеток равно 7 - опорный план является невырожденным.

Найдем стоимость перевозок опорного плана:

Дальнейшее решение транспортной задачи, заключающееся в нахождении оптимального плана перевозок, производится методом потенциалов .

К оглавлению решебника по методам оптимальных решений

Метод Фогеля

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

Задача

Ниже приведены числовые данные транспортной задачи. Стоимость перевозки единицы продукции записана в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу.

Требуется построить начальный план методом Фогеля.

Решение

Стандартная транспортная задача разрешима только в том случае, когда выполняется условие баланса:

 

В нашем случае:

Модель транспортной задачи закрытая.

Воспользуемся способом Фогеля для нахождения начального опорного плана транспортной задачи. В каждом ряду и столбце матрицы  найдем минимальный и ближайший к нему элементы и их разность по абсолютной величине записываем в конце соответствующего ряда справа и снизу. Находим максимальную из этих разностей (число 29 заключено в рамку). В ряду (или столбце), соответствующем максимальной разности, находим минимальный элемент . В клетку (3,5) вписываем число

С оставшейся матрицей поступаем аналогично предыдущему. Все вычисления сведены в таблицу.

Получили начальный опорный план транспортной задачи методом Фогеля.

Найдем стоимость перевозок опорного плана:

Дальнейшее решение транспортной задачи, заключающееся в нахождении оптимального плана перевозок, производится методом потенциалов .

К оглавлению решебника по методам оптимальных решений

Метод двойного предпочтения

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

Задача

Составить план перевозки зерна из районов  на пять элеваторов  (запасы районов и мощности элеваторов приведены) с минимальными издержками за перевозку. Затраты на перевозку 1 ц заданы.

Начальный план перевозок составить по правилу двойного предпочтения.

Решение

Стандартная транспортная задача разрешима только в том случае, когда выполняется условие баланса:

 

В нашем случае:

Модель транспортной задачи закрытая.

Заполняем таблицу по правилу двойного предпочтения.

Сначала в каждой строке находим клетку с минимальным тарифом. Если таких клеток несколько (одинаковые значения) то выбираем их все. В выбранных ячейках ставим отметку *.

Затем выполняем те же самые действия, только на тот раз по столбцам. То есть в каждом столбце тоже находим клетку (клетки) с минимальным тарифом и ставим в ней отметку – *.

Начинаем заполнять транспортную таблицу. В первую очередь заполняем ячейки с двумя звездочками (если их несколько, выбираем ту в которой меньший тариф). Далее заполняем клетки с одной звездочкой. Если остались нераспределенные запасы и неудовлетворенные потребности – заполняем оставшиеся клетки без звездочек.

Найдем стоимость перевозок опорного плана:

Дальнейшее решение транспортной задачи, заключающееся в нахождении оптимального плана перевозок, производится методом потенциалов .

К оглавлению решебника по методам оптимальных решений