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

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

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

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

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

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

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

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

t1=Прикладная математика, t2=0, t3=Прикладная математика

и прирост прибыли составит 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

D j

0

8

7

0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

х11 > 0 ,. . . ., xmn > 0. (5)

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

А(а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 Прикладная математика)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

max (Прикладная математика) = 5 = Прикладная математика

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

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

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

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

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

Находим новые потенциалы, новые оценки. Наибольшую положительную оценку будет иметь свободная клетка 14. Для нее строим цикл пересчета 14-11-31-34 производим перераспределение

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

r max = 20

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

D ij £ 0 i = 1,m; j = 1,n

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

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

§ 8. Динамическое программирование. Распределение капитальных вложений

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

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

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

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

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