Реферат: 5 различных задач по программированию
следовательно, структуры производственной программы)
(2)
предполагая, что можно надеяться получить
дополнительно не более 1/3 первоначального объема ресурса каждоговида
(3)
причем по смыслу задачи t2 0, t3 0.
(4)
Переписав неравенства (2) и (3) в виде:
(5)
из условия (3) следует t2£148/3, t3£158/3 (6)
приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).
Эту задачу легко решить графически: см. рис. 2. Программа ²расшивки² имеет вид
t1=0, t2=14, t3=0 и прирост прибыли составит 112.
Сводка результатов приведена в таблицe 2.
сj 36 32 10 13 b x4+i yi ti
2 3 4 1 103 5 0 0
aij 4 2 0 2 148 0 8 14
2 8 7 0 158 0 2 0
xj 31 12 0 0 1500 112
Dj 0 0 4 3
ТРАНСПОРТНАЯЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Однородный продукт, сосредоточенный в 3 пунктах производства (хранения) в
количествах 40;60; 70 единиц, необходимо распределить между 4 пунктами
потребления, которым необходимо соответственно 36; 32; 40; 53 единиц. Стоимость
перевозки единицыпродукта из пункта отправления в пункт назначения известна для
всех маршрутов и равна С = . Необходимо составить план перевозок, при
котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся
продуктов впунктах производства и общие транспортные расходы по доставке
продуктов были минимальными.
Для решения транспортной задачи чаще всего применяется метод потенциалов.
Общий объем производства åаi =40+60+70=170 больше, чемтребуется всем
потребителям åbi = 36+32 +40 +53 =161, т.е. имеем открытую модель транспортной
задачи. Для превращенияее в закрытую вводим фиктивный пункт потребления с
объемом потребления 170-161 = 9 единиц, причем тарифы на перевозку в этот пункт
условимся считать равныминулю, помня, что переменные, добавляемые к левым частям
неравенств для превращения их в уравнения, входят в функцию цели с нулевыми
коэффициентами.
Первое базисное допустимое решение легко построить по правилу ²северо-западного
угла².
Потребление b1 =36 b2 =32 b3 =40 b4 =53 b5 =9
Производство
а1 =40 36 4 p1 =0
a2 =60 28 32 p2 =
a3 =70 * 8 53 9 p3 =
q1 = q2 = q3 = q4 = q5 =
Общая стоимость всех перевозок для первого базисного допустимого решения:
L= 36* 2 + 4 *3 + 28 *2 + 32 + 8* 7+ 53 =281
Один из потенциалов можно выбрать произвольно, так как в системе (3), (4)
одноуравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные
потенциалы находим из условия, что для базисных клеток . В данном случае
получаем
D11 = 0, p1 + q1 - c11= 0, 0+q1 -2 = 0,
q1 = 2
D12 = 0, p1 + q2 - c12= 0, 0+q2 -3 = 0,
q2 = 3
D22 = 0, p2 + q2 - c22 = 0, р2+3-2 = 0, р2 = -1
и т.д., получим: q3=2, p3=5, q4= -4, q5= -5.
Затем по формуле (6) вычисляем оценки всех свободных клеток:
D21 = p2 + q5 - c21 = -1+2-4 = -3
D31 = p3 + q1 - c31 = 5+2-2 = 5
D32 = 1; D13 =-2; D14 = -5; D24 =0; D15 = -5; D25 = -6.
Находим наибольшую положительную оценку max () = 5 =
Для найденной свободной клетки 31 строим цикл пересчета - замкнутую ломаную
линию, соседниезвенья которой взаимно перпендикулярны, сами звенья параллельны
строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке,
а всеостальные - в занятых клетках. Это будет 31-11-12-22-23-33. Производим
перераспределение поставок вдоль цикла пересчета
36 4 36-r 4+r 28 12
28 32 28-r 32+r 20 40
8 r 8-r 8
= 8
Получаем второе базисное допустимое решение:
bj b1 =36 b2 =32 b3 =40 b4 =53 b5=9
ai
а1 =40 28 12 * p1 =0
a2 =60 20 40 p2 = -1
a3 =70 8 53 9 p3 =0
q1 =2 q2 = 3 q3 = 2 q4 = 1 q5=0
Находим новые потенциалы, новые оценки.
D13 = -2; D14 = 0; D15 = 0; D21 = -3; D24 = -2; D25 = -1; D32 = -4; D33 =
-5,
т.е. все Dij £ 0 i = 1,m; j = 1,n
Общая стоимость всех перевозок для второго базисного допустимого решения:
L= 28* 2 + 12 *3 + 20 *2 + 40 + 8* 2+ 53 =241 – минимальная стоимость.
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. РАСПРЕДЕЛЕНИЕКАПИТАЛЬНЫХ ВЛОЖЕНИЙ
Пусть производственное объединениесостоит из четырех предприятий (n=4). Общая
сумма капитальных вложений равна700 тыс. рублей (b=700), выделяемые предприятиям
суммы кратны 100 тыс. рублей.Значения функций fj(xj) приведены в таблице 1, где,
например, число 50означает, что если третье предприятие получит 600 тыс. руб.
капитальныхвложений, то прирост прибыли на этом предприятии составит 50 тыс.
руб.
Таблица I
Прежде всего заполняем табл. 2. Значенияf2(x2) складываем со значениями F1(x -
x2) = f1(x- x2) и на каждойсеверо-восточной диагонали находим наибольшее число,
которое отмечаемзвездочкой и указываем соответствующее значение . Заполняем
таблицу 3.
Продолжая процесс, табулируем функцииF3(x), (x) и т.д. В табл. 6 заполняем
только одну диагональ для значения x=700.
Таблица 2
x - x2 0 100 200 300 400 500 600 700
x2 F1(x- x2)
f2(x2) 0 15 24 30 36 40 43 45
0
0 0 15 24 30 36 40 43 45
100 18 18* 33* 42* 48 54 58 61
200 26 26 41 50* 56 62 66
300 34 34 49 58* 64* 70*
400 39 39 54 63 69
500 42 42 57 66
600 44 44 59
700 46 46
Таблица 3
x 0 100 200 300 400 500 600 700
F2(x) 0 18 33 42 50 58 64
70
` (x)
0 0 100 100 200 300 300 300
Таблица 4
x- x3 0 100 200 300 400 500 600 700
x3 F2(x- x3)
f3(x3) 0 18 33 42 50 58 64 70
0
0 0 18* 33 42 50 58 64 70
100 16 16 34* 49* 58 66 74 80
200 27 27 45 60* 69 77 85
300 37 37 55 70* 79* 87*
400 44 44 62 77 86
500 48 48 66 81
600 50 50 68
700 56 56
Таблица 5
x 0 100 200 300 400 500 600 700
F3(x) 0 18 34 49 60 70 79
87
(x)
0 0 100 100 200 300 300 300
Таблица 6
x - x4 0 100 200 300 400 500 600 700
x4 F3(x- x4)
f4(x4) 0 18 34 49 60 70 79 87
0 0
87
100 10
89*
200 17 87
300 23 83
400 29 78
500 34 68
600 38 56
700 41 41
.
Наибольшее число на этой диагонали: Zmax = 89 тыс. руб.,
причем четвертому предприятию должно бытьвыделено х*4 = 4 (700) = 100 тыс.
руб.
На долю остальных трех предприятийостается 600 тыс. руб. Из табл. 5 видно, что
третьему предприятию должно бытьвыделено x*3 = 3 (700-x*4) = 3 (600) =
300 тыс. руб.
Продолжая обратный процесс, находим x*2= 2 (700 - x*4 - x*3) = 2
(300) = 100 тыс. руб.
На долю первого предприятия остается x*1 = 700 - x*4 - x*3 - x*2 = 200 тыс.
руб.
Таким образом, наилучшим являетсяследующее распределение капитальных вложений по
предприятиям:
x*1 =200; x*2 =100; x*3 = 300; x*4 = 100.
Оно обеспечивает производственномуобъединению наибольший воможный прирост
прибыли 89 тыс. руб.
выполнение равенства: f1(x*1) + f2(x*2) + f3(x*3) + f4(x*4) = zmax
24+18+37+10=89
ДИНАМИЧЕСКАЯ ЗАДАЧА УПРАВЛЕНИЯПРОИЗВОДСТВОМ И ЗАПАСАМИ
Рассмотрим трехэтапную систему управлениязапасами с дискретной продукцией и
динамическим детерминированным спросом.
Пусть спрос (заявки) потребителей на нашупродукцию составляют: на первый этап
d1=3 единицы, на второй – d2=2, на третий - d3=3 единицы. К началу первого
этапа на складе имеется 3 единицыпродукции, т.е. начальный уровень запаса равен
y1=3. Затраты на хранениеединицы продукции на разных этапах различны и
составляют соответственно h1=4, h2=3, h3=2. Затраты на производство xjединиц
продукции на j-м этапе определяются функцией jj(xj) = xj2 + 2xj + 2
т.е. а=1; b=5; с=2. Требуется указать,сколько единиц продукции на отдельных
этапах следует производить, чтобы заявкипотребителей были удовлетворены, а наши
общие затраты на производство ихранение за все три этапа были наименьшими.
Исходные данные задачи можно краткозаписать одной строкой:
d1 d2 d3 a b c
h1 h2 h3 y1
3 2 3 1 2 2
4 3 2 3
Воспользовавшись рекуррентнымисоотношениями, последовательно вычисляем F1 (x =
y2), F2 (x = y3),..., Fk (x = yk+1), ... и соответственно находим 1
(x= y2), 2 (x = y3 ), ..., ` k (x = yk+1), ...
Положим k = 1.
Параметр состояния x = у2 может приниматьцелые значения на отрезке
0 у2 d2 + d3 0 y2 2 + 3 т.е. у2 = 0, 1, 2, 3, 4, 5.
Каждому значению параметра состояниядолжна отвечать определенная область
изменения переменной x1, характеризуемаяусловием 0 х1 d1 + у2 или 0 х1 3
+ у2
Из балансового уравнения х1 + у1 - d1 = у2 непосредственно следует, что объем
производства связан созначением параметра состояния x= у2соотношением
x1= y2 + d1 - y1 = y2 + 3 - 3 = y2
В этом и состоит особенность первого этапа.Если задан уровень запаса к
началупервого этапа, то каждому значению у2 отвечает единственное значение х1
ипотому F1(x = y2) = W1 (x1, y2)
Придавая у2 различные целые значения от 0до 6 и учитывая предыдущее соотношение,
находим
y2 = 0, x1= 0, W1 (0;0) = 02 + 2×0 + 2 +4×0 = 2*
y2 = 1, x1= 1, W1 (1;1) = 12 + 2×2 + 2 +4×1 = 11
y2 = 2, x1= 2, W1 (2;2) = 22 + 2×2 + 2 +4×2 = 18
y2 = 3, x1= 3, W1 (3;3) = 32 + 2×3 + 2 +4×3 = 29
y2 = 4, x1= 4, W1 (4;4) = 42 + 2×4 + 2 +4×4 = 42
y2 = 5, x1= 5, W1 (5;5) = 52 + 2×5 + 2 +4×5 = 57
Значения функции состояния F1(x )представлены в табл. 1
Таблица 1
x = y2 0 1 2 3 4 5
F1 (x = y2)
2 11 18 29 42 57
x1(x=y2) 0 1 2 3 4 5
Переходим ко второму этапу. Полагаем k =2 и табулируем функцию F2(x = y3)
Здесь минимум берется по единственнойпеременной х2, которая может изменяться в
пределах
0 £ x2 £ d2 + y3 или 0 £ x2 £ 2 + y3
(1)
где верхняя граница зависит от параметрасостояния x = у3, который
принимаетзначения на отрезке
0 £ y3 £ d3 , т.е. 0 £ y3 £ 3
а аргумент у2 связан с х2 и у3 балансовымуравнением x2 + y2 - d2 = y3
откуда следует y2 = y3 + d2 - x2 = =y3 +2 - x2 (2)
Придавая параметру состояния различныезначения от 0 до 3, будем последовательно
вычислять W2 (x2, x), а затем определять F2(x ) и 2(x ).
Положим x = у3 = 0. Тогда, согласно(1), 0 £ x2 £ 2, т.е.переменная х2 может
принимать значения: 0, 1, 2, а каждому значению х2 отвечаетопределенное значение
у2, вычисляемое по формуле (2): у2 = 2 - х2
Последовательно находим:
если x2 = 0, то у2 = 2 , W2 (0,2) = 02 + 2×0 + 2+
F1(2) = 2 + 18 = 20,
x2 = 1, y2 = 2 - 1 = 1, W2 (1,2) = 12 + 5×1 + 2 + F1(1) = 8 +
11 = 19,
x2 = 2, y2 = 2 - 2 =0, W2(2,2) = 22 + 5×2 + 2 + F1(0) = 16+ 2 = 18*,
Наименьшее из полученных значений W2 есть F2 (0), т.е.
F2(x = y3 = 0) = 18,
причем минимум достигается при значениих2, равном ` 2 (x = y3 = 0) = 2
Положим x = у3 = 1. Тогда, согласно(1), 0 £ x2 £ 3, т.е.переменная х2 может
принимать значения: 0, 1, 2, 3, а каждому значению х2отвечает определенное
значение у2, вычисляемое по формуле (2): у2 = 3 - х2
Последовательно находим:
если x2 = 0, то y2 = 3-0 = 3, W2 (0,1) = 02 + 2×0 + 2 + 3×1 + F1(3) = 5+
29 = 34,
x2 = 1, y2 = 3-1 = 2, W2 (1,2) = 12 + 2×1 + 2 + 3×1 +F1(2) = 8 + 18 = 26,
x2 = 2, y2 = 3-2 = 1, W2(2,1) = 22 + 2×2 + 2 + 3×1 + F1(1) = 13 +11 =
24,
x2 = 3, y2 = 3-3 = 0, W2 (3,1) = 32 + 2×3 + 2 + 3×1 +F1(0) = 20 + 2 =
22*,
Наименьшее из полученных значений W2 есть F2 (1), т.е.
F2(x = y3 = 1) = min W2 (x2,1) = 22,
причем минимум достигается при значениих2, равном ` 2 (x = y3 = 1) = 3
Положим x = у3 = 2. Тогда, согласно(1), 0 £ x2 £ 4, т.е.переменная х2 может
принимать значения: 0, 1, 2, 3, 4, а каждому значению х2отвечает определенное
значение у2, вычисляемое по формуле (2): у2 = 4 - х2
если x2 = 0, то y2 = 4-0 = 4, W2 (0,2) = 02 + 2×0 + 2 + 3×2 + F1(4) = 8+
42 = 50,
x2 = 1, y2 = 4-1 = 3, W2 (1,2) = 12 + 2×1 + 2 + 3×2 +F1(3) = 11 + 29 =
40,
x2 = 2, y2 = 4-2 =2, W2(2,2) = 22 + 2×2 + 2 + 3×2 + F1(2) = 16 + 18 =
