Общая форма записи модели задачи ЛП

Целевая функция (ЦФ)

,

при ограничениях

Допустимое решение– это совокупность чисел (план) , удовлетворяющих ограничениям задачи.

Оптимальное решение – это план, при котором целевая функция (ЦФ) принимает свое максимальное (минимальное) значение.

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

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

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

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

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

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

Транспортная задача.

Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по-разному организовать “прикрепление” потребителей к складам, т.е. установить, с какого склада какому потребителю и сколько вести. Кроме того, известна стоимость доставки единицы товара с определенного склада определенному потребителю. Требуется минимизировать издержки по перевозке.

;

Целевая функция (ЦФ) представляет собой общие транспортные расходы на осуществление всех перевозок в целом. Первая группа ограничений указывает, что запас продукции в любом пункте отправления должен быть равен суммарному объему перевозок продукции из этого пункта. Вторая группа ограничений указывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворить спрос на продукцию в этом пункте. Наглядной формой представления модели транспортной задачи (ТЗ) является транспортная матрица.