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

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

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

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

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

Действительно, пусть

при линейных ограничениях

Необходимым условием экстремума является равенство нулю частных производных

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

,

отсюда

Так как все коэффициенты линейной функции не могут быть равны нулю, то внутри области, образованной системой ограничений, экстремальные точки не существуют. Они могут быть только на границе области.

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

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

Модель задачи линейного программирования может быть записана в одной из приведенных ниже форм:

1. Общая или произвольная форма записи

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

– произвольные .

2. Симметричная или стандартная форма записи

а)

б)

3. Каноническая или основная форма записи

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

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

Так, при необходимости задачу минимизации можно заменить задачей максимизацией и наоборот:

.

Неравенство типа путем умножения левых и правых частей на -1 можно превратить в неравенство типа и наоборот.

Ограничения-неравенства типа

преобразуются в ограничения-равенства путем прибавления (вычитания) к левым частям дополнительных (балансовых) неотрицательных переменных :

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

.

Далее рассмотрим геометрическую интерпретацию ЗЛП применительно к двум переменным.

Найти оптимальный план , доставляющий

(2)

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

(3)

(4)

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

Каждые из неравенств (3) определяет на координатной плоскости некоторую полуплоскость, а система неравенств (3), (4) в случае ее совместности – их пересечение.

Это множество будет выпуклым. Оно может представлять собой следующие геометрические конструкции (Рисунок 31).

Перейдем далее к геометрической интерпретации целевой функции (2).

Уравнение при фиксированном значении определяет на плоскости прямую линию

.

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

Вектор с компонентами из коэффициентов при и перпендикулярен к каждой из линий уровня.

а)		выпуклый многоугольник (число вершин равно m);
б)		неограниченная выпуклая многоугольная область;
в)		отрезок прямой;
г)		луч;
д)		точка;
е)		пустое множество.

Рисунок 31. Геометрическая интерпретация ЗЛП

Вектор показывает направление возрастания (убывания) целевой функции.

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

Через обозначаются затраты на перевозку единицы продукта из i -го пункта поставщика в j -й пункт потребителя (Рисунок 32).

Через обозначается количество продукта, перевозимого из i -го пункта поставщика в j -й пункт потребителя.

Необходимо определить такие объемы перевозок продукта для всех маршрутов , при которых суммарные транспортные издержки будут минимальными.

			Потребители
Поставщики

Рисунок 32. Матрица затрат на перевозку

Формальная запись задачи имеет вид:

при условиях

Дана целевая функция и ограничения:

.

Решение:

1. Строятся на плоскости х ₁0 х ₂ граничные прямые по следующим уравнениям

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

3. Строится вектор , определяющий направление возрастания (убывания) целевой функции.

4. Перпендикулярно к вектору проводится линия уровня (Рисунок 33).

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

6. Определяются точки максимума и минимума целевой функции:
точка В определяется системой уравнений

аналогично для точки А имеем

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