Транспортная задача линейного программирования

 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ…………………………………………………………………… 4

1.ТРАНСПОРТНАЯ ЗАДАЧА………………………………………………. 5

1.1 Общая постановка задачи………………………………………… 5

1.2 Нахождение исходного  опорного решения……………………... 8

1.3 Проверка найденного  опорного решения на оптимальность…... 9

1.4 Переход от одного  опорного решения к другому………………. 9

2. РЕШЕНИЕ ТРАНСПОРТНЫХ  ЗАДАЧ…………………………………. 10

2.1 Пример решения задачи  транспортным методом………………. 10

2.2 Экономический вывод  задачи……………………………………. 19

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ ………………………………………………...21

 

ВВЕДЕНИЕ

Я выбрал эту тему курсовой работы, потому что каждый человек, ежедневно не всегда осознавая это  решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь  наибольшего эффекта, имея ограниченные средства, надо составить план, или  программу действий. В середине ХХ века был создан специальный математический аппарат помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.

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

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

Для реализации данной цели в работе необходимо решить следующие  задачи;

-рассмотреть транспортную  задачу, общую постановку, цели, задачи;

-изучить основные типы, виды моделей;

-охарактеризовать методы  решения транспортной задачи;

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

1.ТРАНСПОРТНАЯ ЗАДАЧА

1.1 Общая постановка задачи

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

          В общем виде задачу можно  представить следующим образом:  в m пунктах производства A1, A2 ,…, Am имеется однородный груз в количестве соответственно a1, a2,…,am. Этот груз необходимо доставить в n пунктов назначения B1, B2,…, Bn в количестве соответственно b1, b2,…, bn. Стоимость перевозки единицы груза (тариф) из пункта Ai в пункт Bj равна cij.

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

           В зависимости от соотношения  между суммарными запасами груза  и суммарными потребностями в  нем транспортные задачи могут  быть закрытыми и открытыми.

Если

 

 

то задача называется закрытой. Если

то открытой.

 

Обозначим через хij количество груза, перевозимого из пункта Ai в пункт Bj. Рассмотрим закрытую транспортную задачу. Ее условия запишем в распределительную таблицу которую будем использовать для нахождения решения.

 

Bj Ai	B1	B2	…	Bj	…	Bn
	b1	b2	…	bj	…	bn
A1     a1	c11 x11	c12 x12	…	c1j x1j	…	c1n x1n
A2     a2	c21 x21	c22 x22	…	c2j x2j	…	c2n x2n
…	…	…	…	…	…	…
Ai      ai	ci1 xi1	ci2 xi2	…	cij xij	…	cin xin
…	…	…	…	…	…	…
Am   am	cm1 xm1	cm2 xm2	…	cmj xmj	…	cmn xmn

Таблица 1

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

при ограничениях:

Оптимальным решением задачи является матрица

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

- нахождение исходного  опорного решения

- проверка этого решения  на оптимальность

- переход от одного  опорного решения к другому

Рассмотрим каждый из этих этапов.

 

1.2 Нахождение исходного  опорного решения

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

Рассмотрим один из них  – метод минимального тарифа (элемента). Согласно этому методу, грузы распределяются в первую очередь в те клетки, в которых находится минимальный  тариф перевозок cij. Далее поставки распределяются в незанятые клетки с наименьшими тарифами с учетом оставшихся запасов у поставщиков и удовлетворения спроса потребителей. Процесс распределения продолжают до тех пор, пока все грузы от поставщиков не будут вывезены, а потребители не будут удовлетворены. При распределении грузов может оказаться, что количество занятых клеток меньше, чем m+n-1. В этом случае недостающее их число заполняется клетками с нулевыми поставками, такие клетки, такие клетки называют условно занятыми.

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

Найденное исходное опорное  решение проверяется на оптимальность  методом потенциалов по следующему критерию: если опорное решение транспортной задачи является оптимальным, то ему  соответствует система m+n действительных чисел ui и vj, удовлетворяющих условиям ui + vj= cij, для занятых клеток и ui +vi – cij ≤ 0 для свободных клеток. Одному из потенциалов дается произвольное значение, например u1 = 0, тогда остальные потенциалы определяются однозначно. Так, если известен потенциал vj, то ui = cij - vj.

Обозначим ∆ij = ui+vj-cij. Эту оценку называют оценкой свободных клеток. Если ∆ij ≤ 0, то опорное решение является оптимальным. Если хотя бы одна из оценок ∆ij > 0, то опорное решение не является оптимальным и его можно улучшить перейдя от одного опорного решения к другому.

1.4 Переход от одного  опорного решения к другому

Наличие положительной оценки свободной клетки ( ∆ij > 0) при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению. Свободная клетка становится занятой становится занятой, а одна из ранее занятых - свободной.

Для свободной клетки с  ∆ij > 0 строится цикл (цепь, многоугольник), все вершины которого кроме одной находятся в занятых клетках; углы прямые, число вершин четное. Около свободной клетки цикла ставится знак (+), затем поочередно проставляют знаки (-) и (+). У вершин со знаком (-) выбирают минимальный груз, его прибавляют к грузам, стоящим у вершин со знаком (+), и отнимают от грузов у вершин со знаком (-). В результате перераспределения груза получим новое опорное решение. Это решение проверяем на оптимальность, и т.д. с тех пор, пока не получим оптимальное решение.

2. РЕШЕНИЕ ТРАНСПОРТНЫХ  ЗАДАЧ

2.1 Пример решения задачи  транспортным методом

В качестве примера возьмём  следующую задачу:

Четыре предприятия данного  технологического района для производства продукции используют три вида сырья, потребности в сырье каждого  из предприятий соответственно равны  150, 120, 80, 50 единиц. Сырьё сосредоточено в трёх местах его получения, а запасы соответственно  100, 130, 170 единиц. Тарифы перевозок известны и заданы матрицей:

2	1	8	12
5	3	7	5
3	7	14	4

 

Для начала выясним, какая  это задача, а для этого сравним  общее количество сырья на складах  и общее количество потребления:

А = 100+130+170=400

В = 150+120+80+50 = 400

А = В – из этого следует, что задача является закрытой.

 

 

 

 

 

 

 

 

 

 

 

 

Шаг 1.

Составим таблицу, расставим  тарифы и сделаем распределение:

Ai	Bj	b1		b2		b3		b4		Ui
		150		120		80		50
a1	100	2	100	1		8		12
a2	130	5	50	3	80	7		5
a3	170	3		7	40	14	80	4
Vg

Таблица 2

Распределение выполнили. Можно  найти коэффициент затрат на перевозки  сырья F. С ходом решения этот коэффициент должен только уменьшаться, по сравнению с предыдущим.

 F = 2*100+5*30+3*80+7*40+14*80 = 2290 единиц.

Коэффициент высокий, и нам  нужно выяснить, сможем ли мы уменьшить  его, а для этого проанализируем это, но для начала нам нужно сделать  оценку свободных клеток, а для  этого сделаем следующее: в столбце  V_j в первой строчки поставим 0. А дальше напротив этого нуля найдём заполненную клетку и производим вычисления по формуле:

c_ij=u_i+v_j

 

В итоге у нас получится  вот такая таблица:

 

Ai	Bj	b1		b2		b3		b4		Ui
		150		120		80		50
a1	100	2		1		8		12		0
a2	130	5		3		7		5		3
a3	170	3		7		14		4		7
Vg			2	0		7		-3

Таблица 3

Теперь мы можем выяснить, можем ли мы уменьшить коэффициент  F, а для этого теперь работает с пустыми клетками.

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

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