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

⇐ ПредыдущаяСтр 3 из 9Следующая ⇒

Сразу отметим, что существенным недостатком графического метода является возможность его применения только в задачах с двумя переменными.

Экономико-математическая модель ЗЛП включает неравенства и их системы. Геометрическую интерпретацию решений неравенств, их систем и в целом ЗЛП дают следующие теоремы.

Теорема 1 [1]. Множество решений линейного неравенства является одной из полуплоскостей, на которые вся плоскость разбивается прямой, заданной соответствующим уравнением , включая эту прямую. Другая полуплоскость с той же прямой будет решением неравенства противоположного знака.

Теорема 2. Множество решений совместной системы линейных неравенств

(1)

является выпуклым многоугольником(или выпуклой многоугольной областью).

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

Теорема 3. Множество всех допустимых решений совместной системы m линейных уравнений с n переменными ( )является выпуклым многоугольником (многогранником) или выпуклой многоугольной(многогранной) областью в n-мерном пространстве.

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

Графический метод решения ЗЛП включает три этапа:

1. Определение области допустимых решений (ОДР) задачи.

2. Определение оптимальных точек (точки максимума и/или точки минимума).

3. Вычисление оптимальных значений целевой функции в оптимальных точках.

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

Вид ресурса	Запас ресурса	Количество ресурсов на единицу продукции



		-
			-
Прибыль от единицы продукции	-

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

Решение:

Оптимизационная ЭММ задачи:

Графическое решение:

1. Определение области допустимых решений (ОДР) задачи

Этот этап реализуется в соответствии с теоремами 1, 2 и замечанием к ней. При этом искомая ОДР будет находиться только в первой четверти декартовой системы координат, т.к. в модели задачи есть прямые ограничения .

Решение 1-го неравенства

Строим прямую , определив координаты двух точек (рис. 1):

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

– верно, следовательно, искомая полуплоскость содержит точку О.

Аналогично решаем все остальные неравенства.

Решение 2-го неравенства :

– верно, следовательно, искомая полуплоскость содержит точку О.

Решение 3-го неравенства :

– это прямая, параллельная оси абсцисс ОХ. Решение – полуплоскость под этой прямой.

Решение 4-го неравенства или :

– это прямая, параллельная оси ординат ОY. Решение – полуплоскость слева от этой прямой.

ОДР задачи – это находящееся в первой четверти пересечение всех полученных полуплоскостей, т.е. выпуклый шестиугольник ОАВСDE (рис. 1).

III

x₂

x₁

F_max

F=0

ОДР

Рисунок 1. Графическое решение задачи

2. Определение оптимальных точек (точки максимума и точки минимума) задачи

В соответствии с теоремой 4 оптимальные точки ЗЛП могут находиться в вершинах ОДР. Для поиска оптимальных вершин используют вектор-градиент и линию уровня целевой функции.

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

В нашей задаче вектор-градиент .

Далее строят линию уровня целевой функции.

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

В нашей задаче проведем через начало координат перпендикулярно вектору линию нулевого уровня целевой функции (т.е. линию, в каждой точке которой целевая функция равна нулю). Так как мы ищем точку максимума, то смещаем эту линию параллельно самой себе в направлении вектора до тех пор, пока не выйдем из ОДР. На выходе из области получаем точку С (6, 4) – это и есть точка максимума, т.е. точка, в которой целевая функция достигает своего максимального значения. Заметим, что координаты оптимальной точки можно найти из рисунка или строго, решив систему уравнений, задающих прямые, пересекающиеся в оптимальной точке. В нашем случае это уравненияпрямыхIи II.

3. Вычисление оптимального значения целевой функции

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

Экономическая интерпретация полученных результатов

Предприятию выгодно производить 6 единиц продукции вида и 4 единицы продукции . При таком плане производства предприятие получит максимальную прибыль 24 условных денежных единицы.

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

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

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

Особые случаи графического метода:

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

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

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

⇐ Предыдущая 1 234 5 6 7 8 9 Следующая ⇒