Маематическое программирование

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

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

Методами  математического программирования решаются задачи распределения ресурсов, планирования выпуска продукции, ценообразования, транспортные задачи и т.п.

Математическое  программирование возникло в 30-е годы XX века. Венгерский математик Б.Эгервари в 1931 году решил задачу, называемую проблемой выбора. Американский ученый Г.У. Куй обобщил этот метод, после чего он получил название венгерского метода. В 1939 году российский ученый Л.В. Канторович разработал метод разрешающих множителей решения задач линейного программирования. В 1949 году американский ученый Дж. Данциг опубликовал один из основных методов решения задач линейного программирования, получивший название симплексный.

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

Составление математической модели задачи включает следующие этапы:

1) выбор  переменных задачи;

2) составление  системы ограничений; 

3) выбор целевой функции.

Переменными задачи называются величины x₁, x₂, х₃,..., x_n, которые полностью характеризуют процесс. Их обычно записывают в виде вектора X=(x₁, x₂, x₃,…., x_n)

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

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

Таким образом, общая задача математического программирования формулируется следующим образом:

найти экстремум  целевой функции задачи

Z(X) = f (x₁, x₂, x₃,…., x_n) max(min)          

Допустимым  решением задачи линейного программирования называется любой п-мерный вектор X=(x₁, x₂, x₃,…., x_n), удовлетворяющий системе ограничений и условиям неотрицательности.

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

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

В самом общем виде задачу Л. п. можно записать так. Даны ограничения типа в т. н. канонической форме:

Требуется найти неотрицательные  числа x_j (j = 1, 2, ..., n), которые минимизируют (или максимизируют) линейную форму

Неотрицательность искомых чисел записывается так: x_j ≥ 0.

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