3. Задача о «расшивке узких мест производства»

При выполнении оптимальной производственной программ первый и третий ресурсы используются полностью, то есть образуют “узкие места производства”. Буду заказывать их дополнительно. Пусть T= (t₁,t₂,t₃) – вектор дополнительных объёмов ресурсов.

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

Так как я использую найденные двойственные оценки ресурсов, то должно выполняться условие:

H + Q^-1T ³ 0

Задача состоит в том, чтобы найти векторТ(t₁;0;t₃), максимизирующий суммарный прирост прибыли

W = 7t₁ + 5t₃

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы).

20 -1/4 0 1/4t₁ 0

6 + - 1/8 1 - 3/8 ·0 ≥ 0

24 5/16 0 - 1/16 t₃ 0

предполагая, что дополнительно можно получить не более 1/3 первоначального объема ресурса каждого вида

t₁ 116

0 ≤1/3 94

t₃ 196

причем по смыслу задачи t₁≥0,t₃≥0

Переписав неравенства (2) и (3) в виде:

1/4t₁ – 1/4t₃ ≤ 20 t₁ – t₃ ≤ 80

1/8 t₁ + 3/8 t₃≤ 6 t₁ + 3t₃≤ 48

1/16 t₃ - 5/16 t₁≤ 24 t₃ - 5t₁≤ 384

t₁ ≤ 116/3, t₃ ≤ 196/3

прихожу к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4). Эту задачу легко решить графически: см. рис.1.

По графику видно, что решение данной задачи находится в точке А(116/3;28/9). Таким образом, программа «Расшивки узких мест производства» имеет вид:t₁=116/3, t₂=0, t₃=28/9и прирост прибыли составитW = 7*116/3+ 5*28/9 = 2576/9

Сводная таблица результатов:

Cj	48	15	11	32	Bi	X4+i	Yi	Ti
	4	2	3	1	116	0	7	116/3
aij	2	0	3	2	94	94	0	0
	4	1	0	5	196	0	5	28/9
Xj	24	0	0	80	1792			2576/9
j	0	4	10	0

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

Имеется 3 производителя однородной продукции, имеющие запасы этой продукции 90, 75 и 40 единицы соответственно. Также имеется 4 потребителя данной продукции. Их потребность составляет 48, 75, 41 и 32 единицы соответственно. Транспортная компания заключила контракт с поставщиками и потребителями на вывоз и поставку данной продукции от производителей к потребителям. При перевозке продукции от каждого производителя к каждому потребителю транспортная компания имеет определённые издержки на единицу продукции: 4 у.е. при перевозке от 1-ого производителя к 1-ому потребителю, 1 у.е. - от 1–ого производителя ко 2-ому потребителю, 3 у.е. – от 1-ого к 3-ему, 1 у.е. – от 1-ого к 4-ому, 4 у.е. – от 2-ого к 1-ому, 1 у.е. – от 2-ого ко 2-ому, 3 у.е. – от 2-ого к 3-ему, 2 у.е. – от 2-ого к 4-ому, 5 у.е. – от 3-его к 1-ому, 2 у.е. – от 3-его ко 2-ому, 3 у.е. – от 3-его к 3-ему, 5 у.е. – от 3-его к 4-ому. Так как естественным стремлением транспортной компании является максимизация прибыли, то требуется составить такой план перевозок, чтобы издержки были минимальными.

Можно записать эти издержки на единицу продукции в виде матрицы, где строка издержки при поставке от одного производителя к каждому потребителю, а столбец издержки при поставке к одному потребителю от каждого производителя:

4 1 3 1

C= 4 1 3 2

5 2 3 5

Предложение производителей и спрос потребителей можно записать в виде векторов А иBсоответственно:

90 48

А = 75 и В = 75

40 41

32

Обозначу через x_ijколичество груза, планируемого к перевозке отi- го поставщикаj- му потребителю. При наличии баланса производства и потребления

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

найти план перевозок

X = (x_ij), i = 1,m; j = 1,n,

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

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

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

причём по смыслу задачи

x₁₁ > 0,…, x_mn > 0

В моей задаче 4 потребителя и 3 поставщика, причём суммарный объем производства a_i = 90 + 75 + 40 = 205 больше, чем требуется всем потребителямb_i = 48 + 75 + 41 + 32 = 196, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую ввожу фиктивный пункт потребления с объемом потребления 205-196 = 9 единиц, причем тарифы на перевозку в этот пункт я условлюсь считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение легко построить по правилу северо-западного угла:

Трансп.табл.1

Потребление	b1 =48	b2 =75	b3 =41	b4 =32	b5 =9
Производство
a1= 90	48 ^4	42 ^1	^3	^1	^0	p1=0
a2= 75	^4	33 ^1	41 ^3	1 ^2	^0	p2=0
a3= 40	^5	^2	* ^3	31 ^5	9 ^0	p3=3
	q1=4	q2=1	q3=3	q4=2	q5=-3

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

Обозначим через )

вектор симплексных множителей или потенциалов. Тогда

_ij=A_ij- с_ij i= 1,m;j= 1,n

откуда следует_ij=p_i+q_j-c_iji= 1,m;j= 1,n(6)

Один из потенциалов можно выбрать произвольно, так как в системе (3), (4) одно уравнение линейно зависит от остальных. р₁= 0. Остальные потенциалы нахожу из условия, что для базисных клеток. В данном случае получаем

₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0+q₁ –4 = 0, q₁ = 4

₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0+q₂ –1 = 0, q₂ = 1

₂₂ = 0, p₂ + q₂ – c₂₂ = 0, p₂+1 –1 = 0, p₂ = 0

₂₄ = 0, p₂ + q₄ – c₂₄ = 0, 0+q₄ –2 = 0, q₄ = 2

₂₃ = 0, p₂ + q₃ - c₂₃ = 0, 0 + q₃ – 3 = 0, q₃ = 3

₃₄ = 0, p₃ + q₄ – c₃₄ = 0, p₃+ 2 – 5 = 0, p₃ = 3

₃₅ = 0, p₃ + q₅ – c₃₅ = 0, 3 + q₅ – 0 = 0, р₂ = -3

Затем по формуле (6) вычисляю оценки всех свободных клеток:

₂₁ = p₂ + q₁ - c₂₁ = 0+4-4 = 0

₃₁ = p₃ + q₁ - c₃₁ = 3+4-5 = 2

₃₂ = p₃ + q₂ - c₃₂ = 3+1-2 = 2

₁₃ = p₁ + q₃ – c₁₃ = 0+3-3 = 0

₁₄ = p₁ + q₄ – c₁₄ = 0+2-1 = 1

₃₃ = p₃ + q₃ – c₃₃ = 3+3-3 = 3

₁₅ = p₁ + q₅ – c₁₅ = 0-3-0 = -3

₂₅ = p₂ + q₅ – c₂₅ = 0-3-0 = -3

Нахожу наибольшую положительную оценку max() = 3 =₃₃

Для найденной свободной клетки 33 строю цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 33-23-24-34. Произвожу перераспределение поставок вдоль цикла пересчета

41	1
*	31

41-	1+
	31-

10	32
31

= 31

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

Трансп.табл.2

Потребление	b1 =48	b2 =75	b3 =41	b4 =32	b5 =9
Производство
a1= 90	48 ^4	42 ^1	^3	*^1	^0	p1=0
a2= 75	^4	33 ^1	10 ^3	32 ^2	^0	p2=0
a3= 40	^5	^2	31 ^3	^5	9 ^0	p3=0
	q1=4	q2=1	q3=3	q4=2	q5=0

Нахожу новые потенциалы, новые оценки:

₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0+q₁ –4 = 0, q₁ = 4

₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0+q₂ –1 = 0, q₂ = 1

₂₂ = 0, p₂ + q₂ – c₂₂ = 0, p₂+1 –1 = 0, p₂ = 0

₂₄ = 0, p₂ + q₄ – c₂₄ = 0, 0+q₄ –2 = 0, q₄ = 2

₂₃ = 0, p₂ + q₃ - c₂₃ = 0, 0 + q₃ – 3 = 0, q₃ = 3

₃₃ = 0, p₃ + q₃ – c₃₃ = 0, p₃+ 3 – 3 = 0, p₃ = 0

₃₅ = 0, p₃ + q₅ – c₃₅ = 0, 0 + q₅ – 0 = 0, q₅ = 0

Затем по формуле (6) вычисляю оценки всех свободных клеток:

₂₁ = p₂ + q₁ - c₂₁ = 0+4-4 = 0

₃₁ = p₃ + q₁ - c₃₁ = 0+4-5 = -1

₃₂ = p₃ + q₂ - c₃₂ = 0+1-2 = -1

₁₃ = p₁ + q₃ – c₁₃ = 0+3-3 = 0

₁₄ = p₁ + q₄ – c₁₄ = 0+2-1 = 1

₃₄ = p₃ + q₄ – c₃₄ = 0+2-5 = -3

₁₅ = p₁ + q₅ – c₁₅ = 0-0-0 = 0

₂₅ = p₂ + q₅ – c₂₅ = 0-0-0 = 0

Нахожу наибольшую положительную оценку max() = 1 =₁₄

Для найденной свободной клетки 14 строю цикл пересчета 14-12-22-24. Произвожу перераспределение поставок вдоль цикла пересчета

42			*
33	10		32

42-		
33+	10	32-

10		32
65	10

= 32

Получаю третье базисное допустимое решение:

Трансп.табл.3

Потребление	b1 =48	b2 =75	b3 =41	b4 =32	b5 =9
Производство
a1= 90	48 ^4	10 ^1	^3	32^1	^0	p1=0
a2= 75	^4	65 ^1	10 ^3	^2	^0	p2=0
a3= 40	^5	^2	31 ^3	^5	9 ^0	p3=0
	q1=4	q2=1	q3=3	q4=1	q5=0

Нахожу новые потенциалы, новые оценки:

₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0+q₁ –4 = 0, q₁ = 4

₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0+q₂ –1 = 0, q₂ = 1

₂₂ = 0, p₂ + q₂ – c₂₂ = 0, p₂+1 –1 = 0, p₂ = 0

₁₄ = 0, p₁ + q₄ – c₁₄ = 0, 0+q₄ –1 = 0, q₄ = 1

₂₃ = 0, p₂ + q₃ - c₂₃ = 0, 0 + q₃ – 3 = 0, q₃ = 3

₃₃ = 0, p₃ + q₃ – c₃₃ = 0, p₃+ 3 – 3 = 0, p₃ = 0

₃₅ = 0, p₃ + q₅ – c₃₅ = 0, 0 + q₅ – 0 = 0, q₅ = 0

Затем по формуле (6) вычисляю оценки всех свободных клеток:

₂₁ = p₂ + q₁ - c₂₁ = 0+4-4 = 0

₃₁ = p₃ + q₁ - c₃₁ = 0+4-5 = -1

₃₂ = p₃ + q₂ - c₃₂ = 0+1-2 = -1

₁₃ = p₁ + q₃ – c₁₃ = 0+3-3 = 0

₂₄ = p₂ + q₄ – c₂₄ = 0+1-2 = -1

₃₄ = p₃ + q₄ – c₃₄ = 0+1-5 = -4

₁₅ = p₁ + q₅ – c₁₅ = 0-0-0 = 0

₂₅ = p₂ + q₅ – c₂₅ = 0-0-0 = 0

Я получила таблицу, для которой все

_ij  0 i = 1,m; j = 1,n

Оценки удовлетворяют условию оптимальности, следовательно решение

48 10 0 32 0

X= 0 65 10 0 0

0 0 31 0 9 оптимально.

При этом 9 единиц продукции остаются у 3-го производителя.

Общая стоимость перевозок = 4*48+10*1+32*1+65*1+10*3+31*3= 422 ед.