Общая постановка задачи линейного программирования

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

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

В этом случае оптимальное решение будет находиться методами линейного программирования.

Термин “линейное программирование” впервые появился в 1951г. в работах американских ученых Дж. Данцига и Т. Кумпанса, а первые работы по линейному программированию были выполнены в конце 30-х годов в Ленинградском государственном университете Л. В. Канторовичем. Употребление слова “программирование” связано с тем, что при решении задач находят такой набор переменных, который является программой (планом) при выполнении поставленной задачи.

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

Найти такие неотрицательные значения х₁ , х₂ , х₃ ,..., х_n, которые обеспечивают оптимальное (минимальное или максимальное) значение линейной функции (целевой функции)

F= +с

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

(2.2)

Коэффициенты , с- известные постоянные, характеризующие условия задачи (параметры условия).

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

Задача линейного программирования может не иметь решений в следующих случаях:

1) если система ограничений несовместна, в том числе, если только не выполняется условие неотрицательности переменных x_i;

2) система ограничений совместна, есть допустимые решения, но среди них нет оптимального решения.

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

Пример. Приведите к каноническому виду систему ограничений (2.1) из задачи о производстве столов и стульев.

Введем неотрицательные переменные х₄ , х₅ , х₆.

Перепишем систему неравенств в виде:

Так как левая часть первого неравенства меньше правой, то, добавив к ней положительную переменную х ₄, можем вместо неравенства записать уравнение: 2 х ₁ +0,5 х ₂+ х ₄ = 80. Переменная х ₄ играет роль неизрасходованных часов рабочего времени. Аналогично, так как левая часть второго неравенства больше правой, то, отняв он нее положительную переменную х₅, можем вместо неравенства записать уравнение: х ₂ – 4 х ₁– х ₅ = 0. Переменная х₅ показывает, на сколько количество проданных стульев больше учетверенного количества столов и т.д.

Система (2.1) в каноническом виде имеет вид:

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

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

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

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

Каждое значение целевой функции F ₀ = c ₁ x ₁+ c ₂ x ₂ задает на плоскости прямую, называемую опорной. Все эти прямые параллельны между собой и перпендикулярны вектору, называемому градиентом функции и имеющему координаты:

grad F = (c ₁; c ₂).

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

Это рассуждение иллюстрирует теорему линейного программирования: