Лекции.Орг


Поиск:




Одношаговые задачи управления




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

Одношаговая задача считается за­данной, если известны: пространство состоянии внешней среды с распределением вероятностей для всех , про­странство решений X и критерий качества принятого ре­шения, называемым целе­вой функцией. Целевую функцию, выра­жающую в явном виде цели управления, можно рас­сматривать как выходную величину объекта управления и обозначить через q. Целевая функция является ска­лярной величиной, зависящей от состояния природы J и от состояния объекта управления х, и может быть записана в виде

Решение этой задачи со­стоит в нахождении такого , которое обращает в минимум функцию q, т. е. удовлетворяет условию

Если стоит задача не минимизации, а максимизации функции q, то необходимо рассматривать функцию .

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

Задача называется детерминированной, если нет не­определенности в отношении состояния природы . В де­терминированных задачах пространство состояний при­роды состоит всего из одного элемента , вероятность которого равна единице. В этом случае целевая функция будет зависеть только от состояния объекта управления

Для решения одношаговой задачи широко используются методы математического программирования. Эти методы дают возможность найти значения перемен­ных х1,...,xN, удовлетворяющих ограничениям как в виде равенств, так и в виде неравенств и обра­щающих в минимум целевую функцию q(x1,...,xN). На переменные обычно накладываются добавочные условия не отрицательности их значений.

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

и удовлетворяют системе ограничений

где показатель эффективности приходящийся на единицу переменной хi, аij затраты ресурса на единицу хj, m – число ресурсов.

 

Существо задач линейного программирования пояс­ним на ряде примеров.

1. Задача об использовании ресурсов. Для осущест­вления l различных технологических процессов заводу требуется т видов ресурсов S1,..., Sm (сырье, топливо, материа­лы, инструмент и т. п.). Запасы ресурсов каждого вида ограничены и равны b1,..., bm. Известен расход ресурсов на единицу продук­ции по каждому технологическому процессу. Требуется определить, в каком количестве требуется выпускать продукцию каждого вида, чтобы доход от реализации этой продукции был максимальным.

Обозначим через aij расход ресурсов вида Si, на единицу про­дукции вида Tj, а через сi — доход от реализации единицы про­дукции вида Tj. Все имеющиеся данные представим в виде табл. 1, положив l=3, т=4.

Таблица 1

Обозначим через хj количество единиц выпускаемой продукции вида Тj. Ограничениями в этой задаче являются требования, чтобы расход ресурсов вида Si на выпуск всех видов про­дукции не превышал имеющихся запасов:

Эти ограничения легко превратить в уравнения, введя перемен­ные , означающие неиспользованные ресурсы вида Si. При этом получим:

Величина дохода от реализации выпущенной продукции будет равна:

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

2. Задача о распределении выпуска продукции по предприятиям. План отрасли предусматривает за время Т выпуск следующих видов продукции:

А1 в количестве N1 штук;

А2 в количестве N2 штук;

Al в количестве Nl штук.

Эти виды продукции могут выпускаться на r однородных пред­приятиях П1,…,Пr. Предполагаем, что ни одно предприятие не может одновременно выпускать несколько видов продукции. Кроме того, задано:

— количество продукции Аi, выпускаемой на предприятии Пj, в единицу времени;

— стоимость единицы продукции вида Аi, выпущенной на предприятии Пj;

— время работы предприятия Пj по выпуску продукции Аi.

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

Ограничения:

1) время работы каждого предприятия не должно превышать Т

2) количество выпускаемой продукции должно соответствовать номенклатуре

Целевая функция будет представлять собой общую стоимость выпущенной продукции. Если принять во внимание, что величина представляет собой стоимость части продукции Аi, выпу­скаемой предприятием Пj, то общая стоимость выпускаемой продукции

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

3. Транспортная задача. В пунктах P1,..., Pl имеется однородный груз в количествах , его необходимо перевез­ти в пункты Q1,..., Qr в количествах b1,..., br так, чтобы общая стоимость перевозок была минимальна. При этом предполагается, что количество требуемого груза равно имеющимся запасам

Обозначим через xij количество груза, перевозимого из пункта Рi в пункт Qj, а через сij — стоимость перевозки единицы этого груза. В задаче имеются следующие ограничения:

1) количество груза, отправляемого из пункта Рi на все пунк­ты назначения, должно быть равно имеющимся запасам аi

2) количество груза, прибываемого в Qj, со всех пунктов отправ­ления, должно равняться потребности ,

Целевая функция определяет полную стоимость перевозки всех грузов

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

Пример 1. Предприятие имеет возможность реализовать не более четырех технологических процессов одновременно, причем тех­нологические процессы П1 и П2 используются для производства продукта А, а технологические процессы П3 и П4 — для произ­водства продукта В. Расходы, связанные с реализацией каждо­го технологического процесса, определяются трудозатратами (в человеко-неделях), а также количествами (в килограммах) материалов М и N, потребляемых в течение недели. Основ­ные производственно-экономические показатели приведены в табл. 2, где доходы от производства 1 кг продукта выражены в условных денежных единицах и зависят как от вида продукта, так и от используемого технологического процесса.

Таблица 2

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

Ответ:

где х1 и х2 — объемы производства продукта А с использова­нием технологических процессов П1 и П2 соответственно; х3 и x4 — объемы производства продукта В с использованием тех­нологических процессов П3 и П4 соответственно.

Пример 2. Птицеводческая фабрика имеет возможность заку­пать до трех ингредиентов, используемых для приготовления кормовой смеси, расход которой составляет не менее 20 000 кг в неделю. По используемой технологии выращивания цыплят эта смесь должна содержать: а) не менее 0,8 %, но и не более 1,2 % кальция; б) не менее 22 % белка; в) не более 5 % клетчатки.

Постройте математическую модель задачи минимизации недельных затрат на закупки ингредиентов для приготовления кормовой смеси, соответствующей используемому технологи­ческому процессу. Данные, характеризующие стоимость 1 кг каждого ингредиента (в условных денежных единицах) и со­держание в нем (по весу в 1 кг) питательных веществ (кальций, белок, клетчатка), представлены в табл. 3.

 

Таблица 3

Ответ:

где xk — объем закупок известняка (k = 1), зерна (k=2) и соевых бобов (k=3) в неделю, кг.

Пример 3. Задача по раскрою материала. Листы материала 6х13 м надо раскроить так, чтобы получить заготовки двух видов: 800 штук размером 4х5 м. и 400 штук размером 2х3 м. При этом отходы должны быть минимальными. Способы раскроя материала и количество заготовок каждого типа, полученных при раскрое одного листа, заданы в табл.4.

 

Таблица 4

Размер заготовки Число заготовок при способах раскроя, шт.
       
4 х 5 2 х 3          

Пусть хi –число листов, раскроенных i-м способом. Тогда вектор переменных будет иметь вид х=(х1 , х2, х3, х4).

Объём заготовок (ограничение) можно записать:

Зх1 + 2х2 + х3 = 800,

х1 + 6х2 + 9х3 + 13х4 = 400.

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

12х1 + 2х2 + 4х3 = q(x) min.

Линейное программирование

Допустим, дана система т линейно независимых уравнений с n неизвестными x1,…, хп, называемая системой ограниче­ний задачи линейного программирования:

Характерной особенностью данной задачи является то, что число уравнений меньше числа неизвестных, т. е. m<n. Требуется найти неотрицательные значения пере­менных , которые удовлетворяют урав­нениям ограничения и обращают в минимум целевую функцию

Иногда в задаче линейного программирования все или некоторые из уравнений имеют вид не­равенств. Так, вместо уравнения

в систему может входить неравенства вида

или

От таких неравенств легко перейти к урав­нениям, вводя добавочную переменную хn+j³0 так, что­бы в зависимости от знака неравенства имело место одно из двух выражений

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

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

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





Поделиться с друзьями:


Дата добавления: 2015-11-05; Мы поможем в написании ваших работ!; просмотров: 488 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Лаской почти всегда добьешься больше, чем грубой силой. © Неизвестно
==> читать все изречения...

951 - | 880 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.008 с.