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

1. Тема 5. Транспортная задача.

2.

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

3.

Общая постановка задачи
Производство продукции
1-ый поставщик – a1 единиц продукции
2-ый поставщик – a2 единиц продукции
…………….
i- ый поставщик – ai единиц продукции
……………..
m -ый поставщик – am единиц продукции
Потребление продукции
1-ый пункт – b1 единиц продукции
2-ый пункт – b2 единиц продукции
…………….
j- ый пункт – bj единиц продукции
……………..
n -ый пункт – bn единиц продукции
3

4.

Общая постановка задачи
Матрица транспортных расходов
с11 с1п
С
ст1 стп
сi,j – стоимость перевозки из i-го пункта
производства в j-й пункт назначения
План перевозок
х11 х1п
Х
хт1 хтп
xi,j – количество единиц перевозимого
продукта из i-го пункта производства в
j-й пункт назначения
4

5.

Ограничения
План называется допустимым, если хij, i = 1,…,т, j = 1,…,п
удовлетворяют следующим естественным условиям:
хij 0, i 1,...,т,
j 1,...,п,
хi1 хi 2 хiп аi , i 1,...,т,
х1 j х2 j хтj b j ,
j 1,...,п,
из i-го пункта производства
перевозится по всем j=1,2,…, n
пунктам назначения
в j-й пункт назначения
поступила продукция из
всех i=1,2 ,…, m пунктов
производства
То есть, все что произведено – перевезено потребителям,
а то что требовалось поставщикам – доставлено.
5

6.

Сведение к задаче линейного программирования
Транспортная задача состоит в отыскании среди допустимых планов
перевозок оптимального, то есть такого, по которому общая
стоимость перевозок минимальна. Для этого необходимо найти
минимум целевой функции:
m n
z ci , j x i , j
i 1 j 1
при ограничениях
хij 0, i 1,..., т, j 1,..., п,
хi1 хi 2 хiп аi , i 1,..., т,
х1 j х2 j хтj b j , j 1,..., п,
Необходимое условие совместности
т
п
i 1
j 1
аi b j .
6

7.

Сведение к задаче линейного программирования
Транспортная задача является задачей линейного
программирования и может быть решена симплекс-методом, но в
силу специфики ограничений для ее решения созданы и менее
громоздкие алгоритмы (метод потенциалов, венгерский метод).
В данной работе необходимо сначала решить задачу численно в
Excel, а затем провести ручной счет по методу потенциалов,
используя в качестве первоначального плана распределение по
методу наименьшей стоимости или северо-западного угла.
7

8.

Задание
a1 a,
В предыдущих
обозначениях:
a2 b,
a3 c
b1 f ,
b2 g ,
b3 h,
b4 m,
b5 n
8

9.

Заполняем таблицу с исходными данными в
соответствии с вариантом
Объем
потребления
Объем
производства
Матрица транспортных расходов
9

10.

Проверка условия совместности
Необходимое условие совместности
т
п
i 1
j 1
аi b j .
10

11.

Последовательность действий
Выделяем в любом месте таблицу такого же размера, как матрица
затрат
11

12.

Последовательность действий
Выделяем любую пустую ячейку для искомой величины zmin
(минимальной стоимости перевозки продукции)
Вводим в нее формулу:
12

13.

Последовательность действий
Ставим курсор на ячейку сверху от верхней левой ячейки
таблицы плана перевозок (ячейка В14)
Вводим в нее формулу:
13

14.

Последовательность действий
Протягиваем формулу
из ячейки B14 до F14
14

15.

Последовательность действий
Ставим курсор на ячейку слева от верхней левой ячейки
таблицы плана перевозок (ячейка А15)
Вводим в нее формулу:
15

16.

Последовательность действий
Протягиваем формулу
из ячейки А15 до А17
16

17.

Поиск решения (Вкладка Данные Поиск решения)
17

18.

Указание на форму отчета
18

19.

Результат
Минимальная
стоимость перевозки
Оптимальный план
19

20.

Задание для ручного счета
На основе лекционного материала:
1. составить первоначальный план распределения двумя способами
а) методом наименьшей стоимости
б) методом северо-западного угла
2. Используя метод потенциалов, найти оптимальный план. В
качестве первоначального плана использовать распределение,
полученное методу наименьшей стоимости.
20