Курсовая: Прикладная математика

Курсовая: Прикладная математика

трех переменных это будет "езда" по ребрам многогранника допустимых решений

от одной вершины к другой до достижения оптимальной вершины).

§5. Двойственная задача

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

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

технологиям.

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

(Петров), занимающийся производством каких-то других видов продукции, но с

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

нам "уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает

платить у1 рублей за каждую единицу первого ресурса, у2

руб – второго, у3 руб – третьего. Возникает вопрос: при каких ценах у

1, у2, у3 мы можем согласиться с предложением П.

Величины у1, у2, у3 принято называть

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

в которых действует наше предприятие.

Напомним, что в нашей задаче технологическая матрица А, вектор объемов

ресурсов В и вектор удельной прибыли С имели вид

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

из матрицы А, 4 единицы ресурса первого вида, 2 единицы ресурса второго вида и

3 единицы третьего (элементы первого столбца матрицы). В ценах у1, у

2, у3 наши затраты составят 4у1 + 2у2 +

3у3, т.е. столько заплатит предприниматель П за все ресурсы, идущие

на производство единицы первой продукции. На рынке за единицу первой продукции

мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с

предложением П только в том случае, если он заплатит не меньше

4у1 + 2у2 + 3у3 ³ 36.

Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на

производство единицы продукции второго вида. В ценах П эти затраты составят 3у

1 + 5у2 + у3, а на рынке за единицу продукции

второго вида мы получили бы прибыль 14 рублей. Поэтому перед предпринимателем П

мы ставим условие

3у1 + 5у2 + у3 ³ 14

и т.д. по всем видам продукции.

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить

208у1 + 107у2 + 181у3

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

значения величин у1, у2, у3, чтобы эта сумма

была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым

мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно

зависят от применяемых нами технологий, объемов ресурсов и от ситуации на

рынке.

16

Таким образом, проблема определения расчетных оценок ресурсов приводит к

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

у(у1, y2, y3)

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

f = 208y1 + 107y2 +181y3 (1)

при условии, что по каждому виду продукции суммарная оценка всех ресурсов,

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

получаемой от реализации единицы этой продукции

(2)

4y1 + 2y2 + 3y3 ³ 36

3y1 + 5y2 + y3 ³ 14

4y1 + 2y3 ³ 25

5y1 + 2y2 + 5y3 ³ 50

причем оценки ресурсов не могут быть отрицательными

y10, y20, y30. (3)

Решение полученной задачи легко найти с помощью второй основной теоремы

двойственности, согласно которой для оптимальных решений

(х1, х2, х3, х4) и

(y1, y2, y3) пары двойственных задач необходимо

и достаточно выполнение условий

x 1 (4y1 + 2y2 + 3y3 - 36) = 0

y1 (4x1 +3x2 + 4x3 +

5x4 - 208) = 0

x 2 (3y1 + 5y2 + y3 - 14) = 0

y2 (2x1 +5x2 + 2x

4 - 107) = 0

x 3 (4y1 + 2y3 - 25) = 0

y3 (3x1 + x2 + 2x3 +

5x4 - 181) = 0 .

x 4(5y1 + 2y2 + 5y3 - 50) = 0

Ранее было найдено, что в решении исходной задачи х1>0, x4>0. Поэтому

4y1 + 2y2 + 3y3 - 36 = 0

5y1 + 2y2 + 5y3 - 50 = 0

Если же учесть, что второй ресурс был избыточным и, согласно той же теореме

двойственности, ее двойственная оценка равна нулю

у2=0,

то приходим к системе уравнений

4y1 + 3y3 - 36 = 0

5y1 + 5y3 - 50 = 0

откуда следует

у1=6, у3=4.

Таким образом, получили двойственные оценки ресурсов

у1=6; у2=0; у3=4,

(4)

причем общая оценка всех ресурсов равна 1972.

17

Заметим, что решение (4) содержалось в последней строке последней симплексной

таблицы исходной задачи. Важен экономический смысл двойственных оценок.

Например, двойственная оценка третьего ресурса у3=4 показывает, что

добавление одной единицы третьего ресурса обеспечит прирост прибыли в 4

единицы.

§6. Задача о "расшивке узких мест производства"

При выполнении оптимальной производственной программы первый и третий ресурсы

используются полностью, т.е. образуют ²узкие места производства².

Будем их заказывать дополнительно. Пусть T(t1,t2,t3

)- вектор дополнительных объемов ресурсов. Так как мы будем использовать

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

H + Q-1T 0.

Задача состоит в том, чтобы найти вектор

T (t1, 0, t3),

максимизирующий суммарный прирост прибыли

W = 6t1 + 4t3

(1)

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

структуры производственной программы)

(2)

предполагая, что можно надеяться получить

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

(3)

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

t1 0, t3 0. (4)

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

(6)

(5)

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

Эту задачу легко решить графически: см. рис. 1. Программа

²расшивки² имеет вид

t1=, t2=0, t3=

18

и прирост прибыли составит 519.

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

Таблица 1

сj	36	14	25	50	b	x4+i	yi	ti
	4	3	4	5	208	0	6	46 5/12
aij	2	5	0	2	107	13	0	0
	3	1	2	5	181	0	4	60 1/3
xj	27	0	0	20	1972			519 2/3
Dj	0	8	7	0

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

Транспортная задача формулируется следующим образом. Однородный продукт,

сосредоточенный в m пунктах производства (хранения) в количествах а

1, а2,..., аm единиц, необходимо распределить между

n пунктами потребления, которым необходимо соответственно b1, b

2,..., bn единиц. Стоимость перевозки единицы продукта из i-го

пункта отправления в j-ый пункт назначения равна сij и известна для

всех маршрутов. Необходимо составить план перевозок, при котором запросы всех

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

производства и общие транспортные расходы по доставке продуктов были

минимальными.

Обозначим через хij количество груза, планируемого к перевозке от

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

потребления

(1)

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

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

Х = (хij), i = 1,m; j = 1,n

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

(2)

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

(3)

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

(4)

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

х11 > 0 ,. . . ., xmn > 0.

(5)

19

Для решения транспортной задачи чаще всего применяется метод потенциалов

. Пусть исходные данные задачи имеют вид

А(а1, а2, а3) = (54; 60; 63); В(b1

, b2, b3, b4) = (41; 50; 44; 30); С =

Общий объем производства åаi = 55+60+63 = 178 больше, требуется

всем потребителям åbi = 42+50+44+30 = 166, т.е. имеем открытую

модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный

пункт потребления с объемом потребления 178-166 = 12 единиц, причем тарифы на

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

добавляемые к левым частям неравенств для превращения их в уравнения, входят в

функцию цели с нулевыми коэффициентами.

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

западного угла².

Потребление	b1 =41	b2 =50	b3 =44	b4 =30	b5 =12
Производство
а1 =54	41	13				p1 =0
a2 =60		37	23			p2 =
a3 =63	*		21	30	12	p3 =
	q1 =	q2 =	q3 =	q4 =	q5 =

Следует иметь в виду, что по любой транспортной таблице можно восстановить

соответствующий предпочитаемый эквивалент системы уравнений (3), (4), а в

таблице записаны лишь правые части уравнений, причем номер клетки показывает,

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

системе (3), (4) ровно m + n - 1 линейно независимых уравнений, то в любой

транспортной таблице должно быть m + n - 1 занятых клеток.

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

m)

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

Dij = mAij - сij i = 1,m; j = 1,n

откуда следует

Dij = pi + qj - cij i =

1,m; j = 1,n (6)

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

уравнение линейно зависит от остальных. Положим, что р1 = 0.

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

. В данном случае получаем

D11 = 0, p1 + q1 - c11 = 0, 0+q1 -1 = 0, q1 = 1

D12 = 0, p1 + q2 - c12 = 0, 0+q2 -4 = 0, q2 = 4

D22 = 0, p2 + q2 - c22 = 0, р2 +4-6 = 0, р2 = 2

и т.д., получим: q3=0, p3=6, q4= 1, q5= -6.

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

D21 = p2 + q5 - c21 = 2+1-3 = 0

D31 = p3 + q1 - c31 = 6+1-2 = 5

D32 = 5; D13 = -3; D14 = -1; D24 = -2; D15 = -6; D25 = -4.

20

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

max () = 5 =

Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную

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

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

свободной клетке, а все остальные - в занятых клетках. Это будет 31-11-12-22-

23-33. Производим перераспределение поставок вдоль цикла пересчета

41	13			41-r	13+r			20	34
	37	23			37-r	23+r			16	44
		21		r		21-r		21

= 21

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

bj	b1 =41	b2 =50	b3 =44	b4 =30	b5=12
ai
а1 =54	20	34		*		p1 =0
a2 =60		16	44			p2 =2
a3 =63	21			30	12	p3 =1
	q1 =1	q2 = 4	q3 = 0	q4 = 6	q5= -1

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

иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34

производим перераспределение

20			20-r	r			20
21	30		21+r	30-r		42	10

rmax = 20

и получаем третье базисное допустимое решение. Продолжаем процесс до те пор,

пока не придем к таблице, для которой все

Dij £ 0 i = 1,m; j = 1,n

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

допустимое решение

§8. Динамическое программирование.

21

Распределение капитальных вложений

Динамическое программирование - это вычислительный метод для решения задач

управления определенной структуры. Данная задача с n переменными

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

определяется экстремум функции только от одной переменной.

Знакомство с методом динамического программирования проще всего начать с

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

одного производственного объединения или отрасли. Для определенности можно

считать, что речь идет о распределении капитальных вложений.

Предположим, что указано n пунктов, где требуется построить или реконструировать

предприятия одной отрасли, для чего выделено b рублей. Обозначим через fi

(xi) прирост мощности или прибыли на j-м предприятии, если оно

получит xi рублей капитальных вложений. Требуется найти такое

распределение (x1,x2, ... , xn) капитальных

вложений между предприятиями, которое максимизирует суммарный прирост мощности

или прибыли

z = f1(x1) + f2(х2) + ... + fn(xn)

при ограничении по общей сумме капитальных вложений

x1 + x2 + ... + xn = b

причем будем считать, что все переменные xj принимают только целые

неотрицательные значения

xj = 0, или 1, или 2, или 3, ...

Функции fj(xj) мы считаем заданными, заметив, что их

определение - довольно трудоемкая экономическая задача.

Воспользуемся методом динамического программирования для решения этой задачи.

Введем параметр состояния и определим функцию состояния. За параметр состояния x

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

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

предприятиях, если они вместе получают x рублей. Параметр x может изменяться от

0 до b. Если из x рублей k-е предприятие получит xk рублей, то

каково бы ни было это значение, остальные x - xk рублей естественно

распределить между предприятиями от первого до (К-1)-го так, чтобы была

получена максимальная прибыль Fk-1(x - xk). Тогда прибыль

k предприятий будет равна fk(xk) + Fk-1(x - x

k). Надо выбрать такое значение xk между 0 и x, чтобы эта сумма

была максимальной, и мы приходим к рекуррентному соотношению

Fk(x)=max{fk(xk) + Fk-1(x-xk)}

0 £ xk £ x

для k = 2, 3, 4, ... , n . Если же k=1, то

F1(x) = f1(x)

Рассмотрим конкретный пример. Пусть производственное объединение состоит

из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс.

рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения

функций fj(xj) приведены в таблице 1, где, например,

число 88 означает, что если третье предприятие получит 600 тыс. руб.

капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс.

руб.

22

Таблица I

Прежде всего заполняем табл. 2. Значения f2(x2) складываем

со значениями F1(x - x2) = f1(x- x2

) и на каждой северо-восточной диагонали находим наибольшее число, которое

отмечаем звездочкой и указываем соответствующее значение

. Заполняем таблицу 3.

Продолжая процесс, табулируем функции F3(x),

(x) и т.д. В табл. 6 заполняем только одну диагональ для значения x= 700.

Наибольшее число на этой диагонали:

Zmax = 155 тыс. руб.,

причем четвертому предприятию должно быть выделено

х*4 = 4 (700) = 300 тыс. руб.

На долю остальных трех предприятий остается 400 тыс. руб. Из табл. 5 видно,

что третьему предприятию должно быть выделено

x*3 = 3 (700-x*4) = 3 (400) = 200 тыс. руб.

Продолжая обратный процесс, находим

x*2 = 2 (700 - x*4 - x*3) = 2 (200) = 100 тыс. руб.

На долю первого предприятия остается

x*1 = 700 - x*4 - x*3 - x*2 = 100 тыс. руб.

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

вложений по предприятиям:

x*1 =100; x*2 =100; x*3 = 200; x*4 = 300.

Оно обеспечивает производственному объединению наибольший воможный прирост

прибыли 155 тыс. руб.

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

f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = z max

Таблица 2

	x - x2	0 100 200 300 400 500 600 700
x2	F1(x - x2) f2(x2)	0 20 34 46 53 55 60 60
0	0	0 20* 34 46 53 55 60 60
100	18	18 38* 52* 64 71 73 78
200	29	29 49 63 75 82 84
300	45	45 65* 79 91 98
400	62	62 82* 96 108
500	78	78 98* 112*
600	90	90 110
700	98	98 .

23

Таблица 3

x	0 100 200 300 400 500 600 700
F2(x)	0 20 38 52 65 82 98 112
`(x)	0 0 100 100 300 400 500 500

Таблица 4

	x - x3	0 100 200 300 400 500 600 700
x3	F2(x - x3) f3(x3)	0 20 38 52 65 82 98 112
0	0	0 20 38 52 65 82 98 112
100	25	25* 45* 63* 77 90 107 123
200	41	41 61 79* 93 106 123
300	52	52 72 94* 112 126
400	74	74 94* 112* 126*
500	82	82 102 120
600	88	88 106
700	90	90 .

Таблица 5

x	0 100 200 300 400 500 600 700
F3(x)	0 25 45 63 79 94 112 126
(x)	0 100 100 100 200 400 400 400

Таблица 6

	x - x4	0 100 200 300 400 500 600 700
x4	F3(x - x4) f4(x4)	0 25 45 63 79 94 112 126
0	0	126
100	30	142
200	52	146
300	76	155*
400	90	153
500	104	149
600	116	141
700	125	125 .

§9. Динамическая задача управления производством

24

и запасами

Предприятие производит партиями некоторые изделия. Предположим, что оно

получило заказы на n месяцев. Размеры заказов значительно меняются от месяца

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

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

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

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

производство и хранение изделий. Обозначим:

xj - число изделий, производимых в j -й месяц;

yj - величина запаса к началу j го месяца (это число не содержит

изделий, произведенных в j -м месяце);

dj - число изделий, которые должны быть отгружены в j -й месяц;

fj (xj,yj+1) - затраты на хранение и производство изделий в j -м месяце.

Будем считать, что величины запасов к началу первого месяца y1 и к

концу последнего yn+1 заданы.

Задача состоит в том, чтобы найти план производства

(x1, x2, ..., xn)

(1)

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

xj + yj - dj = yj+1 j

= 1,n (2)

и минимизируют суммарные затраты за весь планируемый период

(3)

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

xj ³ 0, yj ³ 0, j = 1,n

(4)

Прежде чем приступить к решению поставленной задачи, заметим, что для любого

месяца j величина yj+1 запаса к концу месяца должна удовлетворять

ограничениям

0 £ yj+1 £ dj+1 + dj+2 + ... + d

n (5)

т.е. объем производимой продукции xj на этапе j может быть настолько

велик, что запас yj+1 удовлетворяет спрос на всех последующих

этапах, но не

имеет смысла иметь yj+1 больше суммарного спроса на всех последующих

этапах. Кроме того, из соотношений (2) и (4) непосредственно следует, что

переменная xj должна удовлетворять ограничениям

0 £ xj £ dj + yj+1 (6)

Следует также заметить, что переменные xj, yj могут

принимать только целые неотрицательные значения, т.е. мы получили задачу

целочисленного нелинейного программирования.

Будем решать задачу (1)-(6) методом динамического программирования.

Введем параметр состояния и составим функцию состояния.

25

За параметр состояния x примем наличный запас в конце k -го месяца

x = yk+1

(7)

а функцию состояния Fk(x) определим как минимальные затраты за первые

k месяцев при выполнении условия (5)

(8)

где минимум берется по неотрицательным целым значениям x1,...,x

k, удовлетворяющим условиям

xj + yj - dj = yj+1

j = 1, k-1 (9)

xk + yk - dk = x

(10)

Учитывая, что

(11)

и величина запаса yk к концу (k-1) периода, как видно из уравнения (10), равна

yk = x + dk - xk

(12)

приходим к рекуррентному соотношению

(13)

где минимум берется по единственной переменной xk, которая, согласно

(6) может изменяться в пределах

0 £ xk £ dk + x (14)

принимая целые значения, причем верхняя граница зависит от значений параметра

состояния, изменяющегося в пределах

0 £ x £ dk+1 + dk+2 + ... + dn

(15)

а индекс k может принимать значения

k = 2, 3, 4, ... , n

(16)

Если k=1, то

F1(x = y2) = min f1(x1, x)

(17)

x1

где

x1 = x + d1 - y1

(18)

0£ x £ d2 + d3 + ... + dn

(19)

26

т.е. на начальном этапе при фиксированном уровне y1 исходного запаса

каждому значению параметра x отвечает только одно значение переменной x1

, что несколько уменьшает объем вычислений.

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

последнем шаге (при k = n) находим значение последней компоненты xn*

оптимального решения, а остальные компоненты определяем как

(20)

Рассмотрим более подробно функции затрат fj(xj, yj+1

) и рекуррентные соотношения. Пусть

jj(xj) = axj2 + bxj + c

jj (xj) - затраты на производство (закупку) xj единиц продукции на этапе j;

Страницы: 1, 2, 3, 4