 |
Математическая формализация оптимизационной проблемы
|
|
|
|
Математическая формализация оптимизационной проблемы
Искусство управления может рассматриваться как искусство выбора наилучшей с точки зрения управляющего альтернативы среди всех реализуемых альтернатив. В математике процесс выбора наилучшей альтернативы принято называть оптимизацией. Как известно, одним из основных отличий науки от искусства является возможность алгоритмизации. Воспользуемся простейшей задачей производственного планирования [Mathur, с. 159] и сформулируем алгоритм постановки оптимизационной задачи.
Математическая формализация оптимизационной проблемы
Фирма Creative Coffees производит и продает два сорта кофе: Regular и Decaf. На текущий месяц запас кофейных зерен на складе фирмы составляет 200 тонн, а суммарное время жарки зерен ограничено 300 часами. Каждая тонна кофе Regular производится из одной тонны зерен, обжариваемых в течение одного часа, и приносит производителю прибыль в размере $3000. Каждая тонна кофе Decaf также производится из одной тонны зерен, но обжариваемых в течение двух часов, и приносит фирме прибыль в размере $5000. Представим условия задачи в табличной форме:
Таблица 1
| Regular (т) | Decaf (т) | Запас сырья | |
| Зерна (т) | 1 | 1 | 200 |
| Время жарки (ч) | 1 | 2 | 300 |
| Прибыль от продажи ($1000/т) | 3 | 5 |
Определим план выпуска кофе, при котором прибыль фирмы за текущий месяц будет максимальна.
. Переменные, подлежащие определению в результате решения задачи, называются оптимизируемыми. Вектор оптимизируемых переменных называется альтернативой или планом.
Укажем переменные, подлежащие определению в результате решения задачи, и введем понятие плана.
В результате решения задачи производителю (продавцу) необходимо определить, какое количество каждого из сортов кофе следует выпустить. Введем следующие обозначения:- количество кофе Regular, которое следует произвести в текущем месяце,- количество кофе Decaf, которое следует произвести в текущем месяце, и назовем вектор x=(x1, x2) планом выпуска.
|
|
|
Как правило, в каждой проблемной ситуации существует ряд ограничений, не позволяющих реализовать на практике те или иные альтернативы.
. Планы, которые могут быть практически реализованы, называются допустимыми. Множество допустимых планов называется допустимым множеством.
Допустимость альтернативы определяется, в основном, ограниченностью ресурсов, находящихся в распоряжении предпринимателя. Отметим ряд типичных ограничений, которые определяют множество допустимых альтернатив в процессе принятия управленческих решений.
Производственные ограничения - это ограничения, связанные с возможностью выпустить и реализовать ограниченное количество продукции (оказать ограниченный объем услуг), располагая ограниченным количеством ресурсов (денежных средств, сырья, производственных помещений и оборудования, рабочего времени и квалификации персонала).
Рыночные (сбытовые) ограничения - это ограничения, связанные с возможностью реализовать ограниченное количество продукции в рамках избранной ценовой стратегии, а также с необходимостью выполнения заключенных контрактов.
Временные ограничения - это ограничения на время, отпущенное на решение проблемы.
Логические ограничения - это ограничения, связанные с природой оптимизируемых переменных (например, неотрицательность цен, объемов затрат ресурсов и потребления товаров).
Внешние ограничения - это социальные, правовые, этические ограничения, порожденные воздействием общества на бизнес.
Составим уравнения и неравенства, определяющие множество допустимых планов.
|
|
|
Допустимость плана в задачах производственного планирования определяется, прежде всего, тем, хватит ли имеющихся в наличии ресурсов на его реализацию. Выпуск x1 тонн кофе Regular требует x1 тонн кофейных зерен и x1 часов их жарки, а выпуск x2 тонн кофе Decaf требует x2 тонн кофейных зерен и 2x2 часов их жарки. Таким образом, план x=(x1, x2) допустим, если
 (1)
|
Производственные ограничения дополняются логическими ограничениями, связанными с природой введенных в рассмотрение переменных. В данном случае объемы выпуска товаров не могут быть отрицательными: x³0. (2)
Рассмотрим геометрическую интерпретацию понятий: план, допустимый план, множество допустимых планов. Введем в рассмотрение декартову прямоугольную систему координат с осями, соответствующими оптимизируемым переменным, и, учитывая неравенство (2), изобразим ее первый квадрант (рис. 1). Любая точка в нем - план выпуска x=(x1, x2), причем план допустим, если его координаты удовлетворяют соотношениям (1), и не допустим - в противном случае.
Изобразим все планы, на которые хватит зерен кофе: x1+x2£200. С этой целью построим отрезок прямой x1+x2=200. На этом отрезке лежат планы выпуска, полностью исчерпывающие запас зерен, ниже - планы, на которые зерен хватит с избытком, выше - не допустимые планы.
Изобразим все планы, на реализацию которых хватит времени: x1+2x2£300. С этой целью построим отрезок прямой x1+2x2=300. На этом отрезке лежат планы выпуска, полностью исчерпывающие запас времени, ниже - планы, на которые времени хватит с избытком, выше - не допустимые планы.
Таким образом, множество допустимых планов - есть затененная область X на рис. 1 (множество планов, на реализацию которых хватит и первого, и второго ресурса):
Рис. 1 - Допустимое множество в проблеме производственного планирования
Почему невозможно реализовать план y, план z (рис. 1)?
Возникает вопрос: какой из допустимых планов является лучшим для производителя?
. Функция, сопоставляющая альтернативам действительные числа, называется целевой (критериальной), если большее (меньшее) ее значение указывает на строго более предпочтительную альтернативу, а одинаковые значения - на равноценные альтернативы.
Построим целевую (критериальную) функцию
|
|
|
В рассматриваемой задаче из двух допустимых планов лучшим является тот, который принесет фирме большую прибыль. При реализации плана x=(x1, x2) прибыль составит
p(x)=3x1+5x2
тысяч денежных единиц.
Как отмечалось выше, в процессе планирования производитель ищет такой реализуемый план выпуска товара, который принесет ему наибольшую прибыль. Приведем общую математическую постановку такого рода оптимизационных задач.
Предположим, имеется n оптимизируемых переменных, и, соответственно, план x является n-мерным вектором. Обозначим допустимое множество через X, целевую функцию через F.
. Глобальным максимумом (минимумом) функции F(x) на множестве X называется такой допустимый вектор х*X, что
| F(x*) F(x) (F(x*) £F(x)) xX. | (3) |
Максимумы и минимумы функции принято называть ее экстремумами.
. Задача нахождения глобального максимума (минимума) функции F(x) на множестве X называется задачей математического программирования (ЗМП) и записывается в виде
| F(x) max, xX (F (x) min, xX). | (4) |
Решение задачи (4) обозначается
x* = argmax F(x), xX, (x* = argmin F(x), xX),
и называется оптимальным планом. Число F(x*) называется значением задачи (4) и обозначается max F(x) (min F(x)).
. Решить ЗМП - значит найти все ее решения или доказать, что их не существует.
Выпишем получившуюся математическую модель оптимизационной задачи или задачу математического программирования:
p(x)=3x1+5x2 ® max,  (5)
|
Таким образом, для математической формализации проблемы производственного планирования фирмы Creative Coffees мы воспользовались следующим алгоритмом.
Алгоритм математической формализации оптимизационной проблемы.
Указать переменные, подлежащие определению в результате решения задачи, ввести понятие плана.
Составить уравнения и неравенства, определяющие множество допустимых планов.
Построить целевую (критериальную) функцию.
Выписать получившуюся задачу математического программирования.
. Задача математического программирования, целевая функция которой является линейной, а допустимое множество задано системой линейных уравнений и неравенств, называется задачей линейного программирования (ЗЛП).
|
|
|
. ЗЛП называется стандартной задачей линейного программирования, если все ограничения выражены линейными неравенствами одинакового направления (как правило, £), все оптимизируемые переменные предполагаются неотрицательными.
Таким образом, задача (5) - стандартная задача линейного программирования. Если ввести обозначения
ее можно записать в виде
p(x)=сx ® max, Ax£b, x³0.
. ЗЛП называется канонической задачей линейного программирования, если все ограничения выражены линейными равенствами, все оптимизируемые переменные предполагаются неотрицательными.
Для приведения стандартной задачи линейного программирования к канонической следует все неравенства системы ограничений заменить равенствами, введя в левой части каждого неравенства дополнительную переменную.
. Перейдите от стандартной ЗЛП (5) к канонической.
. Каждый галлон молока, фунт сыра и яблок обеспечивает организм определенным количеством миллиграмм протеина и витаминов A, B, C в соответствии с данными приведенной ниже таблицы. Наряду с этими данными, таблица содержит информацию о минимальных ежедневных потребностях организма в вышеупомянутых веществах, представленную Департаментом сельского хозяйства США. Кроме того, в таблицу включены данные о минимальном количестве каждого из продуктов, которое должно войти в меню, и цены продуктов.
Таблица 2
| Молоко (мг/галлон) | Сыр (мг/фунт) | Яблоки (мг/фунт) | Минимальные потребности организма (мг) | |
| Протеины | 40 | 30 | 10 | 80 |
| Витамин A | 5 | 50 | 30 | 60 |
| Витамин B | 20 | 30 | 40 | 50 |
| Витамин С | 30 | 50 | 60 | 30 |
| Минимальное количество в диете | 0,5 гал. | 0,5 фунта | 0,5 фунта | |
| Цена ($) | 2,15 | 2,25 | 1,25 |
Постройте математическую модель оптимизационной проблемы, предполагая, что из двух диет, обеспечивающих организм необходимым количеством питательных веществ, лучшей является более дешевая.
|
|
|
