Главная | Обратная связь | Поможем написать вашу работу!

Линейное программирование

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

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

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

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

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

Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта. Эта модель выражает закономерности экономического процесса в абстрактном виде с помощью математических соотношений.

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

Процедура экономико-математического моделирования заменяет дорогостоящие и трудоемкие натуральные эксперименты достаточно быстрыми и незатруднительными расчетами.

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

(1.1)

на некотором множестве , где удовлетворяют системе ограничений:

(1.2)

и, возможно, ограничениям:

. (1.3)

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

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

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

Задачу линейного программирования, записанную в форме (1.1) – (1.3), называют общей задачей линейного программирования.

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

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

Оптимальным решением или оптимальным планом ЗЛП называется решение системы ограничений (1.2), удовлетворяющее условиям (1.3), при котором линейная функция (1.1) принимает оптимальное (максимальное или минимальное значение).

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

Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение (план) , при котором линейная функция

(1.4)

принимает максимальное или минимальное значение при ограничениях:

, , (1.5)

, , (1.6)

– целые числа. (1.7)