Прикладная математика
Переписав неравенства (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 |
Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в 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
Читателю не составит труда проверить, что будет оптимальным базисное допустимое решение
Динамическое программирование - это вычислительный метод для решения задач управления определенной структуры. Данная задача с 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, или