Прикладная математика
минимизирующий общую стоимость всех перевозок
(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
Получаем второе базисное допустимое решение:
-
bjb1 =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 
2130 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 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 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.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |
Производство
0
0