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

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

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

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

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

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

 

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

Требуется:

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

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

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

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

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

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

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

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

  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 единиц груза в пункт  

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

Задачи и теория на такую же или близкую тему
Сохранить ссылку на страницу в социальной сети:

Помощь в решении ваших задач по этому предмету вы можете найти, отправив сообщение в ВКонтакте, WhatsApp, на Viber или заполнив форму.
Оплата на карту Сбербанка (другие распространенные способы оплаты по договоренности).
Стоимость решения домашней работы начинается от 150 р. за задачу (но не менее 300 р. за весь заказ). Подробное оформление. Стоимость помощи на экзамене онлайн (в этом случае необходима 100% предоплата) - от 1000 р. за решение билета. Подробнее...

@100task.ru 2009-2018 Москва Спб Екатеринбург Сургут Самара Краснодар Омск