Задача распределения ресурсов на расширение производства

Тип работы: Курсовая работа
Бесплатно: Антиплагиат
Объем: 20 страниц
В избранное:

МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ
РЕСПУБЛИКИ КАЗАХСТАН

Казахский национальный технический университет
им. К. И. Сатпаева

Кафедра технической кибернетики

Пояснительная записка
к курсовому проекту
по дисциплине ТОКС

На тему: Задача распределения ресурсов на расширение производства

СОДЕРЖАНИЕ
Задание ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 3
Введение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..4
1. Краткая теоретическая часть ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...5
2. Основная часть ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 8
2.1. Словесная формулировка задачи ... ... ... ... ... ... ... ... ... ... ... ... .8
2.2. Математическая постановка задачи ... ... ... ... ... ... ... ... ... ... ... 9
2.3. Алгоритм ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...10
2.4. Решение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .1 1

Заключение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...16

Список литературы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...17
Приложение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..18
1. Программный продукт ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..19
2. Листинг программы

+

Задание

Задача распределения ресурсов на расширение производства

ВАРИАНТ 5

Пусть в группе из n дочерних предприятий фирмы выделены дополнительные
средства на расширение производства. По каждому дочернему предприятию
известен возможный прирост gi(x) для i=1, ..., n выпуска продукции в
зависимости от выделенной ему суммы x.
Требуется распределить средства C между дочерними предприятиями так,
чтобы общий прирост фирмы (n(C) выпуска продукции был максимальным.
Исходные данные приведены в таблицах 1, 2.
Примечания:
1) Для решения задачи следует использовать метод динамического
программирования. Общий вид функционального уравнения Беллмана можно
взять для данной задачи в следующем виде:
(n(x) = max [gn(x)+ (n-1(C-x)].
0(x(C
2) Для упрощения расчётов значения x принимать кратным 20 тыс. у. е.
1) Просчитать по шагам вручную, сведя в таблицу результаты. В
пояснительную записку включать полностью просчет по шагам. Дать
подробную интерпретацию полученных результатов.
2) Провести моделирование на PC и сравнить с расчётными данными.
X(тыс.у.е) g1(x) G2(X) G3(x) g4(x) g5(x)
0 0 0 0 0 0
20 11 17 14 15 16
40 25 21 23 32 30
60 37 39 46 43 44
80 52 69 61 59 62
100 71 78 77 75 81
120 92 99 87 97 90
140 125 111 121 115 122
160 152 135 155 147 140
180 171 158 167 165 161

Введение

В наше время, наука уделяет все большее внимание вопросам
организации и управления, это обусловлено целым рядом причин.
Быстрое развитие и усложнение техники; увеличение масштабов и
стоимостей проводимых мероприятий; широкое внедрение автоматизации в
сферу управления - все это приводит к необходимости научного анализа
сложных целенаправленных процессов под углом зрения их структуры и
организации. От науки требуются рекомендации по наилучшему
(оптимальному) управлению такими процессами. Эти потребности практики
вызвали к жизни специальные научные методы, которые принято
объединять под названием Исследование операций. Под этим
подразумевается применение математических, количественных методов для
обоснования решений во всех областях целенаправленной человеческой
деятельности.
Наиболее сложно обстоит дело с принятием решений, когда речь
идет о мероприятиях, опыта, в проведении которых еще не существует
и, следовательно, здравому смыслу не на что опереться, а интуиция
может обмануть. При планировании приходится опираться на большое
количество данных, относящихся не столько к прошлому опыту, сколько
к предвидимому будущему. Выбранное решение должно по возможности
гарантировать нас от ошибок, связанных с неточным прогнозированием,
и быть достаточно эффективным для широкого круга условий. Для
обоснования такого решения приводится в действие сложная система
математических расчетов.
Для решения практических задач исследование операций располагает
целым арсеналом математических средств. К ним относятся: теория
вероятностей с ее новейшими разделами (теория случайных процессов,
теоретические основы компьютерных систем, теория массового
обслуживания); математические методы оптимизации, начиная от
простейших способов нахождения экстремумов (максимумов и минимумов)
и кончая современными методами, такие, как линейное
программирование, динамическое программирование и многие другие.
В этой курсовой работе используется метод динамического
программирования.

1. Краткая теоретическая часть

Динамическое программирование (иначе, динамическое планирование)
представляет собой особый математический метод оптимизации
решений, специально приспособленный к многошаговым (или многоэтапным)
операциям.
Многошаговую задачу можно решать по-разному: либо искать сразу все
элементы решения на всех m шагах, либо же строить оптимальное управление
шаг за шагом, на каждом этапе расчета оптимизируя только один шаг. Обычно
второй способ оптимизации оказывается проще, чем первый, особенно
при большом числе шагов.
Такая идея постепенной, пошаговой оптимизации и лежит в основе
динамического программирования. [1]
С первого взгляда эта идея может показаться довольно
тривиальной. В самом деле, чего, казалось бы, проще: если трудно
оптимизировать операцию в целом, то разбить ее на ряд шагов;
каждый такой шаг будет отдельной, маленькой операцией,
оптимизировать которую уже нетрудно. Надо выбрать на каждом шаге
такое управление, при котором эффективность этого шага максимальна.
Принцип динамического программирования отнюдь не предполагает,
что каждый шаг оптимизируется отдельно, независимо от других; что,
выбирая шаговое управление, можно забыть обо всех других шагах.
Напротив, шаговое управление должно выбираться с учетом всех его
последствий в будущем. Планирование должно быть дальновидным, с
учетом перспективы. Что толку, если мы выберем на данном шаге
управление, при котором эффективность этого шага максимальна, если
в дальнейшем это помешает нам получить хорошие результаты других
шагов?
Пусть, например, планируется работа группы промышленных предприятий, из
которых часть занята выпуском предметов потребления, а остальные производят
для них машины. Задача операций – получить за m лет максимальный объем
выпуска предметов потребления.
предметов потребления. Допустим, планируются капиталовложения на первый
год. Исходя из узких интересов данного шага, мы должны были бы
все средства вложить в производство предметов потребления, пустить
имеющиеся машины на полную мощность и добиться к концу года
максимального объема продукции. Имея в виду будущее, необходимо
выделить какую-то долю средств и на производство машин. При этом
объем продукции за первый год, естественно, снизится, зато будут
созданы условия, позволяющие увеличивать ее производство в
последующие годы.[4]
Значит, планируя многошаговую операцию, необходимо выбирать
управление на каждом шаге с учетом его будущих последствий на еще
предстоящих шагах.[2]
Поэтому процесс динамического программирования разворачивается от
конца к началу: раньше всех планируется последний, m-й шаг. А как
его спланировать, если мы не знаем, чем кончился предпоследний?
Очевидно, нужно сделать разные предположения о том, чем кончился
предпоследний (m-1)-й шаг, и для каждого из них найти такое
управление, при котором выигрыш (доход) на последнем шаге был бы
максимален. Решив эту задачу, мы найдем условное оптимальное
управление на m-м шаге, т.е. то управление, которое надо
применить, если (m-1)-й шаг закончился определенным образом.[1]
Таким образом, в процессе оптимизации управления методом динамического
программирования многошаговый процесс проходится дважды: первый раз – от
конца к началу, в результате чего находятся условные оптимальные управления
и условные оптимальные выигрыши.
Второй раз от начало к концу, когда нам остается только прочитать
Уже готовые рекомендации и найти безусловное оптимальное управление,
состоящее из оптимальных шаговых управлений.
Одним словом, на каждом шагу ищется такое управление, которое
обеспечивает оптимальное продолжение процесса относительно
достигнутого в данный момент состояния. Этот принцип выбора
управления называется принципом оптимальности. Само управление,
обеспечивающее оптимальное продолжение процесса относительно заданного
состояния, называется условным оптимальным управлением на данном
шаге.[7]
Теперь предположим, что условное оптимальное управление на
каждом шаге нам известно: мы знаем, что делать дальше, в каком
бы состоянии ни был процесс к началу каждого шага. Тогда мы
можем найти уже не условное, а просто оптимальное управление на
каждом шаге.[3]
Первый вопрос на который нужно ответить ставящему задачу: какими
параметрами характеризуется состояние управляемой системы S перед каждым
шагом? От удачного выбора этих параметров часто зависит возможность успешно
решить задачу оптимизации.
Как быт с числом шагов m? С первого взгляда может показаться, что чем
больше m, тем лучше. Это не совсем так. При увеличении m возрастает объем
расчетов, а это не всегда оправдано. Число шагов нужно выбирать с учетом
двух обстоятельств:
1) шаг должен быть достаточно мелким для того, чтобы процедура
оптимизации шагового управления была достаточно мелким для того,
чтобы процедура оптимизации шагового управления была достаточно
проста.
2) Шаг должен быть не слишком мелким, чтобы не производить ненужных
расчетов, только усложняющих процедуру поиска оптимального решения ,
но не приводящих к существенному изменению оптимума целевой функции.
Сформулируем общий принцип, лежащий на основе решения всех задач
динамического программирования :
1) Выбрать параметры (фазовые координаты), характеризующие состояние S
управляемой системы перед каждым шагом.
2) Расчленить операцию на этапы (шаги).
3) Выяснить набор шаговых управлений для каждого шага и
налагаемые на них ограничения.
4) Определить, какой выигрыш приносит на -м шаге управление
, если перед этим система была в состоянии S, т.е.
записать”функции выигрыша ” :

5) Определить, как изменяется состояние S системы S под влиянием
управления на -м шаге: оно переходит в новое состояние

6) Записать основное рекуррентное уравнение динамического
программирования, выражающее условный оптимальный выигрыш:

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

и находя условное оптимальное управление , для которого этот
максимум достигается.
8) Произвести условную оптимизацию (m-1)-го , (m-2)-го и.т.д.шагов
,полагая в ней ..., и для каждого из шагов указать условное
оптимальное управление , при котором максимум достигается.
9) Произвести безусловную оптимизацию управления, читая
соответствующие рекомендации на каждом шаге. Взять найденное
оптимальное управление на первом шаге .[6]

2. Основная часть

2.1 Словесная формулировка задачи
Имеется группа предприятий Р1, Р2..., Рn . В нашем распоряжении какой-
то запас средств С, который мы должны распределить между предприятиями так,
чтобы получить максимальный доход.
Каждое из предприятий при вложении в него каких-то средств х приносит
доход, gi(x), зависящий от вложенных в него средств.
Сумма всех выделяемых средств не должна превышать величину имеющегося
капитала. Требуется найти оптимальное распределение ресурсов, при котором
суммарная производительность была максимальной.

2.2 Математическая постановка задачи

Пусть заданы:
Из N дочерних gi (x) i= ; C.

Необходимо
Фn(х) = mах [gn(x) + Фn-1(c-x)]
i=
При ограничениях:

n = 5;

0 X C, где 0 С
180[тыс.у.е.],

2.3 Алгоритм

1. Выбрать способ описания процесса, т.е. параметры,
характеризующие состояние системы, фазовое пространство и способ
членения операции на шаги.
2. Записать выигрыш на i -м шаге в зависимости от состояния
системы S в начале этого шага и управления Ui:
Wi = Wi (S,Ui).
3. Записать для i -го шага функцию, выражающую изменение
состояния системы от S к S’ под влиянием управления Ui:
S’ = фi (S,Ui).
4. Записать основные функциональное уравнение,

выражающее функцию Wi (S) через Wi+1 (S):
Wi(S) = max{wi (S,Ui) + Wi+1 (фi (S,Ui))}. (1)

Ui
5. Найти функцию Wm (S) (условный оптимальный выигрыш) для
последнего шага:
Wm(S) = max{wm (S,Um)}.

Um
(максимум берется только по тем управлениям, которые приводят
систему в заданную область конечных состояний Sw) и соответствующее
ей условное оптимальное управление на последнем шаге:
Um (S).
6. Зная Wm (S) и пользуясь уравнением (1) при конкретном виде
функций wi (S,Ui), фi (S,Ui), найти одну за другой функции

Wm-1(S), Wm-2(S),...,W1(S)
и соответствующие им условные оптимальные управления:

Um-1(S), Um-2(S),...,U1(S).
7. Если начальное состояние S0 задано, найти оптимальный выигрыш
Wmax = W1 (S0) и далее безусловные оптимальные управления (и, если
надо, конечное состояние S*m) по цепочке:
S0 - U1(S0) - S*1 - U2(S*1) - ... - S*m-1 - Um(Sm-1) - S*m.
8. Если начальное состояние S0 не задано, а лишь ограничено
условием
S0 С S0,
найти оптимальное начальное состояние S*0, при котором выигрыш,
W1(S) достигает максимума
Wmax = max {W1(S)}
S C S0
и далее, по цепочке, безусловные оптимальные управления.

2.4 Решение

n = 5,
с = 180 [тыс. у. е.]
Исходные данные приведены в таблице 1.
Примечание:
1. Для решения задачи следует использовать метод динамического
программирования. Общий вид функционального уравнения Беллмана можно
взять для данной задачи в следующем виде:
фn(х) = мах [gn(x) + фn-1(c-x)];
0XC
2. Для упрощения расчетов значения Х принимать кратным
20 тыс. [у.е.]

Таблица 1. Исходные данные.
X(тыс.у.е) g1(x) G2(X) G3(x) g4(x) g5(x)
0 0 0 0 0 0
20 11 17 14 15 16
40 25 21 23 32 30
60 37 39 46 43 44
80 52 69 61 59 62
100 71 78 77 75 81
120 92 99 87 97 90
140 125 111 121 115 122
160 152 135 155 147 140
180 171 158 167 165 161

Начинаем оптимизировать с конца.
Для данного предприятия ф1(х) = мах [g1(x) + ф0(c-x)];
0XC
Предполагая, что ф2(с-х) уже оптимизирован.

1-шаг. Для различных вариантов х1 условное оптимальное решение:

X 0 20 40 60 80 100 120 140 160 180 Фmax =W 0 11 25
37 52 71 92 125 152 171
Все варианты условно оптимальны.
Эти значения W будем подставлять в таблицу следующего шага.

2-шаг. Для второго предприятия (при условии, что 1 предприятия уже
оптимальная) учитывая результаты 1-го шага
ф2(х) = мах [g2(x) + ф1(c-x)];
0XC
Имеем различные варианты распределения х по 1 и 2 предприятиям.

x 0 20 20 40 40 40 60 60 60 60 80 80 80 80 X1 0 20 0
40 20 0 60 20 40 0 80 20 40 60 X2 0 0 20 0 20 40 0 40
20 60 0 60 40 20 G1 0 17 0 21 17 0 39 17 21 0 69 17
21 39 G2 0 0 11 0 11 25 0 25 11 37 0 37 25 11
W2=g2+g1 0 17 11 21 28 25 39 42 32 37 69 54 46 50
80 100 100 100 100 100 100 120 120 120 120 120 120 120 0
100 20 40 60 80 0 120 20 40 60 80 100 0 80 0 80 60 40
20 100 0 100 80 60 40 20 120 0 78 17 21 39 69 0 99 17
21 39 69 78 0 52 0 52 37 25 11 71 0 71 52 37 25 11 92
52 78 69 58 64 80 71 99 88 73 76 93 89 92

140 140 140 140 140 140 140 140 160 160 160 160 160 160 140
20 40 60 80 100 120 0 160 20 40 60 80 100 0 120 100 80
60 40 20 140 0 140 120 100 80 60 111 17 21 39 69 78 99
0 135 17 21 39 69 78 0 92 71 52 37 25 11 125 0 125 92
71 52 37 111 109 92 91 106 103 110 125 135 142 113 110
121 115

160 160 ... продолжение

Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.