<<
>>

Транспортная задача.

Цель работы: Изучение методов и модификации решения задач, имеющих свою специфику.

Порядок выполнения работы.

1.Общие сведения о задачи линейного программирования.

2. Постановка задачи и ее мат.

модель.

3. Построение первоначального (опорного) плана.

а) метод северо-западного угла,

б) метод минимальной стоимости,

в) метод двойного предпочтения,

4. Контрольные вопросы.

1.Общие сведения о задачи линейного программирования.

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

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

Некоторый однородный продукт, сосредоточенный у m поставщиков Ai в количестве ai (i=1,2,…m) единиц соответственно, необходимо доставить n потребителям Pj в количестве bj (j=1,2,…n) единиц. Известна стоимость Cij перевозки единицы груза от i-го поставщика к j-му потребителю.

Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость. Обозначим через xij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю; тогда условие задачи можно записать в виде таблицы (табл. 1), называемой матрицей планирования.

Таблица 1.

Поставщики Потребители Запасы
P1 P2 Pn
S1 x11 C11 x12 C12 x1n C1n a1
S2 x21 C21 x11 C22 x2n C2n a2
Sm xm1 Cm1 xm2 Cm2 xmn Cmn an
Потребности b1 b2 b3

Так как от i-го поставщика к j-му потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки составит Cij.

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

а) все грузы должны быть вывезены, т. е. ;

б) все потребности должны быть удовлетворены, т. е. .

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т. е. .

3. Построение первоначального (опорного) плана.

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

а) метод северо-западного угла:

Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя P1 за счет запаса поставщика S1.

Условие задачи: количество поставщиков – 7, количество потребителей – 5, количество запасов – 3000.

Поставщики Потребители Запасы
P1 P2 P3 P4 P5
S1 5 4 9 1 6 100
S2 4 8 7 2 9 350
S3 8 2 3 4 5 800
S4 3 6 4 7 3 500
S5 6 9 1 5 7 250
S6

S7

9

2

3

1

2

6

3

7

1

2

300

700

Потребности 700 600 500 900 300 3000

C min =

б) метод минимальной стоимости:

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую.

Поставщики Потребители Запасы
P1 P2 P3 P4 P5
S1 5 4 9 1 6 100
S2 4 8 7 2 9 350
S3 8 2 3 4 5 800
S4 3 6 4 7 3 500
S5 6 9 1 5 7 250
S6

S7

9

2

3

1

2

6

3

7

1

2

300

700

Потребности 700 600 500 900 300 3000

C min =

в) метод двойного предпочтения:

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

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

Поставщики Потребители Запасы
P1 P2 P3 P4 P5
S1 5 4 9 1 6 100
S2 4 8 7 2 9 350
S3 8 2 3 4 5 800
S4 3 6 4 7 3 500
S5 6 9 1 5 7 250
S6

S7

9

2

3

1

2

6

3

7

1

2

300

700

Потребности 700 600 500 900 300 3000

C min =

4.

Контрольные вопросы.

1. Общая задача линейного программирования.

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

Даны линейная функция z=C1x1+C2x2+…+Cnxn

и система линейных ограничений

x1≥0; xn≥0,

aij; bi Cj – заданные постоянные величины.

Формы записи задач линейного программирования.

1) Каноническая.

Определить max при ограничениях

i=1…n

j=1…m

xj≥0

2) Стандартная. Определить max при ограничениях

i=1…n

j=1…m

xj≥0

3) Общая форма. Определить max при ограничениях

i=1…k (k≤m)

j=1…r (r≤n)

xj≥0

2.Дать определение плана.

Планом или допустимым решением задачи линейного программирования называется вектор Х=(х12,…,хi), удовлетворяющий определенным условиям. План Х=(х12,…,хi) называется опорным, если векторы Ai (i=1,2,…,m) с положительными коэффициентами xi, являются линейно независимыми. Так как векторы Ai являются m мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать m.

Опорный план называется невырожденным, если он содержит m положительных компонент, в противном случае, план называется вырожденным.

3. Какая модель транспортной задачи называется открытой?

Транспортная задача – задача, целью которой является минимизация полной стоимости перевозок известного количества товаров со склада потребителю.

Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е. выполняется условие: , называется закрытой. В противном случае – модель открытая. Для открытой модели может быть два случая:

а) суммарные запасы превышают суммарные потребности;

б) суммарные потребности превышают суммарные запасы.

4. Теорема о решении транспортной задачи.

Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

5.Применение задачи.

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

<< | >>
Источник: Исследование методов решения задач линейного программирования. Лекция. 2017

Еще по теме Транспортная задача.:

  1. N 4. Особенности расследования дорожно-транспортных происшествий
  2. 2 ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  3. Улучшение инвестиционного климата и эффективное развитие транспортного комплекса.
  4. 2П ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  5. Задача распределения функций.
  6. 7.2. Построение экономико- математических моделей задач линейного программирования
  7. 8.1. Постановка задачи
  8. 8.3. Усложненные задачи транспортного типа
  9. 8.5. Транспортная задача в сетевой постановке
  10. Задачи
  11. 17.2. МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ
  12. § 67, Транспортная задача
  13. Задачи
  14. Задачи
  15. ТРАНСПОРТНАЯ ЗАДАЧА
  16. Открытая транспортная задача
  17. Приложение транспортных моделей к решению некоторых экономических задач
  18. Транспортная параметрическая задача