3ПОИСКОВАЯ ОПТИМИЗАЦИЯ

3.1Понятие линейного программирования

Линейное программирование – раздел математического программирования,

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

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

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

3.2Типы задач, решаемые методами линейного программирования

3.2.1 Задача о наилучшем использовании ресурсов

Пусть некоторая производственная единица (цех, завод, объединение и т.д.) исходя их конъюнктуры рынка, технических и технологических возможностей и имеющихся ресурсов может выпускать N различных видов продукции (Прод1, Прод2,…Продn). Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий и других производственных факторов. Все эти виды ограничивающих факторов называют ингредиентами Ri. Пусть их число равно m. Они ограничены, и их количества равны соответственно b1, b2…bm условных единиц. Таким образом b=(b1; b2;…;bi;…bm) – вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая по различным факторам (по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т.п.). Примем в качестве такой меры, цену реализации сj. Вектор цен с=(с1; с2;…;cj;…;cn). Известны также технологические коэффициенты aij, которые указывают, сколько единиц i-го ресурса требуется для производства продукции j вида. Матрицу коэффициентов aij называют технологической и обозначают буквой А. Имеем A=[aij].

Обозначим через х = (х1;…;xj;…;xn) план производства, показывающий, какие виды товаров Прод1, Прод2…, Продn нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.

Тогда общий объем реализации будет следующий:

ЦФ=с1х1+…сnxn

Это выражение – целевая функция, которую нужно максимизировать.

15

Так как aijxj расход i-го ресурса на производство xj единиц j-той продукции, то, просуммировав расход i-го ресурса на выпуск всех N видов продукции, получим общий расход этого ресурса, который не должен превосходить bi единиц:

Ai1x1+…+aijxj+…+ainxn<=bi

Чтобы искомый план х=(х1;х2;…;xj;…;xn) был реализован наряду с

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

Xj>=0 (j=1,N)

Таким образом, математическая модель задачи о наилучшем использовании ресурсов имеет вид:

Найти:

max ЦФ = åcj xj

i=1

При ограничениях:

3.2.2 Задача о выборе оптимальных технологий

В задаче о наилучшем использовании ресурсов определяется оптимальный план выпуска продукции. Пусть при производстве какого-либо продукта используется n технологий. При этом требуется m видов ресурсов, заданных объемами bi (i=1,m). Эффективности технологий, т.е. количество конечной продукции (в рублях), производимой в единицу времени по j-той технологии (j=1,n), обозначим cj. Пусть aij – расход i-го ресурса в единицу вресени по j-той технологии. Пренебрегая временем переналадок, необходимым для перехода от одной технологии к другой, получаем следующую математическую модель задачи: найти план интенсивностей использования технологий х=(х1;…;хn), обеспечивающий максимум выпуска продукции в стоимостном выражении:

16