Реферат: Математическая постановка транспортной задачи линейного программирования и решение её различным

--PAGE_BREAK--
2.2.Метод северо-западного угла

При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) остав­шейся части таблицы. При таком методе заполнение таблицы начи­нается с клетки неизвестного <img width=«21» height=«23» src=«ref-2_1455417400-100.coolpic» v:shapes="_x0000_i1135"> и заканчивается в клетке неизвест­ного <img width=«25» height=«24» src=«ref-2_1455417500-104.coolpic» v:shapes="_x0000_i1136">, т. е. идет как бы по диагонали таблицы перевозок.

Пример.

70

50

15

80

70

300

80

90

40

60

85

150

50

10

90

11

25

250

170

110

100

120

200

700


Заполнение таблицы начинается с ее северо-западного угла, т. е. клетки с неизвестным <img width=«21» height=«23» src=«ref-2_1455417400-100.coolpic» v:shapes="_x0000_i1137">. Первая база <img width=«19» height=«23» src=«ref-2_1455417704-103.coolpic» v:shapes="_x0000_i1138"> может полностью удовле­творить потребность первого заказчика <img width=«19» height=«23» src=«ref-2_1455417807-102.coolpic» v:shapes="_x0000_i1139"> <img width=«173» height=«23» src=«ref-2_1455417909-310.coolpic» v:shapes="_x0000_i1140">. Полагая <img width=«61» height=«23» src=«ref-2_1455418219-156.coolpic» v:shapes="_x0000_i1141">, вписываем это значение в клетку <img width=«21» height=«23» src=«ref-2_1455417400-100.coolpic» v:shapes="_x0000_i1142"> и исключаем из рассмотрения первый столбец. На базе <img width=«19» height=«23» src=«ref-2_1455417704-103.coolpic» v:shapes="_x0000_i1143"> остается измененный запас <img width=«52» height=«19» src=«ref-2_1455418578-140.coolpic» v:shapes="_x0000_i1144">. В оставшейся новой таблице с тремя строками <img width=«63» height=«24» src=«ref-2_1455418718-169.coolpic» v:shapes="_x0000_i1145"> и четырьмя столбцами <img width=«87» height=«24» src=«ref-2_1455418887-199.coolpic» v:shapes="_x0000_i1146">; северо-западным углом будет клетка для неизвестного <img width=«21» height=«23» src=«ref-2_1455419086-100.coolpic» v:shapes="_x0000_i1147">. Первая база с запасом <img width=«59» height=«23» src=«ref-2_1455419186-158.coolpic» v:shapes="_x0000_i1148">может полностью удовлетворить потребность второго заказчика <img width=«20» height=«23» src=«ref-2_1455419344-103.coolpic» v:shapes="_x0000_i1149"> <img width=«179» height=«23» src=«ref-2_1455419447-320.coolpic» v:shapes="_x0000_i1150">. Полагаем <img width=«61» height=«23» src=«ref-2_1455419767-157.coolpic» v:shapes="_x0000_i1151">, вписываем это значе­ние в клетку <img width=«21» height=«23» src=«ref-2_1455419086-100.coolpic» v:shapes="_x0000_i1152"> и исключаем из рассмотрения второй столбец. На базе <img width=«19» height=«23» src=«ref-2_1455417704-103.coolpic» v:shapes="_x0000_i1153"> остается новый остаток (запас) <img width=«56» height=«23» src=«ref-2_1455420127-150.coolpic» v:shapes="_x0000_i1154">. В оставшейся новой таблице с тремя строками <img width=«63» height=«24» src=«ref-2_1455418718-169.coolpic» v:shapes="_x0000_i1155"> и тремя столбцами <img width=«64» height=«24» src=«ref-2_1455420446-166.coolpic» v:shapes="_x0000_i1156"> северо-западным углом будет клетка для неизвестного <img width=«21» height=«24» src=«ref-2_1455420612-100.coolpic» v:shapes="_x0000_i1157">. Теперь третий заказчик <img width=«20» height=«24» src=«ref-2_1455420712-103.coolpic» v:shapes="_x0000_i1158"> может принять весь запас с базы <img width=«19» height=«23» src=«ref-2_1455417704-103.coolpic» v:shapes="_x0000_i1159"> <img width=«179» height=«24» src=«ref-2_1455420918-316.coolpic» v:shapes="_x0000_i1160">. Полагаем <img width=«55» height=«24» src=«ref-2_1455421234-149.coolpic» v:shapes="_x0000_i1161">, вписываем это значение в клетку <img width=«21» height=«24» src=«ref-2_1455420612-100.coolpic» v:shapes="_x0000_i1162"> и исключаем из рассмотрения первую строку. У заказ­чика из <img width=«20» height=«24» src=«ref-2_1455420712-103.coolpic» v:shapes="_x0000_i1163"> осталась еще не удовлетворенной потребность <img width=«52» height=«24» src=«ref-2_1455421586-149.coolpic» v:shapes="_x0000_i1164">.

Теперь переходим к заполнению клетки для неизвестного <img width=«23» height=«24» src=«ref-2_1455421735-103.coolpic» v:shapes="_x0000_i1165"> и т.д.

Через шесть шагов у нас останется одна база <img width=«20» height=«24» src=«ref-2_1455421838-103.coolpic» v:shapes="_x0000_i1166"> с запасом груза (остатком от предыдущего шага) <img width=«61» height=«24» src=«ref-2_1455421941-160.coolpic» v:shapes="_x0000_i1167">и один пункт <img width=«20» height=«24» src=«ref-2_1455422101-102.coolpic» v:shapes="_x0000_i1168"> с потреб­ностью<img width=«59» height=«24» src=«ref-2_1455422203-157.coolpic» v:shapes="_x0000_i1169">. Соответственно этому имеется одна свободная клетка, которую и заполняем, положив <img width=«64» height=«24» src=«ref-2_1455422360-162.coolpic» v:shapes="_x0000_i1170">. План составлен. Базис образован неизвестными <img width=«176» height=«24» src=«ref-2_1455422522-276.coolpic» v:shapes="_x0000_i1171">.

Опорный план имеет вид;


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

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел <img width=«16» height=«22» src=«ref-2_1455422798-108.coolpic» v:shapes="_x0000_i1049">и <img width=«16» height=«25» src=«ref-2_1455422906-111.coolpic» v:shapes="_x0000_i1050">. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Пример

Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

2

3

4

15

11

6

10

1

8

9

3

3

4

1

2

21

10

20

10

 




Решение:

Задача сбалансирована.

Строим первоначальный опорный план методом минимального элемента.

1.     Выясним минимальную стоимость перевозок. <img width=«88» height=«32» src=«ref-2_1455423017-1047.coolpic» v:shapes="_x0000_i1051">Первая перевозка будет осуществляться с пункта производства <img width=«20» height=«22» src=«ref-2_1455424064-115.coolpic» v:shapes="_x0000_i1052">в пункт потребления <img width=«20» height=«22» src=«ref-2_1455424064-115.coolpic» v:shapes="_x0000_i1053">и она составит максимально возможное число единиц продукта <img width=«237» height=«22» src=«ref-2_1455424294-1360.coolpic» v:shapes="_x0000_i1054">:. В этом случае, потребности пункта потребления <img width=«20» height=«22» src=«ref-2_1455424064-115.coolpic» v:shapes="_x0000_i1055">будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки <img width=«134» height=«22» src=«ref-2_1455425769-256.coolpic» v:shapes="_x0000_i1056">.Выясним минимальную стоимость перевозок (без учета столбца № 2).

2.     <img width=«124» height=«32» src=«ref-2_1455426025-1096.coolpic» v:shapes="_x0000_i1057">Вторая и третья перевозки будут осуществляться с пункта производства <img width=«18» height=«22» src=«ref-2_1455427121-111.coolpic» v:shapes="_x0000_i1058">и <img width=«20» height=«22» src=«ref-2_1455427232-113.coolpic» v:shapes="_x0000_i1059">в пункт потребления <img width=«18» height=«22» src=«ref-2_1455427345-112.coolpic» v:shapes="_x0000_i1060">и <img width=«20» height=«24» src=«ref-2_1455427457-116.coolpic» v:shapes="_x0000_i1061">соответственно и составят максимально возможное число единиц продукта: <img width=«228» height=«22» src=«ref-2_1455427573-1349.coolpic» v:shapes="_x0000_i1062">, <img width=«137» height=«24» src=«ref-2_1455428922-267.coolpic» v:shapes="_x0000_i1063">;

3.     <img width=«253» height=«24» src=«ref-2_1455429189-1397.coolpic» v:shapes="_x0000_i1064">

4.     Четвертая перевозка осуществляется с пункта <img width=«20» height=«24» src=«ref-2_1455430586-116.coolpic» v:shapes="_x0000_i1065">в пункт потребления <img width=«20» height=«24» src=«ref-2_1455427457-116.coolpic» v:shapes="_x0000_i1066">, т.к. <img width=«89» height=«32» src=«ref-2_1455430818-1059.coolpic» v:shapes="_x0000_i1067">(без учета первого, второго столбца и четвертой строки). <img width=«237» height=«24» src=«ref-2_1455431877-1367.coolpic» v:shapes="_x0000_i1068">.

5.     Пятая перевозка осуществляется с пункта <img width=«19» height=«22» src=«ref-2_1455427121-111.coolpic» v:shapes="_x0000_i1069">в пункт потребления <img width=«20» height=«24» src=«ref-2_1455427457-116.coolpic» v:shapes="_x0000_i1070">, т.к. <img width=«90» height=«32» src=«ref-2_1455433471-1060.coolpic» v:shapes="_x0000_i1071">(без учета первого, второго столбца, третьей и четвертой строки). <img width=«250» height=«24» src=«ref-2_1455434531-1385.coolpic» v:shapes="_x0000_i1072">.

 

6.                 Шестая перевозка осуществляется с пункта <img width=«20» height=«22» src=«ref-2_1455435916-113.coolpic» v:shapes="_x0000_i1073">в пункт потребления <img width=«20» height=«24» src=«ref-2_1455427457-116.coolpic» v:shapes="_x0000_i1074">т.к. <img width=«97» height=«32» src=«ref-2_1455436145-1076.coolpic» v:shapes="_x0000_i1075">(без учета первого, второго столбца, первой, третьей и четвертой строки).

<img width=«281» height=«24» src=«ref-2_1455437221-1413.coolpic» v:shapes="_x0000_i1076">

Опорный план имеет вид:


2.4. Метод аппроксимации Фогеля

При определении опорного плана транспортной задачи методом аппроксимации Фогеля находят разность по всем столбцам и по всем строкам между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальная стоимость.

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

Пример

Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:

(Здесь мы перенесли потребности в верхнюю строку для удобства построения плана). Рассмотрим задачу, приведенную для методов северо-западного угла и минимального элемента

Решение:

Опорный план имеет вид:
    продолжение
--PAGE_BREAK--

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

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj — числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij — стоимости перевозки единицы продукции между пунктами Аi и Вj:
vj[k] – ui[k]  Cij, i  1, ..., m; j 1, …, п.
Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.
Приложение

Задача 1.

Решить следующую задачу на минимизацию транспортных затрат предприятия с использованием надстройки «Поиск решения» электронной таблицы Excel.

Имеются nпунктов производства и mпунктов распределения продукции. Стоимость перевозки единицы продукции из i-го пункта производства в j-ый центр потребления Cijприведена в таблице, где под строкой понимается пункт производства, а под столбцом -пункт потребления. Кроме того, в таблицах в i-й строке указан объем производства в i-м пункте, а в j-м столбце указан спрос в j-м центре потребления. Составить план перевозок по доставке требуемой продукции в пункты потребления, минимизирующий суммарные транспортные расходы. Необходимые данные для решения задачи взять из представленной ниже таблицы.                                                                                                                                  Таблица1

<place w:st=«on»>I
.Математическая модель задачи.

1) Переменные задачи. Обозначим количество продукции, которые будут перевозиться из nпунктов производства в mпункты потребления как Xij(i=1,2,3,4,5,6; j=1,2,3,4,5). Это переменные задачи, значения которых должны быть определены в процессе решения.

В задаче содержится 6*5=30 переменных.

2) Ограничения на переменные задачи. Очевидно, что все переменные задачи не отрицательные, т.е.

                                Xij<img width=«13» height=«16» src=«ref-2_1455438634-87.coolpic» v:shapes="_x0000_i1077"> 0,

                                где i=1, 2, 3,4,5,; j=1, 2, 3, 4.
Обычно транспортная задача представляется в виде таблицы, где в ячейках помещаются переменные задачи ( Xij), а в правом верхнем углу ячейки стоят стоимости перевозки из пункта iв пункт j( Cij). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи .

Транспортная задача, для которой суммы чисел в последнем столбце и нижней строке равны, называется сбалансированной: 15 + 25 + 5 = 45, 5 + 15 + 15 + 10 = 45. Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец. Причем стоимости перевозки в добавленных ячейках принимаются равными нулю.

Для нашего примера транспортная задача не сбалансирована. Сумма чисел в последнем столбце равна: 14+30+20+32+16=112, а нижней строке равна: 60+10+20+10=100. Чтобы сбалансировать задачу  вводим пятый столбец и добавляем туда 12. Таблица в этом случае имеет вид:




3) Целевая функция. Транспортные расходы на перевозку по доставке требуемой продукции вычисляются по формуле:

Z = <img width=«29» height=«45» src=«ref-2_1455438721-223.coolpic» v:shapes="_x0000_i1172"><img width=«29» height=«46» src=«ref-2_1455438944-226.coolpic» v:shapes="_x0000_i1173">CijXij = 7,3X11 + 9X12 + 3X13 +… +5X54  (1)

II
. Решение транспортной задачи в процедуре
EXCEL
“Поиск решения”

1) Ввод данных. Вводим данные таблицы 1 и 2 в ячейки EXCEL.

В ячейках B4: E7 введены стоимости перевозок (табл. 1).

В  ячейках G4: G8 находится объемы производства. А в  ячейках B9: F12 находится объемы потребления. Ячейки B11: F15 – рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи Xij.

В ячейках G11: G15 нужно записать формулы для вычисления левых частей ограничений:

в G11 должна быть сумма ячеек B11: F11;

в G12 должна быть сумма ячеек B12: F12;

в G13 должна быть сумма ячеек B13: F13;

в G14 должна быть сумма ячеек B14: F14;

в G15 должна быть сумма ячеек B15: F15.  .

Формулы для вычисления левых частей ограничений  введем в ячейки B16: F16:

в C16 должна быть сумма ячеек C11: C15;

в D16 должна быть сумма ячеек D11: D15;

в E16 должна быть сумма ячеек E11: E15;

в F16 должна быть сумма ячеек F11: F15;

Целевую функцию поместим в ячейку H9:

H9: СУММПРОИЗВ (B4: F8; B12: F16).

Таблица исходных данных имеет вид :

<img width=«449» height=«341» src=«ref-2_1455439170-34676.coolpic» v:shapes="_x0000_i1078">

2) Заполнение окна процедуры «Поиск решения».

    целевая функция H9;

    значение целевой функции: min;

    изменяемые ячейки: B12:F16;

    ограничения задачи :

             G12:G16=G4:G8

             B12:F16 = B4:F8

             B12: F16 <img width=«13» height=«16» src=«ref-2_1455438634-87.coolpic» v:shapes="_x0000_i1079">0 (1)

<img width=«483» height=«272» src=«ref-2_1455473933-28903.coolpic» v:shapes="_x0000_i1080">
  3) Выполнив процедуру «Поиск решения» получим следующие результаты:

<img width=«516» height=«446» src=«ref-2_1455502836-53102.coolpic» v:shapes="_x0000_i1081">

Вывод:

Таким образом с предприятия А(исходный пункт 1) следует 14 ед.продукции в пункты потребления 3(пункт назначения 3); из предприятия В(исходный пункт 2) 30 ед.продукции отвести в пункт потребления 1(пункт назначения 1);  из предприятия С(исходный пункт 3) 14 ед.продукции отвести в пункт потребления 1(пункт назначения 1) и 6 ед.продукции отвести в пункт потребления 3(пункт назначения 3); из предприятия D(исходный пункт 4)7,21E-07 ед.продукции отвести в пункт потребления 1(пункт назначения 1), 10 ед.продукции отвести в пункт потребления 2(пункт назначения 2), 10 ед.продукции отвести в пункт потребления 4(пункт назначения 4) и 12 ед.продукции отвести в пункт потребления 5(пункт назначения 5); из предприятия Е(исходный пункт 5) 16 ед.продукции отвести в пункт потребления 1(пункт назначения 1).

  Все эти результаты видны в конечной таблице. При этом суммарная стоимость транспортных расходов составит 394,8 рублей (ячейка Н9).
Задача 2.

Найти опорный план транспортной задачи, в которой запасы на 3-х складах  равны 210, 170, и 65 единиц, а потребности 4-х магазинов равны 125, 90, 130 и 100 единиц продукции. Тарифы перевозки в рублях за единицу продукции следующие:

<img width=«96» height=«98» src=«ref-2_1455555938-354.coolpic» v:shapes="_x0000_s1029">


5        8  1  2

2   5   4  9

9   2   3  1 
Решение методом северо-западного угла





<img width=«182» height=«134» src=«ref-2_1455557015-522.coolpic» v:shapes="_x0000_s1028">Опорный план имеет вид:

125      85   0    0

0       5   130  35

0       0     0    65        
F(x)=<img width=«84» height=«27» src=«ref-2_1455557537-326.coolpic» v:shapes="_x0000_i1181">= 5*125+8*85+5*5+4*130+9*35+1*165=2330
Решение методом минимального элемента

 

 Опорный план имеет вид:

<img width=«170» height=«134» src=«ref-2_1455558586-514.coolpic» v:shapes="_x0000_s1030">


0         45  130  35

125  45  0    0

0       0   0   65
F(x)=<img width=«84» height=«27» src=«ref-2_1455557537-326.coolpic» v:shapes="_x0000_i1189">= 8*45+1*130+9*35+2*125+5*45+1*65=1345
Решение методом Фогеля


Пункты

Отпр-ия

Пункты назначения

Запасы

 
<img width=«19» height=«23» src=«ref-2_1455417807-102.coolpic» v:shapes="_x0000_i1190">

<img width=«20» height=«23» src=«ref-2_1455419344-103.coolpic» v:shapes="_x0000_i1191">

<img width=«20» height=«24» src=«ref-2_1455420712-103.coolpic» v:shapes="_x0000_i1192">

<img width=«20» height=«23» src=«ref-2_1455556600-105.coolpic» v:shapes="_x0000_i1193">



di

  <img width=«19» height=«23» src=«ref-2_1455417704-103.coolpic» v:shapes="_x0000_i1194">



5



8



1



9

210/110/0

1

1

1

7





110

100

<img width=«20» height=«23» src=«ref-2_1455556808-104.coolpic» v:shapes="_x0000_i1195">



2



5



4



9

170/45/25/0

2

1

1

1

125

25

20



<img width=«20» height=«24» src=«ref-2_1455421838-103.coolpic» v:shapes="_x0000_i1196">



9



2



3



1

65/0

1

1







65





Потр-ти

125/0

90/25/0

130

100



 

dj

3

         

3

           

2

1

 


3

2

1

 


3

3

7

 


3

3



 


<img width=«158» height=«122» src=«ref-2_1455560149-469.coolpic» v:shapes="_x0000_s1031">Опорный план имеет вид:
0       0   110    100

125  25    20      0

0       65    0       0

                              
F(x)=<img width=«84» height=«27» src=«ref-2_1455557537-326.coolpic» v:shapes="_x0000_i1197">= 1*110+9*100+2*125+5*25+4*20+2*65=895    продолжение
--PAGE_BREAK--