Линейное и динамическое программирование (84341)

Посмотреть архив целиком

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



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

Примем следующие обозначения:

i - номер группы ресурса (i=1,2, ..., m);

j - номер вида продукции (j=1,2, ..., n);

aij - количество единиц i-го ресурса, расходуемое на производство одной единицы j-го вида продукции;

bij - запасы i-ro ресурса ;

xi планируемое количество единиц j-й продукции;

cj -прибыли от реализации одной единицы j-го вида продукции;

X=(x1, x2,…, xn) - искомый план производства, называется допустимым если имеющихся ресурсов достаточно. называется допустимым если имеющихся ресурсов достаточно.

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

Предположим, что предприятие может выпускать четыре вид продукции, используя для этого три вида ресурсов. Известна технологически матрица А затрат любого ресурса на единицу каждой продукции, вектор В объемов ресурсов и вектор С удельной прибыли


48 30 29 10 удельные прибыли


нормы расхода 3 2 4 3 198

2 3 1 2 96

6 5 1 0 228

запасы ресурсов

Обозначим х1, х2, х3, х4 - число единиц 1-й, 2-й, 3-й, 4-й продукции, которые планируем произвести. При этом можно использовать только имеющиеся запасы ресурсов. Целью является получение максимальной прибыли. Получаем следующую математическую модель оптимального планирования:

L(x1,x2,x3,x4)=48xl+30x2+29x3+10x4 max

1+2х2+4х3+3х4≤198

1+3х2+1х3+2х4≤96

1+5х2+1х3+0х4≤228

xj≥0, jєN4

Для решения полученной задачи в каждое неравенство добавим неотрицательную переменную. После этого неравенства превратятся в равенства, в силу этого добавляемые переменные называются базисными. Получается задача ЛП на максимум, все переменные неотрицательны, все ограничения есть равенства и есть базисный набор переменных: х5 - в 1-м равенстве, х6 - во 2-м и х7 - в 3-м. Теперь можно запускать симплекс-метод.

L(x1,x2,x3,x4)=48xl+30x2+29x3+10x4 max

1+2х2+4х3+3х4+x5 =198

1+3х23+2х4 +x6 =96

1+5х23 +x7=228

xj≥0, jєN7


Таблица N 1

C

B

H

48

30

29

10

0

0

0

x1

x2

x3

x4

x5

x6

x7

0

x5

198

3

2

4

3

1

0

0

0

x6

96

2

3

1

2

0

1

0

0

x7

228

6

5

1

0

0

0

1



0

-48

-30

-29

-10

0

0

0

Если все оценочные коэффициенты (серый цвет) неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0. Если же есть отрицательный оценочный коэффициент, то находят самый малый из них. Если в столбце коэффициентов над ним нет положительных, то задача не имеет решения. Задача оптимального планирования не может быть таковой, поэтому ищут минимальное отношение свободных членов столбца Н к положительным коэффициентам указанного xj. В пересечении строки и столбца получаем разрешающий элемент и затем строим новую таблицу.

Таблица N 2

C

B

H

48

30

29

10

0

0

0

x1

x2

x3

x4

x5

x6

x7

0

х5

84

0

31/2

3

1

0

-3/6

0

x6

20

0

11/3

2/3

2

0

1

-2/6

48

х1

38

1

5/6

1/6

0

0

0

1/6



1824

0

10

-21

-10

0

0

-8


Таблица N 3

C

B

H

48

30

29

10

0

0

0

x1

x2

x3

x4

x5

x6

x7

29

х3

24

0

-1/7

1

6/7

2/7

0

-1/7

0

x6

4

0

13/7

0

13/7

-4/21

1

-5/21

48

х1

34

1

6/7

0

-1/7

-1/21

0

4/21



2328

0

7

0

8

6

0

5


Оптимальное решение (производственная программа): Xоpt=(34; 0; 22; 0); максимум целевой функции равен 2328.

Значение переменной с номером i большим 4-х есть остаток (i-4)-ro ресурса. 'Гак как все оценочные коэффициенты неотрицательны, то получено оптимальное решение: базисные переменные равны свободным членам, остальные равны 0.


Следует обратить внимание на экономический смысл элементов послед­ней строки последней симплексной таблицы. Например, коэффициент Δ2=7 при переменной х2 показывает, что если произвести одну единицу продукции второго вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.

Заметим, что в рассматриваемом примере ли­нейной производственной задачи возможна самопроверка результата.

Воспользуемся тем, что в оптимальной производственной программе х2=0, х4=0. Предположим, что вторую и четвертую продукции мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя перемен­ными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:


L(x1,x3)=48xl+29x3 max

1+4х3≤198

1+ х3 ≤ 96

1+ х3≤228

x1≥0, x3≥0

Задачу линейного программирования с двумя переменными можно решить графически. Возьмем на плоскости систему координат: ось OX3 направим горизонтально и вправо, ось OХ1 -вертикально и вверх. Каждое ограничение задачи, раз оно линейное нестрогое неравенство, графически изображается полуплоскостью, граничная прямая которой соответствует уже не неравенству, а равенству. Допустимое множество задачи является пересечением всех этих полуплоскостей и есть выпуклый многоугольник. Вторая из двух основных теорем линейного программирования гласит: Если экстремум целевой функции достигается на допустимом множестве, то функция принимает его в какой-то вершине многоугольника-допустимого множества. Исходя из этой теоремы, найти искомый экстремум можно просто перебрав вершины многоугольника и определив ту, в которой значение функции экстремально. Чаще делают по-другому: строят линию уровня целевой функции и двигают ее параллельно в направлении экстремума, стараясь уловить последнюю точку пересечения линии с допустимым множеством.





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



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

1)меняется тип экстремума целевой функции (mах на min и наоборот);

2)коэффициенты целевой функции одной задачи становятся свободными членами другой задачи;

3)свободные члены одной задачи становятся коэффициентами целевой функции двойственной задачи;

4)тип неравенств меняется (≤ на ≥ и наоборот);

5) каждый столбец одной задачи порождает строку ограничений другой задачи и наоборот. В матрично-векторном виде обе задачи выглядят так:

исходная задача двойственная задача

L=(c,x)max Z=(b,y)min

Ax≤b, x≥0 Ya≥c, y≥0,


L(x1,x2,x3,x4)=48xl+30x2+29x3+10x4 max Z(y1,y2,y3,y4)=198yl+96y2+228y3 min

1+2х2+4х3+3х4≤198 3y1+2y2+6y3≥48

1+3х2+1х3+2х4≤96 2y1+3y2+5y3≥30

1+5х2+1х3+0х4≤228 4y1+ y2 + y3≥29

xj≥0, jєN4 3y1+2y2≥10

yj≥0, jєN3


Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений X(x1, x2, x3, x4) и Y(y1, y2, y3) пары двойственных задач необходимо и достаточно выполнение условий:


x1(3y1+2y2+6y3-48)=0 y1 (3х1+2х2+4х3+3х4)-198=0

x2(2y1+3y2+5y3-30)=0 y2 (2х1+3х2+1х3+2х4)-96=0

x3(4y1+1y2+1y3-29)=0 y3 (6х1+5х2+1х3+0х4)-228=0

x4(3y1+2y2+0y3-10)=0

В решении исходной задачи х1>0, х3>0, поэтому

3y1+2y2+6y3-48=0

4y1+1y2+1y3-29=0

Учитывая, что второй ресурс был избыточным и, согласно теореме двойственности его оценка равна нулю – y2=0, то приходим к системе:

3y1+6y3-48=0

4y1+1y3-29=0

из которой следует, что y1=6; y3=5.

Таким образом получили двойственные оценки ресурсов: y1=6; y2=0; y3=5; общая оценка всех ресурсов Z=198y1+228y3=2328.

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

Таблица N 3

C

B

H

48

30

29

10

0

0

0

x1

x2

x3

x4

x5

x6

x7

29

х3

24

0

-1/7

1

6/7

2/7

0

-1/7

0

x6

4

0

13/7

0

13/7

-4/21

1

-5/21

48

х1

34

1

6/7

0

-1/7

-1/21

0

4/21



2328

0

7

0

8

6

0

5


Решение одной из пары двойственных задач можно найти, зная только ответ к другой задаче и пользуясь 2-й теоремой двойственности: если i-e ограничение одной из пары двойственных задач на компонентах оптимального решения есть строгое неравенство, то оптимальное значение i-й переменной другой задачи равно 0, или, что то же самое - если оптимальное значение j-й переменной одной задачи строго положительно, то j-e ограничение другой из пары двойственных задач на компонентах оптимального решения есть равенство.

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




Расшивка "узких мест" производства



Таблица N 3

C

B

H

48

30

29

10

0

0

0

x1

x2

x3

x4

x5

x6

x7

29

х3

24

0

-1/7

1

6/7

2/7

0

-1/7

0

x6

4

0

13/7

0

13/7

-4/21

1

-5/21

48

х1

34

1

6/7

0

-1/7

-1/21

0

4/21



2328

0

7

0

8

6

0

5


При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, тем самым они образуют "узкие места" производства. Будем их заказывать дополнительно. Пусть Т=( t1,t2,t3) - вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие H+Q-lТ≥0, где Н - значения базисных переменных в последней симплексной таблице, а Q-1 - обращенный базис, который образуют столбцы при балансовых переменных в этой таблице. Задача состоит в том, чтобы найти вектор Т, максимизирующий суммарный прирост прибыли W=6t1+5 t3 при условии сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции), предполагая, что можно получить дополнительно не более 1/3 первоначального объема ресурсов каждого вида.

24 2/7 0 -1/7 t1 0

4 + -4/21 1 -5/21 0 ≥ 0

34 -1/21 0 4/21 t3 0


t1 198

0 ≤ 1/3 96

t3 228

t1≥0, t3≥0.


W=6t1+5t3 max

-2/7 t1 + 1/7 t3 ≤ 24

4/21 t1 + 5/21 t3 ≤ 4

1/21 t1 - 4/21 t3 ≤ 34

t1198/3, t3228/3.

t1≥0, t3≥0.


Как видно, после графического решения (График 2) программа расшивки приобретает вид:

t1=21, t2=0, t3=0

С новым количеством ресурсов: 198+21 219

b' = 96+0 = 96

228+0 228

у предприятия будет новая производственная программа.

Найдем h'=Q-1 b'


5/28 0 -1/7 219 30 x3

-4/7 1 -1/7 96 = 0 x6

-3/28 0 2/7 228 33 x1

Теперь новая производственная программа имеет вид: X'оpt=(33;0;30;0). При этом второй ресурс был использован полностью.

219

При наличии ресурсов b' = 96 производство наиболее выгодно, так как

228

достигается max прибыль с использованием всех ресурсов. Также обратим внимание на то, что производство продукции 1–го вида при заказе дополнительных ресурсов необходимо будет уменьшить на 15 единиц, а производство продукции 3–го вида – увеличить на единицу.

ΔLmax=(Y,t)=6·21=126, где Y=(6;0;5); t(21;0;0)

L'max= ΔLmax+ Lmax=126+2328=2454.

Этот результат можно проверить, подставив значения х1 и х3 в первоначальную целевую функцию: L'max=48xl+30x2+29x3+10x4=31·37+41·21=1147+861=2454.

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



Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в т пунктах производства (хранения) в количествах a1, а2,..., аm единиц, необходимо распределить между п пунктами потребления, которым необходимо соответственно b1, b2,,…, bn единиц. Стоимость перевозки единицы продукта из i-ro пункта отправления в j-й пункт назначения равна cij и известна для всех маршрутов. Необходимо составить план перевозок, при кото­ром запросы всех пунктов потребления были бы удовлетворены за счет имею­щихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

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


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

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

X=(xij), xij0, iNm, jNn

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


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

, iNm


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

, jNn


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

А(а123)=(40;45;70); В(b1,b2,b3)=(48;30;29;40); 3 6 4 3

С= 2 3 1 3

6 5 1 4

Общий объем производства ai=40+45+70=155 больше, чем требуется всем потребителям bj=48+30+29+40=147, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 155-147=8 единиц, причем тари­фы на перевозку в этот пункт условимся считать равными нулю, помня, что пе­ременные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

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

Таблица 1

Потребл

Произв

b1=48

b2=30

b3=29

b4=40

b5=8


a1=40

40 3

6

4

* 3

0

p1=0

a2=45

8 2

30 3

7 1

3

0

p2=-1

a3=70

6

5

22 1

40 4

8 0

p3=-1


q1=3

q2=4

q3=2

q4=5

q5=1



Обозначим через (p1, p2,…, pm, q1, q2,…, qn) вектор симплексных множителей или потенциалов. Тогда ij=Aij-cij , iNm, jNn, откуда следует

ij=pi+qj-cij , iNm, jNn

Положим, что p1=0. Ос­тальные потенциалы находим из условия, что для базисных клеток ij=0. В данном случае получаем

11=0, p1+q1-c11=0, 0+q1-3=0, q1=3

21=0, p2+q1-c21=0, p2+3-2=0, p2= -1

23=0, p2+q3-c23=0, -1+q3-1=0, q3=2

аналогично, получим: q2=4, р3=-1, q4=5, q5=1.

Затем вычисляем оценки всех свободных клеток:

12=p1+q2-c12=0+4-6= -2

13=p1+q3-c13=0+2-4=-2

14=2; 15=1; 24=1; 25=0; 31= -4; 32= -2

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

mах(ij >0)=2=14,

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


40



*


40-




33



7

8

30

7


8+


7-


15

30





22

40




22+

40-




29

33


max=7

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

Таблица 2

Потребл

Произв

b1=48

b2=30

b3=29

b4=40

b5=8


a1=40

33 3

6

4

7 3

0

p1=0

a2=45

15 2

30 3

1

3

0

p2=-1

a3=70

6

* 5

29 1

33 4

8 0

p3=1


q1=3

q2=4

q3=0

q4=3

q5= -1




Находим новые потенциалы. Новые оценки:

12= -2; 13= -4; 15= -1; 23= -2; 24= -1; 25= -2; 31= -2; 32=0. Поскольку все ij0 решение является оптимальным:

33 0 0 7

Xоpt1 = 15 30 0 0

0 0 29 33

Однако, так как оценка клетки 32=0, делаем вывод о наличие другого возможного оптимального решения. Для его нахождения строим цикл пересчета клетки 32: 32-22-21-11-14-34, производим перераспределение:


Таблица 3

Потребл

Произв

b1=48

b2=30

b3=29

b4=40

b5=8


a1=40

3 3

6

4

37 3

0

p1=0

a2=45

45 2

3

1

3

0

p2=-1

a3=70

6

30 5

29 1

3 4

8 0

p3=1


q1=3

q2=4

q3=0

q4=3

q5= -1



Находим новые потенциалы. Получаем рi и qj соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого max=32, однако элемент с индексом 32 уже присутствует в базисе, поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее базисное оптимальное решение:

3 0 0 37

Xоpt2 = 45 0 0 0

0 30 29 3




Оптимальное распределение инвестиций



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

Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-й фирме инвестиций в размере ξ (сотен тыс. рублей) выражается функцией fi(xi). Приходим к задаче fl(xl)+f2(x2)+f3(x3)+f4(x4)max , где xi - пока еще неизвестный размер х1234≤7; х1234≥0 инвестиций i-й фирме. Эта задача решается методом динамического программирования: последовательно ищется оптимальное распределение для k=2,3 и 4 фирм.

Пусть первым двум фирмам выделено ξ инвестиций. обозначим z2(ξ) величину инвестиций 2-й фирме, при которой сумма f2(z2j)+fl(ξ-z2j), 0≤j≤ ξ максимальна, саму эту максимальную величину обозначим F2(ξ). Далее действуем также: находим функции z3 и F3 и т.д. На k-ом шаге для нахождения Fk(ξ) используем основное рекуррентное соотношение: Fk(ξ)=max{fkjk)+F(k-1)( ξ-хk); 0 ≤ хk ≤ ξ



xj

0

100

200

300

400

500

600

700

f1

0

28

45

65

78

90

102

113

f2

0

25

41

55

65

75

80

85

f3

0

15

25

40

56

62

73

82

f4

0

20

33

42

48

53

56

58


Таблица 1



x2

ξ-х2


0

100

200

300

400

500

600

700

F1(ξ-x2)

f2(x2)

0

28

45

65

78

90

102

113

0

0

0

28

45

65

78

90

102

113

100

25

25

53

70

90

103

115

127


200

41

41

69

86

106

119

131



300

55

55

83

100

120

133




400

65

65

93

110

130





500

75

75

103

120






600

80

80

108







700

85

85









Жирным цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций по 2-м предприятиям.


ξ

0

100

200

300

400

500

600

700

F2

0

28

53

70

90

106

120

133

x2

0

0

100

100

100

200

300

300


Таблица 2



х3

ξ-х2


0

100

200

300

400

500

600

700

F3(ξ-x3)

f3(x3)

0

28

53

70

90

106

120

133

0

0

0

28

53

70

90

106

120

133

100

15

15

43

68

85

105

121

135


200

25

25

53

78

95

115

131



300

40

40

68

93

110

130




400

56

56

84

109

125





500

62

62

90

115






600

73

73

101







700

82

82









Случайные файлы

Файл
122666.rtf
58376.rtf
178553.rtf
138723.rtf
122514.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.