• 2014 год
  • Инфляция: 11.4% √ Безработица: 5.1% √ Рост ВВП: 0.6%
  • МРОТ: 5554 рублей
    Ключевая ставка: 17%
    • Россия в цифрах

      Россия в цифрах

      Статистические данные
    • Мировая экономика в цифрах

      Мировая экономика в цифрах

      Показатели и индикаторы развития мировой экономики.
    • Новости образования

      Новости образования

      Федеральная служба по надзору в сфере образования и науки (Рособрнадзор): список закрытых вузов, новости ЕГЭ

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

Смысл и сущность метода потенциалов
Потенциалы u и v являются переменными двойственной транспортной задачи и обозначают оплату за перевозку единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу cij = ui + vj

Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей X = (xij) называется допустимым планом.

Допустимый план транспортной задачи, имеющий не более (m + n - 1) отличных от нуля величин xij, называется опорным.

Если в опорном плане число отличных от нуля компонент равно в точности (m + n - 1), то план является невырожденным, если меньше, то план называется вырожденным.

План X = (xij), при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

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

Количество столбцов (магазины) Количество строк (поставщики)

Методы построения первого опорного плана

  1. метод наименьших тарифов (стоимости). Выбирается минимальный тариф, c0 = min(cij);
  2. метод северо-западного угла. Выбирается первый тариф начиная с первого, c0 = c11;

Алгоритм оценки оптимальности плана методом потенциалов

  1. Построение первого опорного плана;
  2. Проверка вырожденности плана;
  3. Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клеткам таблицы;
  4. Проверка условия оптимальности;
  5. Построение нового опорного плана.

Пример решения задачи методом северо-западного угла

Стоимость доставки единицы груза из каждого пункта отправления всоответствующие пункты назначения задана матрицей тарифов:

 

1

2

3

4

5

Запасы

1

7

4

8

3

6

70

2

5

5

4

3

8

80

3

5

6

5

8

6

90

Потребности

30

30

60

90

30

 

Пример решения задачи методом наименьших тарифов

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:

 

1

2

3

4

5

Запасы

1

7

4

8

3

6

70

2

5

5

4

3

8

80

3

5

6

5

8

6

90

Потребности

30

30

60

90

30

 

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

Для проверки полученного решения или получения автоматического решения транспортной задачи можно использовать сервис "Решение транспортной задачи". Результаты оформляются в формате doc (MS Word, OpenOffice) с комментариями и ходом решения.
twitter ВКонтакте facebook
594-797-934

Все права защищены и охраняются законом. Copyright © ООО Новый семестр Semestr.RU 2006-2016