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

 

СОДЕРЖАНИЕ

 

ВВЕДЕНИЕ…………………………………………….........................................3        

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ……………………….…………………………4

1.1.Линейное программирование……..………………………………………….4      1.2.Транспортная задача………………………………………………………….5 1.3.Методы составления опорного плана транспортной задачи……………….5 2 Практическая часть……………………………………………..…….8

ЗАКЛЮЧЕНИЕ……………………………………………………….………..24

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ...……………………...25

 

ВВЕДЕНИЕ

 

 

Математическое программирование - математическая дисциплина, посвященная теории и методам решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами).

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

  Задачи, предполагают рассмотрение различных  методов решения транспортных  задач:

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

- метод  наименьшей стоимости;

- метод  потенциалов;

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

Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального по стоимости) плана распределения и перемещения ресурсов от производителей к потребителям.

 Существует  множество методов для решения  данной задачи. Выбрав один из  методов можно быстро рассчитать  оптимальный план распределения, что значительно сократит затраты  на доставку товаров по точкам.  
1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

 

    1. Линейное программирование

 

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

- рационального  использования сырья и материалов; задачи оптимального раскроя;

- оптимизации  производственной программы предприятий;

- оптимального  размещения и концентрации производства;

- составления  оптимального плана перевозок, работы  транспорта;

- управления  производственными запасами;

и многие другие, принадлежащие сфере оптимального планирования.

 

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

 

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

- обеспечить  всех потребителей ресурсами;

- распределить  все произведенные ресурсы;

- переместить  ресурсы от производителей к  потребителям с наименьшими затратами.

От каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.

 

  1.3.Методы составления опорного плана транспортной задачи

 

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

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

Метод наименьшей стоимости.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую. И в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Алгоритм:

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

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

- Если  не все потребители удовлетворены  и не все поставщики израсходовали  товары, возврат к п.1, в противном  случае задача решена.

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

Наиболее простым методом ТЗ является метод потенциалов. Потенциалами называются условные числа Ui ,Vj , приписанные определённым образом каждому поставщику и потребителю.

Теорема(условия оптимального плана): Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток

 

                                                   (1)           [1]


 

Опорный план должен быть не вырожденным (r=m+n-1 – невырожденный план)

Алгоритм решения:

а) строим начальные планы методом северо-западного угла и методом наименьшей стоимости из них выбираем лучший

б) находим потенциалы поставщика и потребителя, пользуясь первым условием оптимальности плана Ui + Vj < Cij

с) проверяем второе условие оптимальности плана для свободных клеток

      

Если оно выполнено, то план оптимален, если нет то улучшаем план.

а) улучшение плана:

- при  не выполнении второго условия  в клетку заносим нарушение  со знаком плюс. Такие клетки называются потенциальными.

- среди  всех потенциальных клеток выбираем  клетку с наибольшим

нарушением.

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

За исключением той клетки, для которой строится контур

- вершины  контура поочерёдно помечаем  знаками плюс и минус, начиная  с клетки, для которой строится  контур.

- среди  клеток помеченных знаком минус  выбираем наименьшею перевозку  и на эту величину увеличиваем  перевозку в клетках помеченных  знаком плюс и уменьшаем в  клетках помеченных знаком минус  в результатах переназначения  освобождается одна клетка.

б) вновь полученный план проверяем на оптимальность.

Данный метод состоит в следующем:

а) на каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;

б) находят max Δcij и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

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

 

 

 

2 ПРАКТИЧЕСКАЯ ЧАСТЬ

 

Задание 1.

Для выпуска двух видов продукции  Ⅰ и  Ⅱ требуется затраты сырья, рабочего времени и оборудования.

Исходные данные:

Ресурс

Норма затрат ресурсов

Наличие ресурсов

Ⅰ

Ⅱ

Сырье, кг

5

2

40

Рабочее время, ч

6

12

96

Оборудование, ед

1

4

28


 

Прибыль от продажи продукции Ⅰ  и Ⅱ соответственно равна 40 и 30 руб. Необходимо определить, сколько продукции каждого вида следует выпустить, чтобы общая прибыль выпускаемой продукции была максимальной. 

Решение: Выберем в качестве параметров, характеризующих процесс планирования производства продукции, число вида продукции Ⅰ (переменная x1) и число вида продукции Ⅱ (переменная x2). Выразим через выбранные неизвестные суммарную прибыль от реализации всей продукции. Она включает в себя прибыль от реализации всех видов продукции Ⅰ (40x1) и продукции Ⅱ (30x2). Тогда цель задачи (максимизация прибыли) запишется в виде:

 

Перейдем к формулировке ограничений. Структура всех трех ограничений одинакова:


 

 

Теперь остается выразить полный расход ресурса через выбранные неизвестные x1 и x2. Так, расход сырья на выпуск продукции составит ,а на рабочее время (см. первую строку таблицы). В сумме это даст полный расход ресурсов и ограничение рабочего времени примет вид линейного неравенства: . Аналогично запишутся ограничения для остальных видов ресурсов:

 

 

Объединяя их в систему, получим:

 

Далее, исходя из смысла введенных переменных (число продукций не может быть отрицательным), на них необходимо наложить условия не отрицательности :   x1 ³ 0  и x2³ 0.

Окончательно выпишем математическую модель задачи в форме задачи линейного программирования (ЗЛП):

,

 

x1 ³ 0, x2³ 0.

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

Рассмотрим неравенство . Оно определяет полуплоскость, лежащую по одну сторону от прямой линии . Чтобы определить, какую именно полуплоскость определяет данное неравенство, достаточно взять произвольную точку плоскости и подставить в неравенство её координаты. Если неравенство верно, то полуплоскость, в которой лежит данная точка, – искомая. В противном случае нужная полуплоскость лежит по другую сторону от прямой . Например, возьмём точку (2;15), тогда – верно.

Аналогичные исследования можно провести и для неравенств:

  и  . Тогда, с учётом не отрицательности переменных x1, x2, получаем заштрихованную область (рисунок 1).

 

 

 

Рисунок 1-График нахождения оптимального плана

 

Известно, что значения целевой функции неограниченно возрастают, если перемещать прямую  в направлении её вектора нормали – градиента , и убывают, если перемещать эту прямую в направлении вектора . Оптимальное решение состоит из точек касания последней линии уровня с допустимой областью, то есть Z = (6;5) – оптимальное решение, Fmax = 40*6+30*5 = 390 ед.

Итак, для получения прибыли в размере 390 ед. необходимо 6 кг. сырья и 5 ч. рабочего времени.

 

Задание 2.

Составьте опорные планы методами:

  1. «северо-западного» угла;
  2. наименьших затрат;
  3. аппроксимации Фогеля.

Методом потенциалов оптимизируйте план, полученный методом наименьших затрат.

Решение:

 

Таблица 1- Исходная транспортная таблица

База

Магазин

Запасы  
продукции, ai

В1

В2

В3

В4

В5

А1

                    

50

 

7

  

6

  

8

  

10

  

12

А2

                    

60

 

9

  

5

  

7

  

4

  

6

А3

                    

40

 

6

  

8

  

4

  

9

  

7

Спрос  
на продукцию, bj

30

20

55

20

25

150


 

,

.

Так как , то имеем закрытую транспортную задачу, n = 3, m = 5.

1 метод. Метод «северо-западного угла»

Таблица 2 заполняется, начиная с «северо-западного» угла, то есть с левой верхней клетки.

Дадим переменной x11 максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1; 1) – «северо-западный» угол таблицы поставок: x11 = min{30, 20} = 50. После этого спрос первого потребителя полностью удовлетворён, в результате чего первый столбец таблицы поставок исключается из дальнейшего рассмотрения (до тех пор, пока опорный план не будет составлен полностью). Заполненные клетки будем перечёркивать по диагонали сплошной линией, а исключённые из дальнейшего рассмотрения – пунктирной линией; при этом предложение первого поставщика уменьшается на 30 ед. и составит 20 ед.

 

Таблица 2-Таблица метода «северо-западного» угла

База

Магазин

Запасы  
продукции, ai

В1

В2

В3

В4

В5

А1

30

  

20

              

50/20

 

7

  

6

  

8

  

10

  

12

А2

        

55

  

5

      

60

 

9

  

5

  

7

  

4

  

6

А3

            

15

  

25

  

40

 

6

  

8

  

4

  

9

  

7

Спрос  
на продукцию, bj

30

20

55

20

25

150


Теперь в таблице поставок 2 находим новый «северо-западный» угол – клетку (1; 2) и отправляем в неё максимально возможную поставку x11 = min{30, 20} = 50 и клетка (1; 2) перечёркивается сплошной линией. После этого мощность первого поставщика полностью использована, то есть клетки (2; 3), (2; 4), (3; 4), и (3;5) исключаются из рассмотрения и перечёркиваются пунктиром. В оставшейся таблице вновь находим «северо-западный» угол и отправляем туда максимально возможную поставку. И так далее.

В результате получаем опорный план, в котором заполненными (базисными) являются n + m – 2 = 5 + 3 – 2 = 6 клеток.

 

 

 

 

Таблица 3-Таблица метода «северо-западного» угла

База

Магазин

Запасы  
продукции, ai

В1

В2

В3

В4

В5

А1

30

  

20

              

50/20/-

 

7

  

6

  

8

  

10

  

12

А2

        

55

  

5

      

60/5/-

 

9

  

5

  

7

  

4

  

6

А3

            

15

  

25

  

40/25/-

 

6

  

8

  

4

  

9

  

7

Спрос  
на продукцию, bj

30/-

20/-

55/-

20/15/-

25/-

150


Этому плану соответствует значение целевой функции:

Fсз = 30·7+20·6+55·7+5·4+15·9+25·7 = 1045.

2 метод. Метод наименьших затрат

Согласно этому методу на каждом шаге заполняется клетка с минимальным коэффициентом затрат.

В таблице поставок 4 находим клетку с наименьшим коэффициентом затрат. Это клетка (3; 3) с коэффициентом затрат, равным 4 (если таких клеток несколько, то выбираем ту, в которую возможна максимальная поставка), причём x33 = min{40} = 0.

Таблица 4-Таблица метода наименьших затрат

База

Магазин

Запасы  
продукции, ai

В1

В2

В3

В4

В5

А1

30

      

15

      

5

  

50

 

7

  

6

  

8

  

10

  

12

А2

    

20

      

20

      

60

 

9

  

5

  

7

  

4

  

6

А3

        

40

      

20

  

40/-

 

6

  

8

  

4

  

9

  

7

Спрос  
на продукцию, bj

30

20

55

20

25

150


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

 

Таблица 5- Таблица метода наименьших затрат

База

Магазин

Запасы  
продукции, ai

В1

В2

В3

В4

В5

А1

30

      

15

      

5

  

50

 

7

  

6

  

8

  

10

  

12

А2

    

20

      

20

      

60/40

 

9

  

5

  

7

  

4

  

6

А3

        

40

      

20

  

40/-

 

6

  

8

  

4

  

9

  

7

Спрос  
на продукцию, bj

30/-

20/-

55

20

25

150


 

В оставшейся таблице 5 наименьший коэффициент затрат равен 4 и находится в клетке (2; 4), x24 = min{20, 60} = 40. При этом из рассмотрения выбывает второй столбец.

Продолжая заполнение таблицы шаг за шагом (табл. 6), получаем x22 = min{20, 40} = 20, x25 = min{20, 20} = 0, x11 = min{30} = 20, x13 = min{20, 15} = 5, x15{5}=0. В результате получаем опорный план, в котором заполненными (базисными) являются 6 клеток.

Таблица 6- Таблица метода наименьших затрат

База

Магазин

Запасы  
продукции, ai

В1

В2

В3

В4

В5

А1

30

      

15

      

5

  

50/20/-

 

7

  

6

  

8

  

10

  

12

А2

    

20

      

20

      

60/40/20/-

 

9

  

5

  

7

  

4

  

6

А3

        

40

      

20

  

40/-

 

6

  

8

  

4

  

9

  

7

Спрос  
на продукцию, bj

30/-

20/-

55/15/-

20/-

25/5/-

150


Соответствующее значение целевой функции равно:

Fнз = 30·7+20·5+ 15·8+40·4+20·4+5·12+20·6 = 850.

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

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