Реферат: Методы решения транспортных задач

1) Выберем переменными задачи x1 – изделий вида А1; x2 – изделий вида А2.

Составим систему ограничений в виденеравенств

/>

Составим целевую функцию z(x) = 25·x1 + 17·x2 → max, т.е. обеспечить максимальную выручку от реализацииготовой продукции.

2) Найдем решение сформулированной задачи, используяее геометрическую интерпретацию. Сначала определим многоугольник решений. Дляэтого в неравенствах системы ограничений и условиях неотрицательностипеременных знаки неравенств заменим на знаки точных равенств и найдемсоответствующие прямые

/>

Эти прямые изображены на рис. 1. Пересечениеполученных полуплоскостей и определяет многоугольник решений данной задачи.

/>

Рис. 1. Графическое представление математическоймодели

Как видно из рис. 1, многоугольником решенийявляется пятиугольникОАВСD. Координатылюбой точки, принадлежащей данному пятиугольнику, удовлетворяют данной системенеравенств и условию неотрицательности переменных. Поэтому сформулированнаязадача будет решена, если мы сможем найти точку, принадлежащую пятиугольникуОАВСD, в которой функция z принимает максимальное значение. Чтобы найти указаннуюточку, построим вектор />, перпендикулярный прямой 25·x1 + 17·x2 = h, где h – некотораяпостоянная такая, что данная прямая имеет общие точки с многоугольникомрешений.

Перемещая, данную прямую в направлении вектора />, видим, чтопоследней общей точкой ее с многоугольником решений задачи служит точка B. Координаты этой точки и определяют план производствапродукции, при котором выручка от их реализации будет максимальной.

Находим координаты точки Cкак координаты точки пересечения прямых 8·x1+ 6·x2 = 848 и 5·x1+ 2·x2 = 432.

Решив эту систему уравнений,получим />, />. Итак, выручкаот реализации будет наибольшей, если в плане по производству содержится выпуск 64изделий А1 и 56 изделий А2, и, составляет 25·64 + 17·56 = 2552ден. ед.

3) Запишем данную задачу в формеосновной задачи линейного программирования. Для этого от ограничений-неравенствперейдем к ограничениям-равенствам. Введем три дополнительные переменные, врезультате чего ограничения запишутся в виде системы уравнений

/>

Составляем таблицу первой итерации:

/>

Базисные

переменные

25 17

/>

/>

/>

/>

/>

/>

/>

/>

848

532

432

8

3

5

6

5

2

1

1

1

/>

-25 -17

В 4-й строке табл. в столбцахпеременных />,/>, имеютсяотрицательные числа. Наличие этих чисел говорит о том, что данный план неявляется оптимальным. Переходим к новому плану задачи: разрешающий элементвыделен (здесь и далее) подчеркиванием.

Вторая итерация

/>

Базисные

переменные

25 17

/>

/>

/>

/>

/>

25

/>

/>

/>

784/5

1364/5

432/5

1

14/5

19/5

2/5

1

1

-8/5

-3/5

1/5

/>

2160 -7

Третья итерация

/>

Базисные

переменные

25 17

/>

/>

/>

/>

/>

17

25

/>

/>

/>

56

60

64

1

1

5/14

-19/14

-1/7

1

-4/7

11/7

3/7

/>

2552

5/2

1

Из табл. видно, что найденный новыйопорный план исходной задачи X* = (64;56; 0; 60; 0) является оптимальным. Приэтом max z = 2552.

Итак, выручка от реализации будетнаибольшей, если в плане по производству содержится выпуск 64 изделий А1и 56 изделий А2, и, составляет 2552 ден. ед.

4)Для данной задачи />, тогда />. Число переменных в двойственнойзадаче равно числу уравнений в исходной задаче, т.е. 3. Коэффициенты в целевойфункции двойственной задачи являются свободными членами неравенств-ограничений,т.е. числами 848, 532, 432. Т.к., в исходной системе ограничения представленынеравенствами, то в двойственной задаче переменные /> являются неотрицательными.

Следовательно, двойственная задачатакова: найти минимум функции z*(x) = 848·y1 + 532·y2 + 432·y3 при условиях

/>

Из последней симплекс-таблицы (итерация3) видно, что двойственная задача имеет решение />, />, />.

1) Распределительный метод

Примем некоторые обозначения: i — индекс строки j — индекс столбца m — количество поставщиков n — количество потребителей Xi,j — перевозка между поставщиком Aiи потребителем Bj.

Поставщик Потребитель Запасы груза

B1

B2

B3

B4

B5

A1

 

14 <p/>

 

8 <p/>

 

17 <p/>

 

5 <p/>

 

3 <p/> 370

A2

 

21 <p/>

 

10 <p/>

 

7 <p/>

 

11 <p/>

 

6 <p/> 450

A3

 

3 <p/>

 

5 <p/>

 

8 <p/>

 

4 <p/>

 

9 <p/> 480 Потребность 300 280 330 290 100

Транспортная задача имеет закрытыйтип, так как суммарный запас груза равен суммарным потребностям. Находимопорный план по правилу северо-западного угла: Введем некоторые обозначения: Ai* — излишек нераспределенного груза от поставщика Ai Bj* — недостача в поставке груза потребителю Bj

Помещаем в клетку (1,1) меньшее изчисел A1*=370 и B1*=300 Так какспрос потребителя B1 удовлетворен, то столбец 1 в дальнейшем врасчет не принимается Помещаем в клетку (1,2) меньшее из чисел A1*=70и B2*=280 Так как запасы поставщика A1исчерпаны, то строка 1 в дальнейшем в расчет не принимается Помещаем в клетку(2,2) меньшее из чисел A2*=450 и B2*=210Так как спрос потребителя B2 удовлетворен, то столбец 2 в дальнейшемв расчет не принимается Помещаем в клетку (2,3) меньшее из чисел A2*=240и B3*=330 Так как запасы поставщика A2исчерпаны, то строка 2 в дальнейшем в расчет не принимается Помещаем в клетку(3,3) меньшее из чисел A3*=480 и B3*=90Так как спрос потребителя B3 удовлетворен, то столбец 3 в дальнейшемв расчет не принимается Помещаем в клетку (3,4) меньшее из чисел A3*=390и B4*=290 Так как спрос потребителя B4удовлетворен, то столбец 4 в дальнейшем в расчет не принимается Помещаем вклетку (3,5) меньшее из чисел A3*=100 и B5*=100

Поставщик Потребитель Запасы груза

B1

B2

B3

B4

B5

A1

 

14

300

<p/>

 

8

70

<p/>

 

17

 

<p/>

 

5

 

<p/>

 

3

 

<p/> 370

A2

 

21

 

<p/>

 

10

210

<p/>

 

7

240

<p/>

 

11

 

<p/>

 

6

 

<p/> 450

A3

 

3

 

<p/>

 

5

 

<p/>

 

8

90

<p/>

 

4

290

<p/>

 

9

100

<p/> 480 Потребность 300 280 330 290 100

Целевая функция F=11320

Решаем задачу распределительнымметодом:

Этап 1

Определим значения оценок Si,jдля всех свободных клеток (неоптимальные выделены красным цветом). Дляэтого строим цикл для каждой свободной клетки и, перемещаясь по клеткам цикла,складываем тарифы клеток. При этом тарифы в нечетных клетках берутся со знаком«плюс», в четных — со знаком «минус». S1,3 = c1,3-c1,2+c2,2-c2,3= 12 S1,4 = c1,4-c1,2+c2,2-c2,3+c3,3-c3,4= 4 S1,5 = c1,5-c1,2+c2,2-c2,3+c3,3-c3,5= -3 S2,1 = c2,1-c2,2+c1,2-c1,1= 5 S2,4 = c2,4-c2,3+c3,3-c3,4= 8 S2,5 = c2,5-c2,3+c3,3-c3,5= -2 S3,1 = c3,1-c3,3+c2,3-c2,2+c1,2-c1,1= -14 S3,2 = c3,2-c3,3+c2,3-c2,2= -6