Постановка задачи. Линейные задачи оптимизации

Линейные задачи оптимизации

Введение

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

Многие задачи в экономике являются многовариантными. Среди множества возможных вариантов решения приходится отыскивать наилучшее в некотором смысле. При этом решение должно удовлетворять ограничениям, определяемым природными, экономическими и технологическими возможностями. Пусть различные варианты решения получаются за счет выбора вектора x=(x₁,…, x_n) управляющих параметров из множества X. Если критерием, по которому отбирается лучшее решение, является линейная по переменным x₁,…, x_n функция (целевая функция), а множество X задается системой линейных по тем же переменным уравнений и неравенств, то такая задача называется задачей линейного программирования.

Одним из основоположников теории линейного программирования был Л.В. Канторович. В 1939 году вышла его работа «Математические методы организации и планирования производства». Спустя 10 лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач – симплекс-метод.

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

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

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

Излагаемый материал основан на работах [1 – 3].

Прежде чем перейти к формальной теории, рассмотрим пример. Небольшая фабрика изготавливает два вида красок: для внутренних (K ₁) и наружных работ(K ₂). Для производства красок используется два исходных продукта A и B. На фабрике имеются: емкость для хранения продукта A вместимостью 8т; емкость для продукта B вместимостью 6т. Ежесуточно перед работой емкости с продуктами A и B наполняются полностью. Для производства 1т краски K ₁ расходуется 1/3т продукта A и 2/3т продукта B. Для производства 1т краски K ₂ расходуется 2/3т продукта A и 1/3т продукта B. Краски K ₁ и K ₂ продаются на оптовом рынке по цене 2 и 3 денежные единицы за тонну соответственно.

Изучение сбыта показало, что суточный спрос на краску K ₁ может превосходить спрос на краску K ₂ не более чем на 3 тонны. Кроме того, спрос на краску K ₁ не превышает 6т в сутки.

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

Дата добавления: 2014-12-27