Постановка и формы задачи линейного программирования.

Задача линейного программирования – оптимизация линейной функции в области, задаваемой линейными ограничениями

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

Допустимым решением задачи называется вектор , удовлетворяющий всем ограничениям задачи

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

Теорема.Всякому решению неравенства соответствует определенное решение уравнения , в котором

И, наоборот, каждому решению уравнения (и неравенства соответствует определенное решение неравенства .

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

Для решения задачи в Excel необходимо правильно поместить математическую модель по ячейкам электронной таблицы

В ячейках, содержащих формулы чаще всего используется функция СУММПРОИЗВ

Все сведения о модели заносят в окно «Поиск решения»

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

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

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

Графический метод решения задач линейного программирования.

Если число переменных в задаче линейного программирования (ЗЛП) равно двум, а ограничениями является система неравенств, то задачу можно решать графическим методом.

Алгоритм решения ЗЛП графическим методом.

1) Записывают уравнения прямых, соответствующих ограничениям (3.3.4), и строят их на плоскости x₁ox_3.

2) Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости х₁ох₂ и подставляют ее координаты в первую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств (3.3.4).

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

4) Определяют направление возрастания (убывания) целевой функции f.

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

6) Вычисляют значения найденной точки, решая совместно уравнения, задающие прямые, на пересечении которых находится эта точка

Двойственные задачи линейного программирования.

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

Правила построения симметричной двойственной пары задач:

- Число неравенств в системе ограничений одной задачи совпадает с числом переменных другой.

-Задача на max ЦФ переходит в задачу на min и наоборот

-Знаки неравенств функциональных ограничений меняются на противоположные

-Ограничения на не отрицательность не изменяются

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

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

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

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

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