Задачи динамического программирования. Задача распределения инвестиций

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

хорошую работу на сайт">

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

Размещено на http://www.allbest.ru/

Задача распределения ресурсов методом динамического программирования

Для расширения производственных мощностей трех предприятий А, В и С выделяется некоторое количество единиц дополнительной электроэнергии в объеме х 0 =8 единиц. Электроэнергия может выделяться в виде 1, 2, 3, 4, 5, 6, 7 и 8 единиц. Вкладывая в развитие i-того предприятия х i единиц электроэнергии можно получить доход у i единиц на предприятии. Существуют разные варианты х i (к) выделения дополнительной электроэнергии. Они приносят доход у i (к), к=1,n. Возможные варианты развития предприятий приведены в табл.1. Суммарный доход по всем предприятиям должен быть максимальным, т.е у=? у i (к)>max

Табл. 1. Варианты развития предприятий

Вариант к

Предриятие А

Предприятие В

Предприятие С

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

у=? у i (к)> max

?х i (к)?х 0

Решение:

Начнем рассмотрение процедуры решения поставленной задачи с последнего (3 шага) этапа (Табл.2), на котором инвестиции выделяются предприятию С. Условно-оптимальное управление на третьем этапе ищется как решение уравнения

g C (S 2)=max k f c , x C (k)?S 2 , k=1,2,3,4

Табл. 2. Условно-оптимальные решения(шаг 3)

Состояние

Управление

Имеется четыре возможности вложения средств - четыре шаговых управления х С (1)=0ед., х С (2)=1ед., х С (3)=2ед., х С (4)=3ед. и девять теоретически возможных состояний системы S 2 , предшествующих выделению средств предприятию С, - объемы не распределенных к 3-му этапу инвестиций: 0,1,2,3,4,5,6,7,8.

Предположим, что система находилась в состоянии S 2 =2.Тогда, для шагового управления х С (2)=1 доход у С (2) будет равен 3ед. (Табл.3), а шаговое управление х С (3)=2 будет оптимальным для этого состояния, дающим условно-максимальный выигрыш g c (S 2)=5. Если система находилась в состоянии S 2 =3, то допустимы все шаговые управления х С (1)=0ед., х С (2)=1ед., х С (3)=2ед., х С (4)=3ед., а оптимальным будет управление х С (4)=3, которое обеспечивает условно максимальный выигрыш g c (S 2)=6.

Табл.3 динамический программирование распределение инвестиция

Аналогично заполняются все возможные состояния предшествующие 3-му этапу. Оптимальные значения показателей выделены в таблицах жирным шрифтом.

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

g А (S 1)=max k f А +g c ], x А (k)?S 1 , k=1,2,3,4

Так, для состояния S 1 =3 с шаговым управление х A (2)=1 получаем:

g А (S 1)=max k f А +g c ]

Max k 4+g c =4+5=9, где находим из таблицы 1, а g c из таблицы 3. Аналогично заполняются все состояния.

Табл. 4. Условно-оптимальные решения(шаг 2)

Состояние

f А +g c

Управление

Здесь возникают ситуации, при которых оптимальное решение будет не единственным, Так в состояние S 1 =3 условно оптимальными будут шаговые управления х A (2)=1 и х A (3)=2, дающие один и тот же выигрыш g A (S 1)=9

Табл. 5. Безусловно-оптимальные решения (шаг 1)

На первом этапе (Табл.5)-выделение инвестиций предприятию В - есть только одно предшествующее состояние системы, соответствующее начальному состоянию S 0 =8. Безусловно оптимальный выигрыш определяется выражением:

у * = g В (S 0)= max k {f А +g А } x в (k)?S 0 =x 0 , k=1,2,3,4,5

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

Схема нахождения всех оптимальных вариантов распределения инвестиций между предприятиями (Табл.6) представлена на рисунке 1.

Табл. 6. Оптимальные распределения инвестиций.

Рисунок 1. Схема оптимального распределения инвестиций между предприятиями

Вывод: рассмотрев задачу распределения ресурсов методом динамического программирования выявили два варианта оптимального распределения ресурсов.

Размещено на Allbest.ru

...

Подобные документы

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

    курсовая работа , добавлен 25.04.2015

    Многошаговые процессы в динамических задачах. Принцип оптимальности и рекуррентные соотношения. Метод динамического программирования. Задачи оптимального распределения средств на расширение производства и планирования производственной программы.

    курсовая работа , добавлен 30.12.2010

    Метод динамического программирования и его основные этапы. Оптимальная стратегия замены оборудования. Минимизация затрат на строительство и эксплуатацию предприятий. Оптимальное распределение ресурсов в ООО "СТРОЙКРОВЛЯ" и инвестиций ПКТ "Химволокно".

    курсовая работа , добавлен 08.01.2015

    Математическая модель планирования производства. Составление оптимального плана производственной деятельности предприятия методом линейного программирования. Нахождение оптимального способа распределения денежных ресурсов в течение планируемого периода.

    дипломная работа , добавлен 07.08.2013

    Расчет стоимости перевозок методом минимальных затрат. Нахождение условного оптимального равенства в процессе динамического программирования. Линейное алгебраическое уравнение Колмогорова для среднего времени безотказной работы резервированной системы.

    курсовая работа , добавлен 14.01.2011

    Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.

    контрольная работа , добавлен 15.10.2010

    Оптимальный план распределения денежных средств между предприятиями. Разработка плана для каждого предприятия, при котором прибыль от вложенных денежных средств примет наибольшее значение. Использование методов линейного и динамического программирования.

    курсовая работа , добавлен 16.12.2013

    Характерные черты задач линейного программирования. Общая постановка задачи планирования производства. Построение математической модели распределения ресурсов фирмы. Анализ чувствительности оптимального решения. Составление отчета по устойчивости.

    презентация , добавлен 02.12.2014

    Нахождение оптимального портфеля ценных бумаг. Обзор методов решения поставленной задачи. Построение математической модели. Задача конусного программирования. Зависимость вектора распределения начального капитала от одного из начальных параметров.

    дипломная работа , добавлен 11.02.2017

    Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.

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

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

Эта задача легко решается методом динамического программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие за второй - в и т. д.

Управляемая система S в данном случае - средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S - наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел при которой суммарный доход максимален:

Решим эту задачу сначала в общем, формульном виде, а потом - для конкретных числовых данных. Найдем для каждого шага условный оптимальный выигрыш (от этого шага и до конца), если мы подошли к данному шагу с запасом средств S. Обозначим условный оптимальный выигрыш , а соответствующее ему условное оптимальное управление - средства, вкладываемые в предприятие, -

Начнем оптимизацию с последнего, шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие Поэтому условное оптимальное управление на -м шаге: отдать последнему предприятию все имеющиеся средства S, т. е.

а условный оптимальный выигрыш

Задаваясь целой гаммой значений S (располагая их достаточно тесно), мы для каждого значения S будем знать . Последний шаг оптимизирован.

Перейдем к предпоследнему, шагу. Пусть мы подошли к нему с запасом средств S. Обозначим условный оптимальный выигрыш на двух последних шагах: (который уже оптимизирован). Если мы выделим на шаге предприятию средства то на последний шаг останется Наш выигрыш на двух последних шагах будет равен

и нужно найти такое , при котором этот выигрыш максимален:

Знак означает, что берется максимальное значение по всем какие только возможны (вложить больше, чем S, мы не можем), от выражения, стоящего в фигурных скобках. Этот максимум и есть условный оптимальный выигрыш за два последних шага, а то значение при котором этот максимум достигается, - условное оптимальное управление на шаге.

и соответствующее ему условное оптимальное управление - то значение при котором этот максимум достигается.

Продолжая таким образом, дойдем, наконец, до предприятия Здесь нам не нужно будет варьировать значения S; мы точно знаем, что запас средств перед первым шагом равен К:

Итак, максимальный выигрыш (доход) от всех предприятий найден. Теперь остается только «прочесть рекомендации». То значение при котором достигается максимум (13.4), и есть оптимальное управление на 1-м шаге.

После того как мы вложим эти средства в 1-е предприятие, у нас их останется . «Читая» рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств: и т. д. до конца.

А теперь решим численный пример. Исходный запас средств (условных единиц), и требуется его оптимальным образом распределить между пятью предприятиями Для простоты предположим, что вкладываются только целые количества средств. Функции дохода заданы в таблице 13.1.

Таблица 13.1

В каждом столбце, начиная с какой-то суммы вложений, доходы перестают возрастать (реально это соответствует тому, что каждое предприятие способно «освоить» лишь ограниченное количество средств).

Произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств?, мы пробуем выделить на этот шаг то или другое количество средств, берем выигрыш на данном шаге по таблице 13.1, складываем с уже оптимизированным выигрышем на всех последующих шагах до конца (учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили) и находим то вложение, на котором эта сумма достигает максимума. Это вложение и есть условное оптимальное управление на данном шаге, а сам максимум - условный оптимальный выигрыш.

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

Таблица 13.2

В первом столбце каждой пары приводится значение условного оптимального управления, во втором - условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом - последнем - шаге вынужденное: выделяются все средства; на всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W за всю операцию - в данном случае он равен 5,6. В последних двух столбцах таблицы 13.2 заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно: . Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму - пять единиц, третьему - две, четвертому - ни одной, пятому - одну единицу. При этом распределении доход будет максимален и равен 5,6.

- 1.03 Мб

Дадим математическую формулировку принципа оптимальности. Для простоты будем считать, что начальное x 0 и конечное x T состояния системы заданы. Обозначим через z 1 (х 0 , u 1) значение функции цели на первом этапе при начальном состоянии системы x 0 и при управлении u 1 , через z 2 (х 1 ,u 2) – соответствующее значение функции цели только на втором этапе, ..., через
z i (х i -1 ,u i) – на i-м этапе, ..., через z N (х N -1 , u N) -на N-м этапе. Очевидно, что

Надо найти оптимальное управление u*= (; ;...;), такое, что доставляет экстремум целевой функции (1) при ограничениях.

Для решения этой задачи погружаем ее в семейство подобных. Введем обозначения. Пусть – соответственно области

определения для подобных задач на последнем этапе, двух последних и т. д.;
– область определения исходной задачи. Обозначим через F 1 (x N -1), F 2 (x N -2), …, F k (x N -k), …, F N (x 0) соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т. д., на k последних и т. д., на всех N этапах.

Начинаем с последнего этапа. Пусть х N-1 – возможные состояния системы на начало N-го этапа. Находим:

F 1 (x N -1) = z N (x N -1 , u N). (2)

Для двух последних этапов получаем

F 2 (x N -2) = (Z N -1 (x N -2 , u N -1) + F 1 (x N -1)). (3)

Аналогично:

F 3 (x N -3) = (Z N -2 (x N -3 , u N -2) + F 2 (x N -2)). (4)

………………………………………………….

F k (x N -k) = (z N-k +1 (x N -k , u N-k +1) + F k- 1 (x N-k +1)). (5)

…………………………………………………..

F N (x 0) = (z 1 (x 0 , u 1) + F N -1 (x 1)). (6)

Выражение (6) представляет собой математическую запись принципа оптимальности. Выражение (5) – общая форма записи условно-оптимального значения функции цели для k оставшихся этапов. Выражения (2) – (6) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.

    1. Особенности задач динамического программирования

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

  • Рассматривается система, состояние которой на каждом шаге определяется вектором x t . Дальнейшее изменение ее состояния зависит только от данного состояния x t и не зависит от того, каким путем система пришла в это состояние. Такие процессы называются процессами без последействия.
  • На каждом шаге выбирается одно решение u t , под действием которого система переходит из предыдущего состояния x t -1 в новое х t . Это новое состояние является функцией состояния на начало интервала x t -1 и принятого в начале интервала решения u t , т. е. x t = x t (x t -1 ,u t).
  • Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
  • На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений.
  • Требуется найти такое допустимое управление u t для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.

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

Геометрическая интерпретация задачи динамического программирования состоит в следующем. Пусть n – размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой, начальное и конечное состояния системы – точками х 0 , (рис. 1). Управление – это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X 0 или X T , которой эти точки принадлежат.

Рисунок 1

Тогда допустимые управления переводят точки из области Х 0 в X T . Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х 0 и оканчивающуюся в области Х T , для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.

  1. ЗАДАЧА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

2.1 Общая постановка задачи

Рассмотрим применение метода динамического программирования на примере распределения средств между шестью объектами реконструкции предприятия горводоканала:

1. Центральная насосно- фильтровальная станция;

2. Восточная насосно- фильтровальная станция;

3. Водопроводная насосная станции перекачки;

4. Центральная станция аэрации;

5. Восточная станция аэрации;

6. Загородная станция аэрации.

Общая сумма средств, предоставленная на развитие составляет не более 195 тысяч гривен. На основе технико-экономических расчетов установлено, что в результате реконструкции в зависимости от количества потраченных средств объекты будут иметь производительность, приведенную в таблице 1.1. Необходимо определить оптимальное распределение средств между объектами реконструкции, которая обеспечит максимальное увеличение производительности этих объектов. Таким образом, в этой задаче используется критерий оптимизации - суммарная производительность предприятий объектов реконструкции.

Таблица 1.1 Входные данные продуктивности объектов реконструкции

Порядковый номер объекта

Объем ресурсов, выданных на развитие объектов (тыс. грн.)

Продуктивность объектов результате развития (тыс. м3)
    1. Блок схема программы

Рисунок 1. Основная программа

QtObj – количество объектов


QtRes – количество ресурсов

effMatrix - матрица производительности объектов,


distVector – вектор выделенных ресурсов


Шаг 1. Условная оптимизация

Шаг 2. Безусловная оптимизация


I = QtObj-1,0 формируем вектор результат

Рисунок 2. Ввод данных

distVector – вектор дистанций, effMatrix = матрица производительности

если все элементы матрицы введены



если вектор производительности- не

отрицательный

Рисунок 3. Условная оптимизация,

формируем мартицу выхода (максимум функции цели)


outMatrix – матрица максимума цели

QtObj – количество объектов

QtRes – количество ресурсов

Matrix – матрица производительности

distVect – вектор дистанций (вектор ресурсов)

нет да Если первое предприятие

Поиск максимума


да maxItem = temp; outMatrix[i][j] = maxItem

    1. Структура алгоритма программы
  1. Ввод данных – класс DataDlg.

Переменные члены класса.

//вектор для хранения объема ресурсов

std::vector distVector;

//матрица производительности объектов

int** effMatrix;

//функция перевода строки в число

int StringToInt(CString);

//функция проверки корректности введенных данных

BOOL FillMatrix();

//функция очистки ресурсов, после закрытия окна

virtual BOOL DestroyWindow();

//функция инициализации диалога

virtual BOOL OnInitDialog();

  1. Вычисление результатов – основ ной класс программы courseWorkDlg

Переменные члены класса

int Value; //значение производительности

int MaxIndex;// максимальный индекс в векторе ресурсов

int Facility;//предприятие

int Recource;//выделенный ресурс

Item ** outMatrix; //матрица максимума цели

std::vector resVector; //вектор результатов

void BuildOutMatrix(int **,std::vector);//функция формирования матрицы цели (условная оптимизация)

afx_msg void OnBnClickedButton1();// обработчик нажатия на кнопку «Вычислить», который запускает процесс вычислений.

virtual BOOL DestroyWindow();//очистка ресурсов программы

  1. Вывод результатов класс Report

Назначение данного класса – это вывод вектора результата в табличной форме.

2.4 Результаты работы программы

Начальный ввод данных

  1. Ввод данных о продуктивности объектов реконструкции
  1. Если не все поля заполнены
  1. Если введен неправильный символ

Корректный ввод данных

Показ результата

  1. Ввод данных

Результат работы программы

Начальный ввод данных

Ввод продуктивности объектов

Приложение.

Листинг программы

int DataDlg::StringToInt(CString str)

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

// все поля заполнены?

BOOL DataDlg::FillMatrix()

bool flag = true;

for (int i = 0; i < Cells.GetSize(); i ++){

for (int j = 0 ; j < Cells.GetAt(i)->Edits.GetSize(); j ++){

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;

if (temp->m_hWnd != NULL){

temp->GetWindowText(str);

if (str.IsEmpty()){

MessageBox(L"Нужно заполнить все поля", L"Ошибка", MB_ICONERROR | MB_OK);

Описание работы

Целью данной работы является реализация на ЭВМ решения задачи оптимального распределения средств на расширение производства.
Задачи курсовой работы:
Рассмотреть теоретические аспекты решения задач динамического программирования; рекуррентность природы задач данного типа; принципы оптимальности Беллмана.
Разработка алгоритма. Блок - схемы. Структура алгоритма.
Реализация на ЭВМ разработанного алгоритма на выбранном языке программирования.

Содержание

ВВЕДЕНИЕ ……………………………………………2
Динамическое программирование
Основные понятия …………………4
Принципы динамического программирования. Функциональные уравнения Беллмана …………………….5
Особенности задач динамического программирования……………….10
Задача распределения ресурсов……………………12
Общая постановка задачи ………………………….13
Блок схема программы
Структура алгоритма программы
Результат работы программы
Заключение
Список используемой литературы

Лабораторная работа

Информатика, кибернетика и программирование

Средства X выделенные kому предприятию приносит в конце года прибыль. Функции заданы таблично: X f1X f2X f3X f4X 1 8 6 3 4 2 10 9 4 6 3 11 11 7 8 4 12 13 11 13 5 18 15 18 16 Определить какое количество средств нужно выделить каждому предприятию чтобы суммарная прибыль равная сумме прибылей полученных от каждого предприятия была наибольшей. Пусть количество средств выделенных kому предприятию. Уравнения на м шаге удовлетворяют условию: либо kому предприятию ничего не выделяем: либо не больше того что...

Лабораторная работа 4_2. Решение задачи о распределении ресурсов методом динамического программирования.

Цель работы – изучить возможности табличного процессора MS Excel для решения задачи распределения ограниченных ресурсов методом динамического программирования.

Краткие теоретические сведения

Построение модели динамического программирования (ДП) и применение метода ДП для решения задачи сводится к следующему:

  1. выбирают способ деления процесса управления на шаги;
  2. определяют параметры состояния и переменные управления X k на каждом шаге;
  3. записывают уравнения состояний;
  4. вводят целевые функции k -ого шага и суммарную целевую функцию;
  5. вводят в рассмотрение условные максимумы (минимумы) и условное оптимальное управление на k -ом шаге: .
  6. Записывают основные для вычислительной схемы ДП уравнения Беллмана для и по правилу:
  1. Решают последовательно уравнения Беллмана (условная оптимизация) и получают две последовательности функций и.
  2. После выполнения условной оптимизации получают оптимальное решение для конкретного состояния:

а) и

б) по цепочке оптимальное управление (решение) .

Постановка задачи динамического программирования в общем виде.

Условие задачи . Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства: у.е. Размеры вложения в каждое предприятие кратны 1 условной единице. Средства X , выделенные k

f 1 (X)

f 2 (X)

f 3 (X)

f 4 (X)

Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль (равная сумме прибылей, полученных от каждого предприятия), была наибольшей.

Решение. Пусть - количество средств, выделенных k -ому предприятию. Суммарная прибыль равна. Переменные X удовлетворяют ограничениям: . Требуется найти переменные, удовлетворяющие данным ограничениям и обращающие в максимум функцию Z .

Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств можно рассматривать как 4-шаговый, номер шага совпадает с номером предприятия; выбор переменных – уравнения на 1, 2, 3, 4 шагах соответственно; - конечное состояние процесса распределения – равно нулю, т.к. все средства должны быть вложены в производство, =0 .

Уравнения состояний и схему распределения можно представить в виде:

Здесь - параметр состояния – количество средств, оставшихся после k -ого шага, т.е. средства, которые остается распределить между оставшимися (4- k ) предприятиями.

Введем в рассмотрение функцию - условно оптимальную прибыль, полученную от -го, ( k +1 )-го, …, 4-го предприятий, если между ними распределялись оптимальным образом средства). Уравнения на -м шаге удовлетворяют условию: (либо k -ому предприятию ничего не выделяем: , либо не больше того, что имеем к k -ому шагу:).

Уравнения Беллмана имеют вид:

Решение уравнений осуществляется путем последовательной оптимизации каждого шага.

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

3 шаг . Делаем предположения относительно остатка средств к 3-ему шагу: может принимать значения 0,1,2,3,4,5 (=0, если все средства отданы 1-ому и 2-ому предприятиям и т.д.). В зависимости от этого выбираем и сравниваем для разных при фиксированных значениях значения суммы. Для каждого максимальное из этих значений есть - условная оптимальная прибыль, полученная при оптимальном распределении средств между 3-м и 4-м предприятиями. Полученные значения для приведены в таблице в графах 5 и 6 соответственно.

S k-1

k =3

k =2

k =1

f 3 (X 3 )+

f 2 (X 2 )+

f 1 (X 1 )+

0+4=4

3+0=3

0+4=4

6+0=6

0+6=6

8+0=8

0+6=6

3+4=7

4+0=4

0+7=7

6+4=10

9+0=9

0+10=10

8+6=14

10+0=10

0+8=8

3+6=9

4+4=8

7+0=7

0+9=9

6+7=13

9+4=13

11+0=11

0+13=13

8+10=18

10+6=16

11+0=11

0+13=13

3+8=11

4+6=10

7+4=11

11+0=11

0+13=13

6+9=15

9+7=16

11+4=15

13+0=13

0+16=16

8+13=21

10+10=20

11+6=17

12+0=12

0+16=16

3+13=16

4+8=12

7+6=13

11+4=15

18+0=18

0+18=18

6+13=19

9+9=18

11+7=18

13+4=17

15+0=15

0+19=19

8+16=24

10+13=23

11+10=21

12+6=18

18+0=18

2 шаг k =2. Для всех возможных значений значения и находятся в столбцах 8 и 9 соответственно; первые слагаемые в столбце 7 – значения взяты из условия, вторые слагаемые взяты из столбца 5 при.

1 шаг . Условная оптимизация проведена в таблице при k =1 для.

Если, то=5; прибыль, полученная от четырех предприятий при условии, что =5 средств между оставшимися тремя предприятиями будут распределены оптимально, равна.

Если, то=4; суммарная прибыль при условии, что =4 средств между оставшимися тремя предприятиями будут распределены оптимально, равна.

Аналогично, при, и;

При, и;

При, и;

Сравнивая полученные значения, получим при.

Вычисляя, получим, а по таблице в столбце 9 находим. Далее находим, а в столбце 6 . Наконец, и. Оптимальное решение.

Ответ. Максимум суммарной прибыли равен 24 у.е. при условии, что 1-ому предприятию выделена 1 у.е.; 2-ому предприятию выделено 2 у.е.; 3-ому предприятию - 1 у.е.; 4-ому предприятию - 1 у.е.

Реализация задачи в MS Excel

  1. Ввод исходных данных в таблицу показан на Рис.1.

Рис.1. Ввод исходных данных в ячейки рабочего листа MS Excel

2. Порядок заполнения ячеек таблицы:

1). В ячейку E 15 введем формулу ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($C15;$B$3:$B$8);G$12+1) и скопируем формулу в диапазоне ячеек с E 15 до E 35.

2). В ячейку F 15 введем формулу

ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($D15;$B$3:$B$8);5) и скопируем формулу в диапазон ячеек с F 15 до F 35.

3). В ячейку G 15 введем формулу E 15+ F 15 и скопируем формулу в диапазон: G 15 - G 35.

4). Находим максимальное значение для каждого состояния от 0 до 5, для этого в ячейку H 15 введем формулу МАКС(G15); после ввода формулы в ячейку H 16 необходимо изменить диапазон с G 16 на G 16: G 17 и т.д. по всему столбику до ячейки H 30 (Рис.2а).

3. Находим значение управления, которому соответствует максимальное значение функции, для этого в ячейку I 15 введем формулу ИНДЕКС($ C 15: G 15;ПОИСКПОЗ(H 15; G 15;0);1), скопируем формулу в ячейку I 16 и увеличим диапазон, в результате в ячейке I 16 получим: ИНДЕКС($ C 16: G 17;ПОИСКПОЗ(H 16; G 16: G 17;0);1). Далее скопируем формулу в ячейки I 18, I 21, I 25, I 30 , постепенно увеличивая диапазон (Рис.2б)

Рис.2а. Вид рабочего листа с формулами, k =3.

Рис.2б (правая часть рабочего листа с формулами, k =3

В результате получим:

Рис. 3 . Результат выполнения первого шага ( k =3).

4. Выделяем диапазон E 15: I 35, выполняем команду Копировать J 15 и выполняем команду Вставить .

5. Изменим формулу функции. В ячейки K 15, K 16, K 18, K 21, K 25, K 30 введем соответственно максимальные значения предыдущего шага, находящиеся в ячейках H 15, H 16, H 18, H 21, H 25, H 30. В остальные ячейки поместим значения, стоящие в этом же столбце и соответствующие предыдущим S k . :

В ячейку K 17 копируем значения ячейки К15;

в ячейки К19 и К20 – значения К16 и К17;

в К22:К24 – значения К18:К20;

в К26:К29 – значения К21:К24;

в К31:К35 – значения К25:К29;

В результате получим:

Рис.4. Результат выполнения второго шага ( k =2).

6. Выделяем диапазон ячеек J 15: N 35, выполняем команду Копировать , устанавливаем курсор в ячейку O 15, выполняем команду Вставить . В результате получаем заполненную таблицу с решением для k =1 (Рис.5)

7. Объясним полученные результаты: при. Вычисляя, получим, а по таблице в столбце 12 находим. Далее определяем, а из столбца 6 . Наконец, и. Таким образом, оптимальное значение, а значение функции 24 у.е., что согласуется с данными, полученными вручную.

Рис.6. Результат выполнения третьего шага ( k =1).

Контрольные упражнения. Варианты.

1. Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства у.е. Размеры вложения в каждое предприятие кратны 1 у.е. Средства X , выделенные k -ому предприятию (), приносит в конце года прибыль. Функции заданы таблично:

f 1 (X)

f 2 (X)

f 3 (X)

f 4 (X)

Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.

2. Планируется деятельность трех промышленных предприятий на очередной год. Начальные средства: у.е. Размеры вложения в каждое предприятие кратны 1 у.е. Средства X , выделенные k -ому предприятию (), приносит в конце года прибыль. Функции заданы таблично:

f 1 (X)

f 2 (X)

f 3 (X)

Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль, была наибольшей.


А также другие работы, которые могут Вас заинтересовать
58796. Geographical Outlook 977.5 KB
By the end of the lesson you should be able to recognize and understand new words and word combinations in the text, to read and understand the gist and details despite the natural difficulties.
58797. Інформація та інформаційні процеси. Обчислювальна система 128 KB
Загальна характеристика теми. Правила техніки безпеки в кабінеті ПЕОМ. Інформатика. Поняття інформації. Інформація і шум. Інформаційні процеси. Інформація й повідомлення.
58798. Операційні системи 126 KB
Робочий стіл. Основні об’єкти Windows. Виділення об’єкта. Операції, властивості та основні команди для роботи з об’єктами. Контекстне меню об’єкта. Ярлики та їх призначення.
58799. Основи роботи з дисками 144.5 KB
Загальна характеристика теми. Форматування диска. Діагностика та дефрагментація дисків. Відновлення інформації на диску. Правила записування та зчитування інформації з дискет.
58800. Текстовий редактор 190 KB
Системи опрацювання текстiв i їх основнi функцiї. Завантаження текстового редактора. Iнтерфейс редактора. Інформаційний рядок. Режими екрана, використання вікон.
58801. Графічний редактор 708 KB
Загальна характеристика теми. Машинна графiка. Графiчний екран. Система опрацювання графiчної інформації. Вказiвки малювання графiчних примiтивiв при роботi з редактором. Типи графічних файлів.
58802. Електронні таблиці 280.5 KB
Навчальна. Охарактеризувати нову тему, висвітлити її роль в курсі інформатики. Ввести поняття електронна таблиця. Ознайомити учнів з програмами опрацювання ЕТ, правилами введення та редагування інформації в ЕТ, способами форматування ЕТ.
58803. Системи управління базами даних (СУБД) 156.5 KB
Бази даних. Фактографічні й документальні БД. Iєрархiчна, мережева, реляцiйна модель бази даних. Основнi елементи та об’єкти бази даних: поле, запис, файл. СУБД.