Xreferat.com » Рефераты по математике » Динамическое и линейное программирование

Динамическое и линейное программирование

width="363" height="144" align="LEFT" hspace="13" />

30 11 45 36 28

50 14

36

70

16 11 43

*

30

2
28



Теперь наибольшая положительная оценка всех свободных клеток транспортной таблицы, соответствует клетке 25, отсюда строим цикл пересчета: 25-23-33- и производим перераспределение поставок вдоль этого цикла пресчета:

43

*

15 28
2 28

30 0


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

30 11 45 36 28

50 14

36

70 16 11 15
28

30

30



Находим оценки всех свободных клеток таблицы:


Все , где ;

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

при котором транспортные расходы по обеспечению продуктом всех четырех пуктов потребления будут наименьшими. При этом из второго пункта производства товар будет вывезен не полностью, т.е. там останется остаток продукта 28 единиц.


5. Распределение капитальных вложений

Задача о распределении капитальных вложений – это нелинейная задача распределения ресурсов между предприятиями одного производственного объединения или отрасли.

Предположим, что указано пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделена определенная сумма. При этом известен прирост мощности или прибыли для каждого предприятия, в зависимости от суммы капитальных вложений в это предприятие. Требуется найти такое распределение капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли всей отрасли.

Примем следующие обозначения:

Номер предприятия (j=1,2,…,n)

Общая сумма капитальных вложений

Сумма капитальных вложений в j-ое предприятие

Прирост мощности или прибыли j-го предприятия, если оно получит xj денежных единиц капитальных вложений

Тогда, задача состоит в том, чтобы найти такие значения , , …, , при которых значение суммарного прироста прибыли или мощности всей отрасли:

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

=0 или 1, или 2, или 3, …;

Эту задачу можно решить методом динамического программирования. Для этого необходимо ввести параметр состояния и функцию состояния :

Некоторое количество предприятий, для которых определяется параметр и функция состояния ()

Сумма капитальных вложений, выделяемая нескольким предприятиям ()

Максимальный прирост прибыли или мощности на первых предприятиях, если они вместе получат капитальных вложений

Тогда, если из денежных единиц k-ое предприятие получит денежных единиц, то остаток денежных средств необходимо распределить между предприятиями от первого до так, чтобы был получен максимальный прирост прибыли или мощности . Следовательно, прирост прибыли или мощности k предприятий будет равен и нужно выбрать такое значение между 0 и , чтобы увеличение прибыли или мощности k предприятий было бы максимальным, т.е.:

, где .

Если же k=1, то:

Допустим, что производственное объединение состоит из четырех предприятий (n=4). Общая сумма капитальных вложений равна 700 денежных единиц (b=700), при этом суммы выделяемые предприятиям кратны 100 денежным единицам. Значения функций приведены в таблице 3:


Таблица 3.

0 100 200 300 400 500 600 700

0 42 58 71 80 89 95 100

0 30 49 63 68 69 65 60

0 22 37 49 59 68 76 82

0 50 68 82 92 100 107 112

Для заполнения таблицы 5 необходимо в таблице 4 сложить значения функции со значениями и на каждой северо-восточной диагонали выбрать наибольшее число (отмечено звездочкой), указав соответствующие значение :


Таблица 4.


0 100 200 300 400 500 600 700

0 42 58 71 80 89 95 100

0

0 0

42*

58 71 80 89 95 100

100

30 30

72*

88 101 110 119 125
200 49 49

91*

107*

120 129 138

300 63 63 105

121*

134*

143*




400 68 68 110 126 139



500 69 69 111 127




600 65 65 107





700 60 60







Таблица 5.

0 100 200 300 400 500 600 700

0 42 72 91 107 121 134 143

0 0 100 200 200 300 300 300

Для заполнения таблицы 7 необходимо в таблице 6 сложить значения функции со значениями и на каждой северо-восточной диагонали выбрать наибольшее число (отмечено звездочкой), указав соответствующие значение :


Таблица 6.


0 100 200 300 400 500 600 700

0 42 72 91 107 121 134 143

0

0 0

42*

72*

91 107 121 134 143

100

22 22 64

94*

113*

129*

143 156
200 37 37 79 109 128

144*

158*



300 49 49 91 121 140 156


400 59 59 101 131 150



500 68 68 110 140




600 76 76 118





700 82 82







Таблица 7.

0 100 200 300 400 500 600 700

0 42 72 94 113 129 144 158

0 0 0 100 100 100 200 200

Теперь, в таблице 8, необходимо сложить значения функции со значениями , но только для значения , т.е. заполнить только одну диагональ:


Таблица 8.


0 100 200 300 400 500 600 700

0 42 72 94 113

129

144 158

0

0






158

100

50





194
200 68




197*



300 82



195


400 92


186



500 100

172




600 107
149





700 112 112






Наибольшее число этой диагонали показывает максимально возможный суммарный прирост прибыли всех четырех предприятий данного производственного объединения, при общей сумме капитальных вложений в 700 денежных единиц, т.е.:

денежных единиц

причем четвертому предприятию должно быть выделено:

денежных единиц

Тогда третьему предприятию должно быть выделено (см. табл. 7.):

денежных единиц

второму предприятию должно быть выделено (см. табл. 5.):

денежных единиц

на долю первого предприятия остается:

денежных единиц

Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:

которое обеспечивает производственному объединению наибольший возможный прирост прибыли:

денежных единиц

6. Динамическая задача управления запасами

Задача управления запасами – это задача о поддержании баланса производства и сбыта продукции предприятия, минимизирующего расходы предприятия на производство и хранение продукции.

Предположим, что предприятие, производящее партиями некоторую продукцию, получило заказы на n месяцев. Размеры заказов значительно меняются от месяца к месяцу, поэтому иногда лучше выполнять заказы сразу нескольких месяцев, а затем хранить готовую продукцию, пока она не потребуется, чем выполнять заказ именно в тот месяц, когда этот заказ должен быть

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

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

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

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