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

Введение

Прокурорский надзор

Учебно-методическое пособие

Путилин Владимир Валерьевич

Пономарева Наталья Сергеевна

Подписано в печать _____. Формат 60 х 84 1/16

Бумага офсетная. Гарнитура Таймс Новая. Печать офсетная.

Усл.-печ. л. ____

Тираж экз. Заказ №

Воронежский институт МВД России

394065 Воронеж, просп. Патриотов, 53

Типография Воронежского института МВД России

394065 Воронеж, просп. Патриотов, 53

[1] Далее - Закон о прокуратуре РФ.

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

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

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

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

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

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

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

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