Курсовая работа: Решение задачи линейного программирования графическим методом

Основная задача линейного программирования (ОЗЛП) ставится следующим образом: Имеется ряд переменных . Требуется найти такие их неотрицательные значения, которые удовлетворяли бы системе линейных уравнений:

{1.1}

и, кроме того, обращали бы в минимум линейную целевую функцию (ЦФ)

Очевидно, случай, когда ЦФ нужно обратить не в минимум, а в максимум, легко сводится к предыдущему, если изменить знак функции и рассмотреть вместо нее функцию

Допустимым решением ОЗЛП называют любую совокупность переменных , удовлетворяющую уравнениям (1.1).

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

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

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

{1.2}

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

Введём уравнения:

{1.3}

где - добавочные переменные, которые также как и являются неотрицательными.

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

Коэффициенты в формуле (1.3) перед равны нулю.

2. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.1. Теоретическое введение

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

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

Все вышесказанное относится и к случаю, когда система ограничений (1.2) включает равенства, поскольку любое равенство

можно представить в виде системы двух неравенств (см. рис.2.1)

ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня .

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