Графический способ решения линейных оптимизационных моделей

Рассмотрим линейнуюоптимизационную модель в общей форме записи:

(1.8)

(1.9)

(1.10)

(1.11)

, ; (1.12)

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

с геометрической точки зрения. Целевая функция (1.8) определяет семейство параллельных гиперплоскостей уровня цели, каждой из которых соответствует определенное значение функции , так как при изменении коэффициенты не меняются. Поскольку частные производные целевой функции по переменным : определяют координаты вектора , то вектор - это вектор градиентного направления и, следовательно, определяет направление наискорейшего возрастания целевой функции , а вектор определяет направление наискорейшего убывания. Неравенства (1.9), (1.11) определяют полупространства, а (1.10) – гиперплоскости. Полупространства и гиперплоскости являются выпуклыми множествами. Множество точек выпукло, если отрезок, соединяющий две произвольные точки этого множества, принадлежит множеству. Пересечение конечного числа выпуклых множеств – множество выпукло. Следовательно, пересечение полупространств и гиперплоскостей определяет выпуклое множество, называемое многогранным множеством или многогранником. Многогранник (ограниченный или неограниченный) – это область допустимых решений линейной оптимизационной модели. Особое значение имеют угловые (или крайние) точки области допустимых решений. Угловой (крайней) точкой выпуклого множества называется точка, если она не является внутренней ни для какого отрезка целиком принадлежащего множеству.

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

Теорема 1.1. Множество планов линейнойоптимизационной модели является выпуклым.

Доказательство (для канонической линейнойоптимизационной модели). Линейнуюоптимизационную модель можно записать и в матричном виде:

где .

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

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

что и требовалось доказать.

Введением дополнительного неравенства:

(достаточно большое)

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

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

Таким образом, линейнуюоптимизационную модель на геометрическом языке можно сформулировать следующим образом: найти точку многогранника планов, определяемого системой ограничений (1.9) – (1.11), через которую проходит гиперплоскость семейства (1.8), соответствующая наибольшему (наименьшему) значению функции .

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

(1.13)

,

через которую проходит прямая семейства

, (1.14)

соответствующая наибольшему (наименьшему) значению функции .

Прямые называются линиями уровня. Используя данную геометрическую интерпретацию, линейнуюоптимизационную модель (1.13)- (1.14) можно решить графически. Для этого:

1) нужно построить многоугольник (многоугольную область) планов, т. е. множество допустимых решений Ω с учетом системы ограничений (1.13);

2) построить вектор и одну из прямых семейства , например ;

3) параллельным перемещением прямой в направлении вектора найти точку, в которой достигает максимума (минимума);

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

При определении оптимального плана возможны случаи:

1) функция может достигать минимума в одной точке, а максимума – в любой точке отрезка;

2) максимум может достигаться в одной точке, минимума не имеет ( → – ) или минимум может достигаться в любой точке отрезка;

3) функция не имеет ни максимума ( → + ), ни минимума ( → – ).

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

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

Отметим, что графическим методом можно решать линейнуюоптимизационную модель со многими переменными. Нужно, чтобы в канонической записи задачи разность между числом неизвестных () – n и числом линейно независимых уравнений r было равно двум: n – r = 2. Преобразовав такую задачу к симметричной форме, получаем линейнуюоптимизационную модель с двумя переменными, которую и решают графически. Найдя две координаты точки оптимума, подставляют их в ограничения. Решая полученную систему уравнений, определяем остальные координаты точки оптимума.

Рисунок 1.1.

Пример 1.7. Две базы поставляют продукцию трем потребителям. Объемы запасов, потребности и затраты на перевозку единицы продукции с баз представлены в таблице 1.3:

Таблица 1.3

Базы	Потребители	Запасы
Потребности

Необходимо спланировать перевозки таким образом, чтобы затраты на них были минимальными.

Решение. Обозначим через количество единиц продукции, которые нужно перевезти с базы к потребителю . Построим распределительную таблицу 1.4:

Таблица 1.4

Базы	Потребители	Запасы
Потребности				min

Составим математическую модель. Определим план перевозок таким образом, чтобы минимизировать стоимость перевозок:

При этом должны выполняться следующие ограничения:

1) продукция с баз должна быть вывезена:

;

;

2) заявки потребителей должны быть удовлетворены полностью:

;

;

;

3) должны быть исключены обратные перевозки:

, i = 1, 2; j = 1, 2, 3.

Это модель закрытой транспортной задачи. Так как

nm – (n + m – 1) = 2 · 3 – (2 + 3 – 1) = 2,

то задача может быть решена графически.

Выберем две свободные неизвестные, например, и . Выразим все другие переменные через свободные, получим:

; ; ;

.

Подставим значения , , , выраженные через свободные переменные, в целевую функцию:

.

Из требования неотрицательности всех переменных ( ≥ 0) имеем:

.

Целевая функция достигает минимума, если функция: достигает максимума. Найдем . Для этого выполним следующие действия:

1) построим область Ω – множество допустимых решений, удовлетворяющих системе ограничений:

.

Для построения области строим на плоскости граничные прямые:

соответствующие данным неравенствам (см. рисунок 1.2).

25

20

10

0 10 15 20

Рисунок 1.2.

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

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

2) построим вектор , = (2, 1);

3) проведем линию уровня цели перпендикулярно вектору ;

4) так как ищется максимум , то, прямую = 0, будем перемещать в направлении вектора , так чтобы она заняла крайнее положение в области Ω;

5) решаем систему из уравнений прямых, пересекающихся в точке оптимума:

6) находим координаты точки оптимума:

.

7) далее находим значения остальных неизвестных :

.

Тогда минимум целевой функции: = 310 – (2·15 + 5) = 275.

Оптимальный план перевозок записывается в виде таблицы 1.5:

Таблица 1.5

				Запасы
Потребность

или матрицы

.