Введение. Методы оптимизации, как научная дисциплина, по существу считается частью более общей дисциплины – «Исследование операций»

Методы оптимизации, как научная дисциплина, по существу считается частью более общей дисциплины – «Исследование операций». Начало ее развития связывают с сороковыми годами двадцатого столетия. Отправной, наиболее крупной и значимой работой в этой области считается монография Л.В.Канторовича «Математические методы организации и планирования производства», вышедшая в 1939 году (в 1975 году Л.В.Канторовичу за цикл работ в области оптимального использования ресурсов в экономике была присуждена Нобелевская премия). Но уже в 1930 году советский ученый А.Н.Толстой предложил модель транспортной задачи. В зарубежной научной практике одним из пионеров в области линейного программирования был Джон фон Нейман, знаменитый математик и физик, успешно работавший в области теории игр, тесно связанной с методами линейного программирования. В зарубежной научной литературе ключевой обычно считается работа Дж.Данцига, вышедшая в 1947 году и посвященная решению линейных экстремальных задач, в которой автор, опираясь на методы линейной алгебры, смог сформулировать и развить «симплексный метод».

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

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

Задача оптимизации записывается следующим образом:

,

т.е. равнозначны два варианта задачи:

или .

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

Типы моделей. Математическая модель – одно или система уравнений, отражающих количественную связь между входящими в модель параметрами. Целью составления модели является исследование взаимозависимости между ними, а также исследование управления процессами, которые описываются данными моделями. Уровень точности и результативности конкретной математической модели существенно зависят от ряда факторов, в том числе:

- полноты учета независимых параметров;

- точности исходных параметров;

- видов и методов математического аппарата, привлекаемого для составления модели.

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

- одномерная модель отражает положение точки на числовой оси,

(например, х=а);

- двумерная модель отражает положение точки на плоскости,

(например, ах₁ +bх₂ =с);

- трехмерная модель отражает положение точки на какой-то поверхности,

(например, ах₁ + bх₂ + сх₃ =d);

- многомерная модель имеет количество независимых параметров более

трех (например, ах₁ + bх₂ + сх₃ + dх₄ =е).

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

Независимые параметры входят в структуру модели с различными степенями:

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

линию (двумерная модель)

ах₁ +bх₂ =с,

или плоскость

ах₁ + bх₂ + сх₃ =d;

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

,

или незамкнутую поверхность (например, параболоид вращения)

.

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

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

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

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

I. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1. Производственная задача или задача планирования

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

Задача 1. Для изготовления трех видов продукции А, В, С, используются следующие металлообрабатывающие станки: токарные, фрезерные, шлифовальные и используется сварочное оборудование. Предприятие обычно имеет ограниченные ресурсы по использованию станочного парка. На обработку каждого из типов изделий по каждому виду работ надо затратить определенное количество времени (станкочасов). Обозначим его через а_ij, где i - тип оборудования, j- вид изделия. Готовые изделия реализуются на рынке. При этом стоимость каждого изделия составляет с_j (например, руб/шт).

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

Воспользовавшись числовыми показателями (произвольно), представим условия задачи в табличной форме (таблица 1).

Обозначим количество производимых изделий по видам следующим образом:

А - х₁, В - х₂, С - х₃ .

Составим математическую модель производства:

- при работе фрезерного оборудования общие затраты станкочасов должны

подчиняться следующему неравенству:

Таблица 1

Условия производства

;

- при работе токарных станков общее время их загрузки должно отвечать неравенству:

;

- суммарная загрузка шлифовальных станков должна отвечать неравенству:

;

- сварочное оборудование может быть использовано на программу выпуска в соответствии с неравенством:

.

Приведенные выше неравенства называются ограничениями задачи. Они могут быть неравенствами типа как “ ≤ ”, так и “ ≥ “, возможны ограничения и в виде равенств. По смыслу задачи очевидны такие ограничения:

, , .

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

.

Целью задачи является нахождение такого плана производства, при котором функция F будет максимальной, т.е.:

.

Функция F называется функцией цели или функционалом.

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

Пусть имеется некоторый экономический объект, который может производить продукцию, ассортимент которой составляет п видов изделий. В процессе производства допустимо использование m видов ресурсов. Применяемые технологии характеризуются нормами затрат соответствующего ресурса по каждому виду изделия в количестве а_ij (где i=1…m, j=1…n). Если принять, что предприятие располагает каждым из ресурсов в объеме не более b_i, то при плане производства x_j по каждому типу изделия процесс должен подчиняться ограничениям:

(1)

Система линейных неравенств (1) с позиций векторной алгебры характеризуется следующим. Суммарные технологические нормативы для данного производства описываются матрицей:

Она называется технологической характеристикой предприятия. Сводный план производства (по видам изделий) может быть представлен в виде п – мерного вектора-строки:

.

Тогда общие затраты по i – му ресурсу на производство всех видов изделий можно выразить в виде суммы:

.

Она представляет собой скалярное произведение векторов А и Х. Ограничения на ресурсы, которыми располагает предприятие, описываются m - мерным вектор-столбцом:

,

где b_i - максимальное количество i – го ресурса, которое можно использовать в производственном процессе.

Тогда систему неравенств (1) можно записать в кратком виде, используя правила векторной алгебры, представив левую часть неравенств как произведение матрицы А на вектор Х, а правую – как вектор В:

. (2) К системе также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства: , , … ,… , или, что то же самое

. (3)

Обозначив через с_j цену единицы j – го продукта и записав вектор-строку

,

получим выражение суммарного дохода от выполнения плана производства, задаваемого вектором Х:

или . (4)

Это векторная запись функции цели. Формулы (2,3,4) являются не чем иным, как простейшей математической моделью, описывающей отдельные стороны функционирования некоторого, например, экономического объекта, поведением которого мы хотим управлять. В рамках данной модели, вообще говоря, можно формулировать различные задачи. Но скорее всего самой естественной задачей будет задача поиска такого плана производства, который дает наибольшее (наименьшее) значение целевой функции (4), но одновременно удовлетворяет и ограничениям (2,3). Кратко такую задачу записывают в следующем виде:

, где

. (5)

Это векторная запись задачи линейного программирования (ЗЛП) типа планирования производства.

Несмотря на очевидную простоту задачи (5), ее решение является далеко не тривиальным и во многом стало возможным только после разработки специального математического аппарата. Существенным достоинством методов решения ЗЛП является их универсальность, поскольку к модели (5) могут быть сведены очень многие как экономические, так и неэкономические проблемы.

Поскольку любая научная модель содержит упрощающие предпосылки, для корректного применения получаемых с ее помощью результатов необходимо четкое понимание сути этих упрощений, что в конечном итоге позволяет сделать вывод об их допустимости или недопустимости. Наиболее «сильным» упрощением в рассмотренных моделях является предположение о прямо пропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат а_ij В действительности , что приводит к нелинейности функции цели, а соответственно к принципиальному изменению типа задачи. К другим упрощающим предпосылкам относятся предположения о независимости цен c_j от объемов производства x_j, что может быть справедливо только при незначительных объемах выпуска. Подобные «уязвимые» места модели важно знать, так как они позволяют наметить принципиальные направления совершенствования модели.

Поиск по сайту: