Реферат: Модель распределения ресурсов

СодержаниеВведение1.Основные понятия1.1.Модель динамического программирования1.2.Принцип оптимальности. Уравнение Беллмана2.Оптимальное распределение ресурсов2.1Постановка задачи2.2Двумерная модель распределения ресурсов2.3Дискретная динамическая модель оптимального распределения ресурсов2.4 Учетпоследействия в задачах оптимального распределения ресурсовЗаключениеСписокиспользуемых источниковПриложение1. Листинг программы для решения задачи оптимального распределения ресурсов сзаданными параметрами. Результаты работы программы
/>/>Введение

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

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

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

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

В основе метода динамического программированиялежит принцип оптимальности, сформулированный Беллманом. Этот принцип и идеявключения конкретной задачи оптимизации в семейство аналогичных многошаговыхзадач приводят к рекуррентным соотношениям — функциональным уравнениям — относительнооптимального значения целевой функции. Их решение позволяет последовательнополучить оптимальное управление для исходной задачи оптимизации.


/>/>1. Основные понятия/>/> 1.1 Модель динамического программирования

Дадим общее описание моделидинамического программирования.

Рассматривается управляемая система,которая под влиянием управления переходит из начального состояния /> в конечное состояние />. Предположим, что процессуправления системой можно разбить на п шагов. Пусть />, />,…, />— состояния системы послепервого, второго,..., п-го шага. Схематически это показано на рис. 1.

/>

Рисунок 1

Состояние /> системыпосле k-го шага (k=1,2 …,n) характеризуется параметрами />,/>,…, /> которые называются фазовымикоординатами. Состояние /> можноизобразить точкой s-мерного пространства называемого фазовым пространством.Последовательное преобразование системы (по шагам) достигается с помощьюнекоторых мероприятий />, />,…, />, которые составляютуправление системой />, где /> — управлениена k-м шаге, переводящее систему из состояния /> в состояние /> (рис. 1). Управление /> на k-ом шагезаключается в выборе значений определенных управляющих переменных*/>.

Предполагаем впредь, что состояниесистемы в конце k-го шага зависит только от предшествующего состояниясистемы /> и управления /> на данном шаге (рис. 1). Такоесвойство получило название отсутствия последействия. Обозначим этузависимость в виде

/>,                          (1.1)

Равенства (1.1) получили название уравненийсостояний. Функции />  полагаем заданными.

Варьируя управление U, получим различную «эффективность» процесса**, которую будем оценивать количественноцелевой функцией Z, зависящей от начального состояниясистемы /> и от выбранного управленияU:

/>.                               (1.2)

Показатель эффективности k-гошага процесса управления, который зависит от состояния /> в начале этого шага иуправления />, выбранного на этом шаге,обозначим через /> рассматриваемойзадаче пошаговой оптимизации целевая функция (1.2) должна быть аддитивной, т.е.

/>.                       (1.3)

Если свойство аддитивности целевойфункции Z не выполняется, то этого иногда можно добиться некоторымипреобразованиями функции. Например, если Z— мультипликативная функция, заданнаяв виде />, то можно рассмотретьфункцию />, которая являетсяаддитивной.

Обычно условиями процесса науправление на каждом шаге /> накладываютсянекоторые ограничения. Управления, удовлетворяющие этим ограничениям называютсядопустимыми.

Задачу пошаговой оптимизации можносформулировать так: определить совокупность допустимых управлении />, />,…, />, переводящих систему изначального состояния /> в конечноесостояние /> и максимизирующих илиминимизирующих показатель эффективности (1.3).

Для единообразия формулировок (но невычислительных процедур!) в дальнейшем мы будем говорить только о задачемаксимизации, имея в виду, что если необходимо минимизировать Z, то, заменив Z на Z' = —Zперейдем к максимизации Z'.

Начальное состояние /> и конечное состояние /> могут быть заданыоднозначно или могут быть указаны множество /> начальныхсостояний множество /> конечныхсостояний так, что />, />. В последнем случае взадаче пошаговой оптимизации требуется определить совокупность допустимыхуправлений, переводящих систему из начального состояния /> в конечное состояние /> и максимизирующих целевуюфункцию (1.3). Управление, при котором достигается максимум целевой функции(1.3), называется оптимальным управлением и обозначается через />.

Если переменные управления /> принимают дискретныезначения, то модель ДП называется дискретной. Если же указанныепеременные изменяются непрерывно, то модель ДП называется непрерывной. Взависимости от числа параметров состояний (s) и числа управляющих переменных на каждом шаге (r) различают одномерные и многомерныемодели ДП. Число шагов в задаче может быть либо конечным, либо бесконечным.

Динамическое программированиеприменяется при оптимизации как детерминированных, так и стохастическихпроцессов.

В некоторых задачах, решаемых методомДП, процесс управления естественно разбивается на шаги. Например, прираспределении на несколько лет ресурсов деятельности предприятия шагоместественно считать временной период; при распределении средств между n предприятиями номером шагаестественно считать номер очередного предприятия. В других задачах разбиение нашаги вводится искусственно. Например, непрерывный управляемый процесс можнорассматривать как дискретный, условно разбив его на некоторые временные отрезки— шаги. Исходя из условий каждой конкретной задачи, длину шага выбирают таким образом,чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемуюточность вычислений.

/>/> 1.2 Принцип оптимальности. Уравнение Беллмана

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

Иллюстрацией к сказанному выше можетслужить задача о выборе кратчайшего пути для перехода из точки A в точку B, если маршрут должен пройти через некоторые пункты. На рис. 2 эти пунктыобозначены кружками, а соединяющие их дороги — отрезками, рядом с которымипроставлены соответствующие расстояния.


/>

Рисунок 2

С точки зрения интересов оптимизациитолько каждого ближайшего шага — выбора кратчайшего пути из данной точки всоседнюю — следует двигаться по маршруту, проходящему через точки />. Длина этого маршрутаравна 34. Такой путь из A в B не является кратчайшим. Например,маршрут, проходящий через точки />, имеетменьшую длину, равную 25. Решив эту задачу, можно убедиться, что второй путьтакже не является оптимальным.

Приведенный пример многошаговойоперации показывает, что управление на каждом шаге надо выбирать с учетом егопоследствий на предстоящих шагах. Это основное правило ДП, сформулированное Р.Беллманом, называетсяпринципом оптимальности.

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

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

Так, если система в начале k-гошага находится в состоянии />, и мывыбираем произвольное управление />, тосистема придет в новое состояние />, идальнейшие управления /> должнывыбираться оптимальными относительно состояния />.Последнее означает, что при этих управлениях максимизируется показательэффективности на последующих до конца процесса шагах k+1,...,n, т. е. величина />.Показатель, характеризующий суммарную эффективность от данного k-го допоследнего п-го шага, будем обозначать через />,т.е. />. Задача оптимизациипроцесса, начиная с k-годо последнего n-го шага(рис. 3), похожа на исходную при начальном состоянии системы />, управлении /> и показателе эффективности/> [аналогично (1.2)]. Выбравоптимальное управление /> на оставшихся п—k+l шагах, получим величину />, которая зависит только от />, т. е.

/>.                           (1.4)

Назовем величину /> условным максимумом.Если теперь мы выберем на k-м шаге некоторое произвольное управление />, то система придет всостояние />. Согласно принципуоптимальности, какое бы /> мы нивыбрали, на последующих шагах управление /> должновыбираться так, чтобы показатель эффективности /> достигалмаксимального значения, равного />.Остается выбрать управление />. Егонельзя выбирать из условия локальной максимизации показателя эффективности наданном k-м шаге, лишь бы получить />.Такой подход был бы недальновидным, поскольку от выбора /> зависит новое состояние />, а от последнего—максимальновозможная эффективность, которая может быть достигнута в дальнейшем, т. е.величина />. Поэтому необходимовыбирать управление /> так, чтобы оно всовокупности с оптимальным управлением на последующих шагах (начиная с (k+1)-го) приводило бы к общему максимуму показателяэффективности на п—k+l шагах, начиная с k-го до конца. Этоположение в аналитической форме можно записать в виде следующего соотношения:

/>,                         (1.5)

получившего название основногофункционального уравнения ДП, или уравнения Беллмана. Схематическисоотношение (1.5) иллюстрируется на рис. 3.

/>

Рисунок 3

Из уравнения (1.5) может бытьполучена функция />, если известнафункция />; аналогично можно получить/>, если найдена /> и т. д., пока не будетопределена величина />, представляющаяпо определению максимальное значение показателя эффективности процесса в целом:/>.

Соотношения (1.5) для определенияпоследовательности функций /> через /> />получили название основныхрекуррентных уравнений Беллмана.

Решая уравнение (1.5) для определенияусловного максимума показателя эффективности за n—k+l шагов, начиная с k-го, мы определяем соответствующееоптимальное управление />, при которомэтот максимум достигается. Это управление также зависит от />. Будем обозначать такоеуправление через />и называть условнымоптимальным управлением на k-м шаге.

Основное значение уравнения (1.5), вкотором реализована идея динамического программирования, заключается в том, чторешение исходной задачи определения — максимума функции (1.2) n переменных />, />,…, /> сводится к решениюпоследовательности nзадач, задаваемых соотношениями (1.5), каждое из которых является задачей максимизациифункции одной переменной />. Этизадачи оказываются взаимосвязанными, так как в соотношении (1.5) приопределении /> учитывается найденная прирешении предыдущей задачи функция />.


/>/>2. Оптимальное распределение ресурсов

/>/> 2.1 Постановка задачи

Класс задач, рассматриваемый в даннойглаве, имеет многочисленные практические приложения.

В общем виде эти задачи могут бытьописаны следующим образом. Имеется некоторое количество ресурсов, под которымиможно понимать денежные средства, материальные ресурсы (например, сырье, полуфабрикаты,трудовые ресурсы, различные виды оборудования и т. п.). Эти ресурсы необходимораспределить между различными объектами их использования по отдельнымпромежуткам планового периода или по различным промежутками по различнымобъектам так, чтобы получить максимальную суммарную эффективность от выбранногоспособа распределения. Показателем эффективности может служить, например,прибыль, товарная продукция, фондоотдача (задачи максимизации) или суммарныезатраты, себестоимость, время выполнения данного объема работ и т. п. (задачи минимизации).

Вообще говоря, подавляющее числозадач математического программирования вписывается в общую постановку задачиоптимального распределения ресурсов. Естественно, что при рассмотрении моделейи вычислительных схем решения подобных задач методом ДП необходимоконкретизировать общую форму задачи распределения ресурсов.

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

Задача 1. Имеется начальное количество средств/>/>,которое необходимо распределить в течение n лет между s предприятиями. Средства />, выделенные в k-м году i-му предприятию,приносят доход в размере /> и кконцу года возвращаются в количестве/>. Впоследующем распределении доход может либо участвовать (частично илиполностью), либо не участвовать.

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

Следовательно, в качестве показателяэффективности процесса распределения ресурсов за n лет принимается суммарныйдоход, полученный от s предприятий:

/>.                       (2.1)

Количество ресурсов в начале k-гогода будем характеризовать величиной /> (параметрсостояния). Управление на k-мшаге состоит в выборе переменных />,обозначающих ресурсы, выделяемые в k-м году i-мупредприятию.

Если предположить, что доход вдальнейшем распределении не участвует, то уравнение состояния процесса имеетвид

/>           (2.2)

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

Требуется определить ns неотрицательных переменных />, удовлетворяющих условиям(2.2) и максимизирующих функцию (2.1).

Вычислительная процедура ДПначинается с введения функции />,обозначающей доход, полученный за п—k+1 лет, начиная с k-го года до концарассматриваемого периода, при оптимальном распределении средств между sпредприятиями, если в k-мгоду распределялось /> средств. Функции/> для /> удовлетворяютфункциональным уравнениям (1.5), которые запишутся в виде

/>                        (2.3)

При /> согласно(1.5) получаем

/>.      (2.4)

Далее необходимо последовательнорешить уравнения (2.4) и (2.3) для всех возможных />. Каждое из этих уравнений представляет собой задачу наоптимизацию функции, зависящей от s переменных.Таким образом, задача с ns переменными сведена к последовательности n задач, каждая из которых содержит sпеременных. В этой общей постановке задача по-прежнему сложна (из-замногомерности) и упростить ее, рассматривая как ns-шаговую задачу, в данномслучае нельзя. В самом деле, попробуем это сделать. Пронумеруем шаги по номерампредприятий сначала в 1-м году, затем во 2-м и т. д.:

/>

/>

и будем пользоваться одним параметром/> для характеристики остаткасредств.

В течение k-го года состояние />к началу любого шага /> (i=l, 2,… s) определится по предыдущему состоянию/> с помощью простогоуравнения />. Однако по истечении года,т. е. к началу следующего года, к наличным средствам необходимо будет добавить /> средств и, следовательно,состояние /> в начале />-го шага будет зависеть нетолько от предшествующего ks-го состояния, но и от всех sсостояний и управлений за прошлый год. В результате мы получим процесс споследействием. Чтобы исключить последействие, приходится вводить несколько параметровсостоянии; задача на каждом шаге остается по-прежнему сложной из-за многомерности.

/>/> 2.2 Двумерная модель распределения ресурсов

 

Задача 2. Планируется деятельность двухпредприятий (s=2) в течениеn лет. Начальные средства составляют />. Средства x, вложенные в предприятие I, приносятк концу года доход /> и возвращаются вразмере />; аналогично, средства x, вложенные в предприятие II, дают доход /> и возвращаются в размере />. По истечении годавсе оставшиеся средства заново перераспределяются между предприятиями I и II, новыхсредств не поступает и доход в производство не вкладывается.

Требуется найти оптимальный способраспределения имеющихся средств.

Будем рассматривать процессраспределения средств как n-шаговый,в котором номер шага соответствует номеру года. Управляемая система — двапредприятия с вложенными в них средствами. Система характеризуется однимпараметром состояния /> — количествомсредств, которые следует перераспределить в начале k-го года. Переменных управления на каждом шаге две: />и /> — количество средств, выделенныхсоответственно предприятию I и II. Так как средства ежегодно перераспределяются полностью, то />. Для каждого шага задачастановится одномерной. Обозначим /> через />, тогда />.

Показатель эффективности k-го шага равен />. Это—доход, полученный от двухпредприятий в течение k-го года.

Показатель эффективности задачи—доход,полученный от двух предприятий в течение n лет—составляет

/>.         (2.5)

Уравнение состояния выражает остатоксредств /> после k-го шага и имеет вид

/>.              (2.6)

Пусть /> —условный оптимальный доход, полученный от распределения средств /> между двумя предприятиямиза п—k+1 лет,начиная с k-го года до конца рассматриваемого периода. Запишем рекуррентныесоотношения для этих функций:

/>;                      (2.7)

/>,

где /> -определяется из уравнения состояния (2.6).

 

Задача 3. Решить задачу 2 при следующихусловиях: />; />; />; />; />; />.

Если /> и/> - средства, выделенныесоответственно предприятиям I  и II в k-м году, то суммарный доход, полученный от обоихпредприятий, равен

/>,

а уравнение состояния (2.6) принимаетвид

/>.

Основные функциональные уравнения(2.7) запишутся следующим образом:

/>;

/>.

Проведем этап условной оптимизации.

4-й шаг. Условный оптимальный доходравен

/>,

так как линейная относительно /> функция достигаетмаксимума в конце интервала, т.е. при />.

3-й шаг:

/>.

Коэффициент при /> отрицателен, поэтомумаксимум в этой линейной относительно /> функциидостигается в начале интервала, т.е.

/>; />.

2-й шаг:

/>, откуда />; />.

1-й шаг:

/> при />.

Результат условной оптимизации:

/>; />;/>; />;

/>; />;/>; />

Перейдем к безусловной оптимизации.Полагаем />; тогда />, />. Зная />, находим />; используя />, получаем /> и />. Аналогично />, />. Наконец, />. Следовательно, средствапо годам нужно распределить так:

Год Предприятие 1 2 3 4 I 5120 II 10000 8000 6400

При таком распределении средств(10000 руб.) за четыре года будет получен доход, равный />.

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

/>/>2.3Дискретная динамическая модель оптимального распределения ресурсов

При дискретном вложении ресурсовможет возникнуть вопрос о выборе шага /> в изменении переменных управления. Этотшаг может быть задан или определяется исходя из требуемой точности вычислений иточности исходных данных. В общем случае эта задача сложна, требует интерполированияпо таблицам /> на предыдущих шагах вычисления.Иногда предварительный анализ уравнения состояния позволяет выбрать подходящийшаг />, а также установитьпредельные значения />, для которых накаждом шаге нужно выполнить табулирование.

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

Задача 3. Составить оптимальный планежегодного распределения средств между двумя предприятиями в течениетрёхлетнего планового периода при следующих условиях: 1) начальная суммасоставляет 400; 2) вложенные средства в размере x приносят на предприятии I доход /> и возвращаются в размере60% от x, а на предприятии II—соответственно /> и 20%; 3) ежегоднораспределяются все наличные средства, получаемые из возвращенных средств: 4)функции /> и /> заданы в табл. 1:

Таблица 1

              x    

/>

50 100 150 200 250 300 350 400

/>

6 10 15 26 28 38 45 49

/>

8 12 20 28 35 40 46 48

Модель динамического программированияданной задачи аналогична модели, составленной в задаче 1.

Процесс управления являетсятрехшаговым. Параметр /> — средства,подлежащие распределению в k-м году (k=1, 2, 3). Переменная управления /> — средства, вложенные впредприятие I в k-м году.Средства, вложенные в предприятие II в k-м году, составляют />.Следовательно, процесс управления на k-м шаге зависит от одного параметра/> (модель одномерная).Уравнение состояния запишется в виде

/>,                        (2.8)

а функциональные уравнения – в виде

/>,    (2.9)

/>.               (2.10)

Попытаемся определить максимальновозможные значения, для которых необходимо проводить табулирование на k-м шаге (k=1, 2, 3). При /> изуравнения (2.8) определяем максимально возможное значение />; имеем /> =0,6-400= 2400 (всесредства вкладываются в предприятие I). Аналогично, для /> получаем предельноезначение />. Пусть интервал изменения /> совпадает с табличным, т.е. />=50. Составим таблицусуммарной прибыли на данном шаге: />(см. табл. 2). Это облегчитдальнейшие расчеты. Так как />, то клетки, расположенные по диагонали таблицы,отвечают одному и тому же значению/>, указанномув 1-й строке (в 1-м столбце) табл. 2. Во 2-й строке таблицы записаны значения />, а во 2-м столбце — значения/>, взятые из табл. 1.Значения в остальных клетках таблицы получены сложением чисел /> и />. стоящих во 2-й строке и во 2-м столбце и соответствующихстолбцу и строке, на пересечении которых находится данная клетка. Например, для/>=150 получаем ряд чисел:20—для x=0,у=150; 18—для x=50, y==100; 18— для x=100, y=50; 15—для x=150,y=0.

Таблица 2

       x

y

50 100 150 200 250 300 350 400 6 10 15 26 28 38 45 49 50 8 14 18 23 34 36 46 53 100 12 18 22 27 38 40 50 150 20 26 30 35 46 48 200 28 34 38 43 54 250 35 41 45 50 300 40 46 50 350 46 52 400 48

Аналогичную таблицу полезноподготовить и для расчетов по формуле (2.8). Расчет /> приведенв табл.3.

Таблица 3

       x

y

50 100 150 200 250 300 350 400 30 60 90 120 150 180 210 240 50 10 40 70 100 130 160 190 220 100 20 50 80 110 140 170 200 150 30 60 90 120 150 180 200 40 70 100 130 160 250 50 80 110 140 300 60 90 120 350 70 100 400 80

Проведем условную оптимизацию пообычной схеме.

3-й шаг. Основное уравнение (2.9)

/>

решим с помощью табл. 2. Какуказывалось выше, />. Просмотримчисла на диагоналях, соответствующих />; 50;100; 150 и на каждой диагонали выберем наибольшее. Это и есть />. В 1-й строке находимсоответствующее условное оптимальное управление. Данные оптимизации на 3-м шагепоместим в основную таблицу (табл. 4). В ней введен столбец />, который в дальнейшем используется при интерполяции.

Оптимизация 2-го шага проведена втабл. 5 согласно уравнению вида (2.10):

/>.

Таблица 4 (основная)

/>

3-й шаг 2-й шаг

/>

/>

/>

/>

/>

/>

8 10,8 50 8 50 10,8 50 6 9,6 100 14 50 20,4 50 6 8,0 150 20 28,4 100 14 200 42,4 200 9,2 250 51,6 200

Таблица 5

/>

50 100 150

/>

50 50 100 50 100 150

/>

50 100 50 150 100 50

/>

10 30 20 40 60 30 50 70 90

/>

8 6 12 14 10 20 18 18 15

/>

1,6 4,8 3,2 6,4 9,2 4,8 8 10,4 12,8

/>

9,6

10,8

15,2 20,4 19,2 24,8 26

28,4

27,8

Продолжение

/>

200 250

/>

50 100 150 200 50 100 150 200 250

/>

200 150 100 50 250 200 150 100 50

/>

40 60 80 100 120 50 70 90 110 130 150

/>

28 26 22 23 26 35 34 30 27 31 28

/>

6,4 9,2 11,6 14 16,4 8 10,4 12,8 16,2 17,6 20

/>

34,4 35,2 33,6 37

42,4

43 44,4 42.8 42,2

51,6

48

Результаты оптимизации занесены втабл. 4. Для значений/>, некратных 50,приведена линейная интерполяция функции /> втабл. 4.

Условная оптимизация 1-го шага согласноуравнению

/>

для />=400приведена во вспомогательной табл. 6. Для значений, некратных 50, соответствующиезначения функции /> полученыинтерполяцией в основной табл. 4.

Таблица 6

/>

50 100 150 200 250 300 350 400

/>

400 350 300 250 200 150 100 50

/>

80 100 120 140 160 180 200 220 240

/>

48 52 50 50 54 48 50 53 49

/>

16,6 20,4 23,6 27,8 31,2 36,8 42,4 46,1 49,8

/>

64,6 72,4 73,6 77,8 85,2 84,8 92,4

99,1

98,8

Перейдем к безусловной оптимизации.Из табл. 6 получаем Zmax=99,l, />=350,/>=50. По /> и /> в табл. 3 находим />=220; для этого значения изтабл. 4 получаем />=200.Следовательно, />=20. Этомууправлению в табл. 3 соответствует />=124;для полученного значения /> изтабл. 4 после интерполирования находим />=24и />=100.

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

Предприятие 1-й год 2-й год 3-й год I 350 200 24 II 50 20 100

При этом может быть полученмаксимальный доход, равный Zmax=99,l. Прямой подсчет дохода по табл. 2 длянайденного оптимального управления дает 97,2. Расхождение в результатах на 1,9(около 2%) объясняется ошибкой линейной интерполяции.

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

/>/>2.4 Учет последействия в задачахоптимального распределения ресурсов

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

Таким образом, нарушается одно изусловий, предъявляемых к задачам оптимизации, для того чтобы их можно былоописать моделью ДП. Чтобы учесть предысторию процесса распределения ресурсов,можно увеличить число параметров состояния на каждом шаге, искусственно включивв число фазовых координат все управляющие параметры: предшествующих шагов,которые определяют последействие. Если число таких параметров велико, то схемаДП усложняется настолько, что становится практически неприменимой. В случаеесли размерность искусственного фазового пространства не превышает 3-4, тозадачу можно решить вручную или (для большого числа шагов n) на машине.

Рассмотрим модель задачи оптимальногораспределения ресурсов с последействием, аналогичную задаче 2.

Задача 5. Начальные средства /> распределяются между двумяпредприятиями в течение nлет. Доход, полученный в конце k-го года от предприятий I и II, зависит от средств /> и />, выделенных соответственнов предприятия I и II в k-мгоду, и от суммы всех вложенных в предприятия I и II средств соответственно запредыдущие k—1 лет. От этих же факторов зависит ивеличина средств, которые возвращаются в конце каждого года иперераспределяются в очередном плановом периоде. Новые средства не поступают,доход в производство не вкладывается.

Требуется найти оптимальный способраспределения ресурсов между предприятиями I и II на n лет.

Обозначим через />, /> /> функции дохода, а через />и />— функции возврата средств дляпредприятии I и II соответственно.

Состояние системы /> в конце k-го шагаудовлетворяет уравнению

/>, (2.11)

а доход, полученный на k-м шаге от двух предприятий, равен

/>.      (2.12)

Величины (2.11) и (2.12) зависят нетолько от управления /> на k-м шаге, но и от всех управлении на предшествующих шагах(процесс распределения ресурсов обладает последействием).

Введем в рассмотрение две новыефазовые координаты:

/>, />,             (2.13)

полагая />. Состояние системы к началу k-гошага характеризуется тремя параметрами: />, />,/>. Так как все наличныесредства /> в k-мгоду полностью распределяются между предприятиями I и II, то />.

Уравнение состояния имеет вид

/>(2.14)

а доход на k-м шаге равен


/>.     (2.15)

Суммарный доход за n лет составляет

/>.                   (2.16)

Требуется найти неотрицательныепеременные />, обращающие в максимумфункцию (2.16) и удовлетворяющие уравнениям (2.14) при начальных условиях />, />, />.

Обозначим через /> условный максимальныйдоход, полученный за nk+1 шагов, начиная с k-го до n-го включительно, при оптимальномраспределении средств /> на этих шагах.

Функциональные уравнения (1.5) для /> имеют вид

/>

/>;

/>.                        (2.17)

Решая последовательно уравнения(2.17) для />, получим, как и выше, двепоследовательности значений /> и />. Далее при начальныхусловиях />, />, />,учитывая уравнение состояния (2.14), по цепочке получим оптимальное управление /> и />:

/>/>/>/>/>/>/>     />

/> /> /> /> /> /> /> /> /> />

/>/>/>/>/>

/>/>/>/>/>/>/>

/>


/>/>/>.

Оптимальное управление /> получается по формулам />, а соответствующий максимальныйдоход равен />.

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

Задача 6. Средства />=6 распределяются между тремя предприятиями, принадлежащими одному объединению исвязанными одним технологическим циклом так, что продукция предприятия I служитполуфабрикатом для предприятияII, и продукция первых двух предприятийслужит полуфабрикатом для предприятия III. В табл. 7 заданы функции />, />, />, характеризующие выпускпродукции в одних и тех же единицах в зависимости от вложенных средств /> в предприятия I, II, IIIсоответственно. Каждому предприятию можно выделить не более 5 ед. средств,кратных />.

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

Запишем модель ДП задачи.

Начальное состояние />=6; номер шага k—номер предприятия (k=l, 2, 3); переменные /> -средства, выделенные предприятиям I, II, IIIсоответственно,— удовлетворяют условиям

/>. (2.18)

Таблица 7

Предприятия Продукция

/>

1 2 3 4 5 I

/>

2,1 3,2 4,3 5,1 5,1 II

/>

x1      x2              

1 2 3 4 5 2,2 2,8 3.1 4,3 6 1 3,1 4.2 5,3 7,1 8 2 3,3 4,5 6,1 7,3 - 3 3,5 4,8 6,7 - - 4 5,4 5,9 - - - III

/>

          x3   

x1+x2           

1 2 3 4 5 3,4 3,8 4,2 5,0 5,0 1 3,7 4,1 4,5 5,3 5,3 2 3,7 4,1 4,5 5,4 - 3 4,0 4,5 4,8 - - 4 4,2 4,8 - - - 5 4,6 - - - - 6 - - - - -

Показатель эффективности — суммарнаяпродукция — равен

/>. (2.19)

Найти переменные />, удовлетворяющие условиям (2.18)и обращающие в максимум функцию (2.19).

Будем характеризовать состояниепроцесса распределения средств в начале k-го шага двумя параметрами: /> — остатком средств послевыделения предыдущим k—1предприятиям; /> — количествомсредств, вложенных в предыдущее предприятие (/>).Уравнения состояний имеют вид

/>               (2.20)

Пусть /> -условный максимум продукции, выпущенной предприятиями, считая с k-го до конца. Функции /> при /> удовлетворяют уравнениям

/>,

/>,                        (2.21)

/>,

Обозначим выражения, стоящие вфигурных скобках второго и третьего уравнений (2.21), соответственно через /> и />.

Условная оптимизация 3-го шагасводится к решению первого уравнения из (2.21). Результат ее совпадает сразделом III табл. 7 (здесь />).

Условная оптимизация 2-го шагапроведена в табл. 8, при этом во втором из уравнений (2.21) состояния /> и /> выражены через /> и /> из соотношений (2.20).Условные максимумы для всех />, /> в таблице подчеркнуты. Призаполнении табл. 8 использовались разделы II и III табл. 7.

Условная оптимизация 1-го шагапроведена в табл. 9 только для />=6. Прииспользовании третьего из уравнений (2.21) /> и/> выражены через /> и /> из соотношений (2.20). Прирасчетах в табл. 9 использовались раздел I табл. 7 и подчеркнутые значения /> табл. 8.

Используя результат условнойоптимизации (табл. 9, 8 и раздел III табл. 7), получим оптимальное решение.

Из табл. 9 получаем Zmax=15,l; это значение достигается при />.Отсюда />. Из табл. 8 находим />; следовательно, />. Из раздела III табл.7 определяем />.

Таким образом, при распределении />=(4, 1, 1) средств междутремя предприятиями может быть достигнут максимальный выпуск продукции,величина которого равна 15,1 ед.

Таблица 8

/>

/>

/>

/>

/>

/>

/>

/>

 

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

 

1 3,4

3,4

3,7

3,7

3,7 3,7 3,5 3,5 4,6 4,6

 

1 2,2 2,2 3,1 3,1 3,3

5,3

4,0

4,0

5,4

5,4

 

 

2 3,8 3,8 3,8 3,8 4,1 4,1 4,5 4,5 4,8 4,8

 

2 1 1 2,2 3,7

5,9

3,1 3,7

6,8

3,3 4,0

7,3

3,5 4,2

7,7

5,4 4,6

10,0

 

2 2,8 2,8 4,2 4,2 4,5 4,5 4,8 4,8 5,9 5,9

 

 

3 4,0 4,2 4,5 4,5 4,5 4,5 4,8 4,8

 

1 2 2,2 38 6,0 3,1 4,1 7,2 3,3 4,5 7,8 3,5 4,8 8,3

 

3 2 1 2,8 3,7

6,5

4,2 4,0

8,2

4,5 4,2

8,7

4,8 4,6

9,4

 

3 3,1 3,1 5,3 5,3 6,1 6,7 6,7

 

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

/>

4 5 5 5,3 5,3 5,4 5,4 1 3 2,2 4,5 6,7 3,1 4,5 7,6 3,3 4,8 8,1 4 2 2 2,8 4,1 6,9 4,2 4,5 8,7 4,5 4,8 8,4 3 1 3,1 4 7,1 5,3 4,2 9,5 6,1 4,6 10,7 4 4,3 4,3 7,1 7,1 7,3 7,3 5 5 5 5,3 5,3 1 4 2,2 5,3 7,5 3,1 5,4 8,5 5 2 3 2,8 4,5 7,3 4,2 4,8 9 3 2 3,1 4,5 7,6 5,3 4,8 10,1 4 1 4,3 4,2 8,5 7,1 4,6 11,7 5 6 6 8 8 6 5 5 1 5 2,2 5,3 7,5 2 4 2,8 5,4 8,2 6 3 3 3,1 4,8 7,9 4 2 4,3 4,8 9,1 5 1 6 4,6 10,6 6 6 6

Таблица 9

/>

/>

/>

/>

/>

/>

6 10,6 10,6 1 5 1 2,1 11,7 13,8 2 4 2 3,2 10,7 13,9 3 3 3 4,3 9,4 13,7 4 2 4 5,1 10 15,1 5 1 5 5,1 5,4 10,5
/>/>Заключение

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


/>/>Список используемых источников

1.        Беллман Р.Динамическое программирование. М.: ИЛ, 1960. 430 с.

2.        Бронштейн И.Н.,Семендяев К.А. Справочник по математике для инженеров и учащихся ВТУЗов. М.:Наука, 1986. 534 с.

3.        Каллихман И.Л.,Войтенко М.А. Динамическое программирование в примерах и задачах. М.: Высшаяшкола, 1979. 124 с.

4.        Химмельблау Д.М.Прикладное нелинейное программирование. М.: Мир, 1975. 534с.


/>/>Приложение 1Листинг программы для решения задачи оптимальногораспределения ресурсов с заданными параметрами

#include<iostream.h>

#include<conio.h>

#include<values.h>

//--------------Определяемначальные ресурсы--------------------

const ksi_0 = 6;

//--------------Класстаблицы для вывода------------------------

class Table

{

         inttx, ty, c_x, new_y;

public:

         Table();

         voidNewString(double a1, double a2, double a3,

                            doublea4, double a5, double a6, double a7);

         void EndOfTable();

};

//-------------Конструктор класса-------------------------------

Table::Table()

{

         tx=1,ty=1;

         c_x=77;

         clrscr();

         gotoxy(tx,ty);

         cout<< "┌";

         for(int i=0;i<c_x;i++)

                   cout<< "─";

         cout<< "┐";

         gotoxy(tx+7,ty);cout << "┬";

         gotoxy(tx+14,ty);cout << "┬";

         gotoxy(tx+19,ty);cout << "┬";

         gotoxy(tx+26,ty);cout << "┬";

         gotoxy(tx+26,ty);cout << "┬";

         gotoxy(tx+40,ty);cout << "┬";

         gotoxy(tx+63,ty);cout << "┬";

         gotoxy(tx,ty+1);cout << "│";

         gotoxy(tx+2,ty+1); cout << «ksi1»;

         gotoxy(tx+7,ty+1);cout << "│";

         gotoxy(tx+9,ty+1); cout << «eta1»;

         gotoxy(tx+14,ty+1);cout << "│";

         gotoxy(tx+16,ty+1);cout << «x1»;

         gotoxy(tx+19,ty+1);cout << "│";

         gotoxy(tx+21,ty+1);cout << «ksi2»;

         gotoxy(tx+26,ty+1);cout << "│";

         gotoxy(tx+28,ty+1);cout << «f2(x2,eta1)»;

         gotoxy(tx+40,ty+1);cout << "│";

         gotoxy(tx+42,ty+1);cout << «Z3_max(ksi2,eta1+x1)»;

         gotoxy(tx+63,ty+1);cout << "│";

         gotoxy(tx+65,ty+1);cout << «Z2(ksi1,eta1)»;

         gotoxy(tx+78,ty+1);cout << "│";

         gotoxy(tx,ty+2);cout << "├";

         for(i=0;i<c_x;i++)

                   cout<< "─";

         cout<< "┤";

         gotoxy(tx+7,ty+2);cout << "┼";

         gotoxy(tx+14,ty+2);cout << "┼";

         gotoxy(tx+19,ty+2);cout << "┼";

         gotoxy(tx+26,ty+2);cout << "┼";

         gotoxy(tx+26,ty+2);cout << "┼";

         gotoxy(tx+40,ty+2);cout << "┼";

         gotoxy(tx+63,ty+2);cout << "┼";

         new_y=ty+3;

}

//-------------Определениеметодов класса таблицы---------------

voidTable::NewString(double a1, double a2, double a3,

                            doublea4, double a5, double a6, double a7)

{

         gotoxy(tx,new_y);

         for(inti=0;i<c_x;i++)

                   cout<< " ";

         gotoxy(tx+7,ty+2);cout << "┼";

         gotoxy(tx+14,ty+2);cout << "┼";

         gotoxy(tx+19,ty+2);cout << "┼";

         gotoxy(tx+26,ty+2);cout << "┼";

         gotoxy(tx+26,ty+2);cout << "┼";

         gotoxy(tx+40,ty+2);cout << "┼";

         gotoxy(tx+63,ty+2);cout << "┼";

         gotoxy(tx,new_y);cout << "│";

         gotoxy(tx+2,new_y); cout << a1;

         gotoxy(tx+7,new_y);cout << "│";

         gotoxy(tx+9,new_y); cout << a2;

         gotoxy(tx+14,new_y);cout << "│";

         gotoxy(tx+16,new_y);cout << a3;

         gotoxy(tx+19,new_y);cout << "│";

         gotoxy(tx+21,new_y);cout << a4;

         gotoxy(tx+26,new_y);cout << "│";

         gotoxy(tx+28,new_y);cout << a5;

         gotoxy(tx+40,new_y);cout << "│";

         gotoxy(tx+42,new_y);cout << a6;

         gotoxy(tx+63,new_y);cout << "│";

         gotoxy(tx+65,new_y);cout << a7;

         gotoxy(tx+78,new_y);cout << "│";

         new_y++;

         if(new_y>24)

         {

                   gotoxy(tx,new_y);cout << "└";

                   for(int i=0;i<c_x;i++)

                            cout<< "─";

                   cout<< "┘";

                   gotoxy(tx+7,ty+2);cout << "┴";

                   gotoxy(tx+14,ty+2);cout << "┴";

                   gotoxy(tx+19,ty+2);cout << "┴";

                   gotoxy(tx+26,ty+2);cout << "┴";

                   gotoxy(tx+26,ty+2);cout << "┴";

                   gotoxy(tx+40,ty+2);cout << "┴";

                   gotoxy(tx+63,ty+2);cout << "┴";

                   new_y=ty+3;

         }

}

voidTable::EndOfTable()

{

         inti,j;

         gotoxy(tx,new_y);cout << "└";

         for(i=0;i<c_x;i++)

                   cout<< "─";

         cout<< "┘";

         gotoxy(tx+7,ty+2);cout << "┴";

         gotoxy(tx+14,ty+2);cout << "┴";

         gotoxy(tx+19,ty+2);cout << "┴";

         gotoxy(tx+26,ty+2);cout << "┴";

         gotoxy(tx+26,ty+2);cout << "┴";

         gotoxy(tx+40,ty+2);cout << "┴";

         gotoxy(tx+63,ty+2);cout << "┴";

         gotoxy(tx,new_y+1);

         for(j=new_y+1;j<26;j++)

         {

                   for(i=tx;i<c_x+4;i++)

                   {

                            gotoxy(i,j);

                            cout<< " ";

                   }

         }

         gotoxy(1,24);

}

//------------Сообщения-----------------------------------------

voidMessageSend(char *MessageForFunc)

{

         cout << MessageForFunc << endl;

         getch();

}

//----Определения функций,характеризующих выпуск продукции-----

double f3(intarg1, int arg2)

{

         if((arg1<0|| arg1>ksi_0) || (arg2<0 || arg2>ksi_0))

                   return(double)MAXINT;

         doubleValues[ksi_0+1][ksi_0+1]={ 0, 3.4, 3.8, 4.2, 5.0, 5.0, 0,

                                                0, 3.7, 4.1, 4.5, 5.3, 5.3, 0,

                                                0, 3.7, 4.1, 4.5, 5.4, 0,   0,

                                                0, 4.0, 4.5, 4.8, 0,   0,   0,

                                                0, 4.2, 4.8, 0,   0,   0,   0,

                                                0, 4.6, 0,   0,   0,   0,   0,

                                                0, 0,   0,   0,   0,   0,   0 };

         returnValues[arg2][arg1];

}

double f2(intarg1, int arg2)

{

         if((arg1<0|| arg1>ksi_0) || (arg2<0 || arg2>ksi_0))

                   return(double)MAXINT;

         doubleValues[ksi_0+1][ksi_0+1]={ 0, 2.2, 2.8, 3.1, 4.3, 6, 0,

                                                0, 3.1, 4.2, 5.3, 7.1, 8, 0,

                                                0, 3.3, 4.5, 6.1, 7.3, 0, 0,

                                                0, 3.5, 4.8, 6.7, 0,   0, 0,

                                                0, 5.4, 5.9, 0,   0,   0, 0,

                                                0, 0,   0,   0,   0,   0, 0,

                                                0, 0,   0,   0,   0,   0, 0 };

         returnValues[arg2][arg1];

}

double f1(intarg1)

{

         if(arg1<0|| arg1>ksi_0)

                   return(double)MAXINT;

         doubleValues[ksi_0+1]={ 0, 2.1, 3.2, 4.3, 5.1, 5.1, 0 };

         returnValues[arg1];

}

int main(void)

{

         clrscr();

         Tableob;

         intksi, eta, x, i, j, Indexes[6][5], IndexOfMax = -1, X_opt[3];

         doubleZ_2[6][5], Max=0, MayBeMax=0, Z_max;

         for(i=0;i<6; i++)

                   for(j=0;j<5; j++)

                   {

                            Z_2[i][j]=0;

                            Indexes[i][j]=-1;

                   }

         for(ksi=1;ksi<7; ksi++)

         {

                   for(eta=0;eta<5; eta++)

                   {

                            Max= MayBeMax = 0;

                            for(x=0;x<ksi + 1; x++)

                            {

                                      if((ksi+ eta) > 6)

                                               break;

                                      MayBeMax= f2(x, eta) + f3(ksi — x, x + eta);

                                      if(Max< MayBeMax)

                                      {

                                               Max= MayBeMax;

                                               IndexOfMax= x;

                                      }

                                      ob.NewString(ksi,eta, x, ksi-x, f2(x, eta), f3(ksi — x, x + eta), MayBeMax);

                                      getch();

                            }

                            if(Max>0)

                            {

                                      Z_2[ksi-1][eta]= Max;

                                      Indexes[ksi-1][eta]= IndexOfMax;

                            }

                   }

         }

         ob.EndOfTable();

         getch();

         Max =MayBeMax = 0;

         for(x= 0; x<ksi_0; x++)

         {

                   MayBeMax= f1(x) + Z_2[ksi_0 — 1 — x][x];

                   if(Max< MayBeMax)

                   {

                            Max= MayBeMax;

                            X_opt[0]= x;

                   }

         }

         Z_max= Max;

         X_opt[1]= Indexes[ksi_0 — 1 — X_opt[0]][X_opt[0]];

         Max =MayBeMax = 0;

         for(i=0;i<ksi_0 + 1; i++)

         {

                   MayBeMax= f3(i,X_opt[0]+1);

                   if(Max< MayBeMax)

                   {

                            Max= MayBeMax;

                            X_opt[2] = i;

                   }

         }

         cout <<«Максимальный выпуск продукции: » << Z_max << endl;

         cout <<«достигается при распределении средств: »;

         cout <<«x1=» << X_opt[0] << ", x2=" << X_opt[1]<< ", x3=" << X_opt[2];

         getch();

         getch();

         return 0;

}


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

┌──┬───┬──┬──┬───────┬────────────┬───────┬

│ksi1│eta1│x1│ksi2│f2(x2,eta1)│Z3_max(ksi2,eta1+x1)│Z2(ksi1,eta1)│

├───┴───┴──┴──┴───────┴───────────┴───────┴

│ 1    │ 0            │ 0  │ 1    │ 0            │ 3.4                               │3.4          │

│ 1    │ 0            │ 1  │ 0    │ 2.2         │ 0                                  │2.2          │

│ 1    │ 1            │ 0  │ 1    │ 0            │ 3.7                                │3.7          │

│ 1    │ 1            │ 1  │ 0    │ 3.1         │ 0                                  │3.1          │

│ 1    │ 2            │ 0  │ 1    │ 0            │ 3.7                               │3.7          │

│ 1    │ 2            │ 1  │ 0    │ 3.3         │ 0                                  │3.3          │

│ 1    │ 3            │ 0  │ 1    │ 0            │4                                           │ 4             │

│ 1    │ 3            │ 1  │ 0    │ 3.5         │0                                  │ 3.5          │

│ 1    │ 4            │ 0  │ 1    │ 0            │4.2                               │ 4.2          │

│ 1    │ 4            │ 1  │ 0    │ 5.4         │0                                  │ 5.4          │

│ 2    │ 0            │ 0  │ 2    │ 0            │3.8                               │ 3.8          │

│ 2    │ 0            │ 1  │ 1    │ 2.2         │3.7                               │ 5.9          │

│ 2    │ 0            │ 2  │ 0    │ 2.8         │0                                  │ 2.8          │

│ 2    │ 1            │ 0  │ 2    │ 0            │4.1                               │ 4.1          │

│ 2    │ 1            │ 1  │ 1    │ 3.1         │3.7                               │ 6.8          │

│ 2    │ 1            │ 2  │ 0    │ 4.2         │0                                  │ 4.2          │

│ 2    │ 2            │ 0  │ 2    │ 0            │ 4.1                              │ 4.1          │

│ 2    │ 2            │ 1  │ 1    │ 3.3         │4                                  │ 7.3          │

│ 2    │ 2            │ 2  │ 0    │ 4.5         │0                                  │ 4.5          │

│ 2    │ 3            │ 0  │ 2    │ 0            │ 4.5                               │4.5          │

│ 2    │ 3            │ 1  │ 1    │ 3.5         │4.2                               │ 7.7          │

│ 2    │ 3            │ 2  │ 0    │ 4.8         │0                                  │ 4.8          │

│ 2    │ 4            │ 0  │ 2    │ 0            │4.8                               │ 4.8          │

│ 2    │ 4            │ 1  │ 1    │ 5.4         │4.6                               │ 10           │

│ 2    │ 4            │ 2  │ 0    │ 5.9         │0                                  │ 5.9          │

│ 3    │ 0            │ 0  │ 3    │ 0            │ 4.2                               │4.2         │

│ 3    │ 0            │ 1  │ 2    │ 2.2         │4.1                               │ 6.3          │

│ 3    │ 0            │ 2  │ 1    │ 2.8         │3.7                               │ 6.5          │

│ 3    │ 0            │ 3  │ 0    │ 3.1         │ 0                                  │3.1          │

│ 3    │ 1            │ 0  │ 3    │ 0            │4.5                               │ 4.5          │

│ 3    │ 1            │ 1  │ 2    │ 3.1         │4.1                               │ 7.2          │

│ 3    │ 1            │ 2  │ 1    │ 4.2         │ 4                                 │ 8.2          │

│ 3    │ 1            │ 3  │ 0    │ 5.3         │0                                  │ 5.3          │

│ 3    │ 2            │ 0  │ 3    │ 0            │4.5                               │ 4.5          │

│ 3    │ 2            │ 1  │ 2    │ 3.3         │4.5                               │ 7.8          │

│ 3    │ 2            │ 2  │ 1    │ 4.5         │4.2                               │ 8.7          │

│ 3    │ 2            │ 3  │ 0    │ 6.1         │0                                  │ 6.1          │

│ 3    │ 3            │ 0  │ 3    │ 0            │4.8                               │ 4.8          │

│ 3    │ 3            │ 1  │ 2    │ 3.5         │4.8                               │ 8.3          │

│ 3    │ 3            │ 2  │ 1    │ 4.8         │4.6                               │ 9.4          │

│ 3    │ 3            │ 3  │ 0    │ 6.7         │0                                  │ 6.7          │

│ 4    │ 0            │ 0  │ 4    │ 0            │5                                  │ 5             │

│ 4    │ 0            │ 1  │ 3    │ 2.2         │4.5                               │ 6.7          │

│ 4    │ 0            │ 2  │ 2    │ 2.8         │4.1                               │ 6.9          │

│ 4    │ 0            │ 3  │ 1    │ 3.1         │4                                  │ 7.1          │

│ 4    │ 0            │ 4  │ 0    │ 4.3         │0                                  │ 4.3          │

│ 4    │ 1            │ 0  │ 4    │ 0            │5.3                               │ 5.3          │

│ 4    │ 1            │ 1  │ 3    │ 3.1         │4.5                               │ 7.6          │

│ 4    │ 1            │ 2  │ 2    │ 4.2         │4.5                               │ 8.7          │

│ 4    │ 1            │ 3  │ 1    │ 5.3         │4.2                               │ 9.5          │

│ 4    │ 1            │ 4  │ 0    │ 7.1         │0                                  │ 7.1          │

│ 4    │ 2            │ 0  │ 4    │ 0            │5.4                               │ 5.4          │

│ 4    │ 2            │ 1  │ 3    │ 3.3         │4.8                               │ 8.1          │

│ 4    │ 2            │ 2  │ 2    │ 4.5         │4.8                               │ 9.3          │

│ 4    │ 2            │ 3  │ 1    │ 6.1         │4.6                               │ 10.7        │

│ 4    │ 2            │ 4  │ 0    │ 7.3         │0                                  │ 7.3          │

│ 5    │ 0            │ 0  │ 5    │ 0            │5                                  │ 5             │

│ 5    │ 0            │ 1  │ 4    │ 2.2         │5.3                               │ 7.5          │

│ 5    │ 0            │ 2  │ 3    │ 2.8         │4.5                               │ 7.3          │

│ 5    │ 0            │ 3  │ 2    │ 3.1         │4.5                               │ 7.6          │

│ 5    │ 0            │ 4  │ 1    │ 4.3         │4.2                               │ 8.5          │

│ 5    │ 0            │ 5  │ 0    │ 6            │0                                  │ 6             │

│ 5    │ 1            │ 0  │ 5    │ 0            │5.3                               │ 5.3          │

│ 5    │ 1            │ 1  │ 4    │ 3.1         │5.4                               │ 8.5          │

│ 5    │ 1            │ 2  │ 3    │ 4.2         │4.8                               │ 9             │

│ 5    │ 1            │ 3  │ 2    │ 5.3         │ 4.8                              │ 10.1        │

│ 5    │ 1            │ 4  │ 1    │ 7.1         │4.6                               │ 11.7        │

│ 5    │ 1            │ 5  │ 0    │ 8            │0                                  │ 8             │

│ 6    │ 0            │ 0  │ 6    │ 0            │ 0                                  │0             │

│ 6    │ 0            │ 1  │ 5    │ 2.2         │5.3                               │ 7.5          │

│ 6    │ 0            │ 2  │ 4    │ 2.8         │5.4                               │ 8.2          │

│ 6    │ 0            │ 3  │ 3    │ 3.1         │ 4.8                               │7.9          │

│ 6    │ 0            │ 4  │ 2    │ 4.3         │4.8                               │ 9.1          │

│ 6    │ 0            │ 5  │ 1    │ 6            │4.6                               │ 10.6        │

│ 6    │ 0            │ 6  │ 0    │ 0            │0                                  │ 0             │

└──────────────────────────────────────────

Максимальный выпуск продукции:15.1

достигается прираспределении средств: x1=4, x2=1, x3=1

еще рефераты
Еще работы по информатике, программированию