Формулировка линейной производственной задачи

- 2/3 t1 + 1/2t3 = 26 – ограничивающая прямая I      Множество точек треугольника, ребрами

                1/2t3 =  4 – ограничивающая прямая II      которого являются I,II и III прямые, образует      

  1/3t1 – 1/2t3  = 36 – ограничивающая прямая III    область устойчивости двойственных оценок ресурсов, в которой сохраняется структура программы производства.

          t1 = 186/3

                                - ограничивающие прямые IV, V

          t3 = 196/3

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

Построим вектор-градиент grad W = (0, 0); (6, 5), указывающий направление наискорейшего возрастания функции W. Линии уровня функции W перпендикулярны вектору-градиенту grad W и образуют семейство параллельных прямых.

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

Определяем, что максимального  значения в области допустимого  множества функция W достигнет в точке Q, которая является пересечением II и IV прямых. Следовательно, координаты этой точки определяют оптимальное дополнительное количество ресурсов:

     t1 = 186/3                        t1* = 62

     1/2t3 =  4                         t3* = 8

 

Максимальный дополнительно  возможный прирост прибыли за счет увеличения количества дефицитных ресурсов равен:

W* = 6t1* + 5t3* = 6*62 + 5*8 = 412 денежных единиц

Сводка результатов  по 1-му,2-му заданиям приведена в  таблице:

 

сj	38	12	28	21	b		x4+i	y*i	t*i
	3	0	3	3	186		0	6	62
aij	2	3	1	1	102		4	0	0
	4	3	2	2	196		0	5	8
х*j	36	0	26	0	2096				412
Δj	0	3	0	7

3. ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

Задание

Составить математическую модель транспортной задачи, взяв следующие исходные данные:

                                             

                       Вектор объемов потребления

Вектор объемов производства		38	42	28	41	Матрица транспортных издержек
	60	3	2	4	3
	50	5	3	1	4
	48	4	3	6	1

 

 

Если полученная модель окажется открытой, то свести ее к замкнутой  и найти оптимальное решение  транспортной задачи методом потенциалов.

 

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

 

Транспортная  задача линейного программирования может быть сформулирована следующим образом:

Известны:

• Вектор объемов производства, указывающий количество однородного продукта, сосредоточенное в каждом из трех пунктов производства (хранения):

• Вектор объемов потребления, указывающий количество данного продукта, необходимое каждому из четырех пунктов потребления:

 

В ( 38, 42, 28, 41 )

 

• Матрица транспортных издержек С, в которой каждый элемент с_ij означает стоимость перевозки единицы продукта из i-го пункта отправления (производства) в j-ый пункт назначения (потребления):

Требуется:

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

 

Составим математическую модель транспортной задачи:

Общий объем производства åа_i = 60 + 50 + 48 = 158 единиц.

Общий объем потребления åb_j = 38 + 42 + 28 + 41 = 149 единиц.

Таким образом, объем  производства больше объема потребления åа_i > åb_j на 9 единиц, следовательно, данная модель транспортной задачи является открытой.

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

 

 

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

 

1) Найти план перевозок (какое количество продукции из какого пункта производства и в какой пункт потребления необходимо перевезти)

 

2) минимизирующий общую  стоимость всех перевозок

L = = 3х11 + 2х12 +4х13 +3х14 +5х21 +3х22 +х23 +4х24 +4х31 +3х32 +6х33 +х34 → min

3) при условии, что  из любого пункта производства  вывозится весь продукт:

х11 + х12 + х13 + х14 + х’15 = 60

х21 + х22 + х23 + х24 + х’25 = 50

х31 + х32 + х33 + х34 + х’35 = 48

4) и любому потребителю  доставляется необходимое количество груза:

х11 + х21 + х31 = 38

х12 + х22 + х32 = 42

х13 + х23 + х33 = 28

х14 + х24 + х34 = 41

                                                    х’15 + х’25 + х’35 = 9

5) где по смыслу  задачи              х11, х12, х13, х14, х’15, х21, х22, х23, х24, х’25, х31, х32, х33, х34, х’35 ≥ 0                                                       

 

3.2. Решение  транспортной задачи методом  потенциалов.

 

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

 

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

 

Следует иметь в виду, что по любой транспортной таблице  можно восстановить предпочитаемый эквивалент системы уравнений 3) – 4), а в таблице записаны лишь правые части уравнений, причем номер клетки показывает, какая неизвестная в соответствующем уравнении является базисной. Так как в системе 3) – 4) ровно (m + n – 1) линейно независимых уравнений, то в любой транспортной таблице должно быть m + n – 1 занятых клеток. 

 

Потребление Производство	b1 = 38		b2 = 42		b3 = 28		b4 = 41		b’5 = 9
a1 = 60	38	3	22	2		4		3		0	p1 = 0
a2 = 50		5	20	3	28	1	2 –	4	*           +	0	p2 = 1
a3 = 48		4		3		6	39 +	1	9           –	0	p3 = - 2
	q1  = 3		q2  = 2		q3  = 0		q4  = 3		q5  = 2

Решаем транспортную задачу методом потенциалов, в соответствии с которым каждому пункту производства ставится в соответствие потенциал pi, а каждому пункту потребления – потенциал qj.

Обозначим через μ (p1, p2, p3, q1, q2, q3, q4) вектор симплексных множителей или потенциалов.

Каждой клетке транспортной таблицы соответствует некоторая  оценка:

                                                 D_ij = p_i + q_j - c_ij                    i = 1, 2, 3;   j = 1, 2, 3, 4 

Один из потенциалов  можно выбрать произвольно, так  как в системе уравнений 3) – 4)одно уравнение линейно зависит от остальных.

Положим, что p1 = 0

Остальные потенциалы находим  из условия, что для базисных клеток D_ij = 0:

D₁₁ = 0,  p₁ + q₁ - c₁₁ = 0, 0 + q₁ - 3 = 0,            q₁ = 3

D₁₂ = 0,  p₁ + q₂ - c₁₂ = 0, 0 + q₂ -2 = 0,            q₂ = 2

D₂₂ = 0,  p₂ + q₂ - c₂₂ = 0, р₂ + 2 -  3 = 0,            р₂ = 1

D₂₃ = 0,  p₂ + q₃ – c₂₃ = 0, 1 + q₃ - 1 = 0,            q₃ = 0

D₂₄ = 0,  p₂ + q₄ – c₂₄ = 0, 1 + q₄ - 4 = 0,            q₄ = 3

D₃₄ = 0,  p₃ + q₄ – c₃₄ = 0, р₃ + 3 - 1 = 0,            р₃ = - 2

D₃₅ = 0,  p₃ + q₅ – c₃₅ = 0, -2 + q₅ - 0 = 0,            q₅ = 2

 

Вычисляем оценки всех свободных клеток вычисляем по формуле D_ij = p_i + q_j - c_ij:

D₁₃ = p₁ + q₃ - c₁₃ = 0 + 0 - 4 = - 4

D₁₄ = p₁ + q₄ - c₁₄ = 0 + 3 - 3 = 0

D₁₅ = p₁ + q₅ – c₁₅ = 0 + 2 - 0 = 2

D₂₁ = p₂ + q₁ - c₂₁ = 1 + 3 - 5 = - 1

D₂₅ = p₂ + q₅ - c₂₅ = 1 + 2 - 0 = 3

D₃₁ = p₃ + q₁ – c₃₁ = - 2 + 3 - 4 = - 3

D₃₂ = p₃ + q₂ – c₃₂ = - 2 + 2 - 3 = - 3

D₃₃ = p₃ + q₃ – c₃₃ = - 2 + 0 - 6 = - 8

 

Находим наибольшую положительную  оценку:

max (

) = 3 =

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

Это будет 25 – 24 – 34 – 35. Клетка 25 помечается знаком «плюс», далее  соседние вершины цикла пересчета  помечаются по очереди знаками «минус»  и «плюс». Выбирается минимальная  из поставок, отмеченных знаком «минус» ρ max, и к поставкам, отмеченным знаком «плюс» добавляется ρ max, а из поставок, отмеченных знаком «минус», вычитается ρ max

ρ max = 2                      производим перераспределение поставок вдоль цикла пересчета

2	*		2 - r	r		0	2
39	9		39 + r	9 - r		41	7

Получаем второе базисное допустимое решение и заполняем вторую транспортную таблицу

Потребление Производство	b1 = 38		b2 = 42		b3 = 28		b4 = 41		b’5 = 9
a1 = 60	38	3	22	2		4		3		0	p1 = 0
a2 = 50		5	20	3	28	1		4	2	0	p2 = 1
a3 = 48		4		3		6	41	1	7	0	p3 = 1
	q1  = 3		q2  = 2		q3  = 0		q4  = 0		q5  = - 1