5 различных задач по программированию
Первое базисное допустимое решение легко построить по правилу ²северо-западного угла².
|
|
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) = z max 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.
Производство
bj
а1 =40