Xreferat.com » Рефераты по математике » Прикладная математика

Прикладная математика

/> Х = (х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 занятых клеток.

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

)

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

ij = Aij - сij i = 1,m; j = 1,n

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

ij = pi + qj - cij i = 1,m; j = 1,n (6)

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

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

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

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


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

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

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

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

32 = 5; 13 = -3; 14 = -1; 24 = -2; 15 = -6; 25 = -4.

Н

20

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

max () = 5 =

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


41 13

41-

13+



20 34


37 23

37-

23+



16 44


21

21-


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-



20

21

30

21+

30-

42 10

max = 20

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


ij 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) мы считаем заданными, заметив, что их определение - довольно трудоемкая экономическая задача.

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

Введем параметр состояния и определим функцию состояния. За параметр состояния примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния Fk() определим как максимальную прибыль на первых k предприятиях, если они вместе получают рублей. Параметр может изменяться от 0 до b. Если из рублей k-е предприятие получит xk рублей, то каково бы ни было это значение, остальные - xk рублей естественно распределить между предприятиями от первого до (К-1)-го так, чтобы была получена максимальная прибыль Fk-1( - xk). Тогда прибыль k предприятий будет равна fk(xk) + Fk-1( - xk). Надо выбрать такое значение xk между 0 и , чтобы эта сумма была максимальной, и мы приходим к рекуррентному соотношению


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

0 xk

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

F1() = f1()


Рассмотрим конкретный пример. Пусть производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций fj(xj) приведены в таблице 1, где, например, число 88 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 88 тыс. руб.

Т

22

аблица I


Прежде всего заполняем табл. 2. Значения f2(x2) складываем со значениями F1( - x2) = f1(- x2) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение . Заполняем таблицу 3.

Продолжая процесс, табулируем функции F3(), () и т.д. В табл. 6 заполняем только одну диагональ для значения = 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


 - x2

0 100 200 300 400 500 600 700

x2

F1( - 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

0 100 200 300 400 500 600 700

F2()

0 20 38 52 65 82 98 112

()

0 0 100 100 300 400 500 500


Таблица 4


 - x3

0 100 200 300 400 500 600 700

x3

F2( - 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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: