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

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

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

Пример решения задачи

Условие задачи

В трех пунктах отправления  имеется однородный груз в количестве  соответственно. Этот груз нужно доставить пяти заказчикам . Потребности в грузе в каждом пункте  известны и равны  соответственно. Известны также тарифы перевозки  - стоимость перевозки единицы груза из пункта  в пункт . Нужно найти такой план перевозок, при котором весь груз из пунктов потребления будет вывезен, потребности всех заказчиков будут удовлетворены, и при этом общая стоимость перевозки всего груза будет наименьшей. Данные в таблице,  в клетках которой проставлены элементы матрицы тарифов ; в последнем столбце таблицы указаны значения величин , в последней строке - значения величин .

 

                Заказчики Пункты
4 9 2 5 3  23
4 6 2 1 8  25
6 2 3 4 5  17
 14  10  16  10  15  

Требуется:

  • Составить математическую модель задачи.
  • Найти оптимальное решение транспортной задачи методом потенциалов.

Если перед сессией вам объективно не до выполнения заданий по методам оптимальных решений, то существует возможность заказать контрольную работу на сайте 100task.ru. Подробнее по ссылке Выполнить контрольную работу по методам оптимальных решений...

Решение задачи

Математическая модель задачи

Обозначим через  количество груза, перевозимого от  поставщика  потребителю. Тогда общая стоимость перевозок равна:

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения:   

Полученную задачу можно решить симплекс-методом, так как это классическая ЗЛП, однако относительная простота систем уравнений дает возможность использовать метод решения более простой. Особенности систем следующие:

  1. коэффициенты при неизвестных во всех уравнениях равны 1;
  2. каждая переменная встречается только в двух уравнениях;
  3. система уравнений транспортной задачи симметричная относительно всех переменных ;
  4. матрица, составленная из коэффициентов при переменных  состоит из единиц и нулей, причем каждый столбец матрицы содержит два элемента, равных 1, а остальные 0.

Проверка задачи на закрытость модели

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

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

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

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

Заполняем таблицу по правилу минимального элемента.

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

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

Метод потенциалов

 Решать задачу будем методом потенциалов. Число занятых клеток должно быть . Потенциал 1-й строки принимаем равным нулю. После этого мы можем вычислить остальные потенциалы (если известны потенциал и тариф занятой клетки, то из соотношения v + u =c легко определить неизвестный потенциал).

Найдем оценки свободных клеток по формуле: 

S ( 1, 1)= 4-( 0-1)=  5 S ( 1, 2)= 9-( 0+ 0)=  9
S ( 1, 4)= 5-( 0-4)=  9 S ( 2, 2)= 6-( 5+ 0)=  1
S ( 2, 3)= 2-( 5+ 2)= -5 S ( 3, 1)= 6-( 2-1)=  5
S ( 3, 3)= 3-( 2+ 2)= -1 S ( 3, 4)= 4-( 2-4)=  6

Для клетки ( 2, 3) с минимальной отрицательной оценкой строим цикл.

Перемещаем груз, равный 1 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.

Вычисляем потенциалы:

Найдем оценки свободных клеток по формуле

S ( 1, 1)= 4-( 0+ 4)=  0 S ( 1, 2)= 9-( 0+ 0)=  9
S ( 1, 4)= 5-( 0+ 1)=  4 S ( 2, 2)= 6-( 0+ 0)=  6
S ( 2, 5)= 8-( 0+ 3)=  5 S ( 3, 1)= 6-( 2+ 4)=  0
S ( 3, 3)= 3-( 2+ 2)= -1 S ( 3, 4)= 4-( 2+ 1)=  1

 

Для клетки ( 3, 3) с минимальной отрицательной оценкой строим цикл.

Перемещаем груз, равный 7 из вершин, помеченных минусом к вершинам цикла, помеченным плюсом.

Вычисляем потенциалы:

Найдем оценки свободных клеток по формуле

S ( 1, 1)= 4-( 0+ 4)=  0 S ( 1, 2)= 9-( 0+ 1)=  8
S ( 1, 4)= 5-( 0+ 1)=  4 S ( 2, 2)= 6-( 0+ 1)=  5
S ( 2, 5)= 8-( 0+ 3)=  5 S ( 3, 1)= 6-( 1+ 4)=  1
S ( 3, 4)= 4-( 1+ 1)=  2 S ( 3, 5)= 5-( 1+ 3)=  1

Оценки свободных клеток не отрицательны, следовательно, полученный план является оптимальным:

Ответ

Пункт      поставляет 8 единиц груза в пункт   и 15 единиц груза в пункт  

Пункт   поставляет 14 единиц груза в пункт  , 1 единицу груза в пункт  и 10 единиц груза в пункт

Пункт      поставляет 10 единиц груза в пункт   и 7 единиц груза в пункт  

Минимальные транспортные издержки оптимального плана: