Геометрическая интерпретация и графическое решение ЗЛП - Экономико-математические методы

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

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

Пусть дана задача:

Z=c1x1+c2x2 max (2.6)

(2.7)

(2.8)

Дадим геометрическую интерпретацию элементов этой задачи.

Введем на плоскости декартову прямоугольную систему координат x1Ox2 и сопоставим каждой паре чисел (x1,x2) точку плоскости с координатами x1 и х2. Выясним сначала, что представляет собой множество точек, соответствующих допустимым решениям данной задачи.

Рассмотрим одно линейное неравенство.

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

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

Каждое из ограничений (2.7), (2.8) задает на плоскости х1Oх2 некоторую полуплоскость. Нас интересуют те точки плоскости, координаты которых принадлежат всем полуплоскостям. Следовательно, допустимое множество ЗЛП геометрически изображается пересечением (общей частью) полуплоскостей, определяемых отдельными ограничениями. Полуплоскость - выпуклое множество. Множество называется выпуклым, если ему вместе с двумя произвольными точками принадлежит и прямолинейный отрезок, их соединяющий. Пересечение любого числа выпуклых множеств является выпуклым множеством. Таким образом, область допустимых решений задачи (2.6) - (2.8) есть выпуклое множество. На рис.2.1 представлены возможные ситуации, когда область допустимых решений ЗЛП - выпуклый многоугольник (а), неограниченная выпуклая многоугольная область (б), единственная точка (в), прямая линия (г), луч (д), отрезок (е), пустое множество (ж).

X2 X2

б)

0 а) X1 0 X1

Х2 Х2 Х2

в) 1 д)

г)

0 Х1 0 Х1 0 Х 1

Х2 Х2

е) ж)

Х1

0 0 Х1

Рис.2.1

Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП - непустое множество, например, многоугольник ABCDE рис.2.2.

X2

B C

M

A

D

E

0 X1

Рис.2.2 N

Рис.2.2 N

Выберем произвольное значение целевой функции Z=Z0. Получим

C1x1+c2x2=Z0

Это уравнение прямой линии (рис.2.2 - прямая MN). В точках прямой MN целевая функция сохраняет одно и то же постоянное значение Z0.

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

Возникает вопрос: как установить направление возрастания (убывания) целевой функции по x1 и х2 :

(2.9)

(2.10)

Частная производная (2.9) и (2.10) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, с1 и с2 - скорости возрастания вдоль осей Oх1 и Oх2. Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции. Вектор - указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. Вектор перпендикулярен к прямым Z = const семейства

Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.

1, С учетом системы ограничений строим область допустимых решений.

Строим вектор наискорейшего возрастания целевой функции.

Проводим произвольную линию уровня Z=Z0, перпендикулярную к вектору так, чтобы она пересеклась с областью допустимых решений.

При решении задач на max перемещаем линю уровня Z=Z0 в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точки) (на рис.2.2 точка С). В случае решения задачи на min линию уровня Z=Z0 перемещают в направлении вектора - (на рис.2.2 - точка Е).

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

Пример 2.1.

Предприятию необходимо изготовить два вида продукции А и В, с использованием трех видов ресурсов R1, R2, R3 количество которых ограничено. Исходные данные задачи представлены в таблице:

Вид ресурсов

Количество ресурсов, идущих на изготовление единицы продукции

Запасы ресурсов

А

В

R1

6

6

36

R2

4

2

20

R3

4

8

40

Доходы от реализации продукции

12

15

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

Решение.

Обозначим через х1 и х2 количество единиц продукции видов А и В, планируемых к выпуску.

Известно, что доход от реализации единицы продукции А составляет 12 усл. ед. и количество этой продукции - х1. Следовательно, доход от реализации всей продукции А составит 12х1 усл. ед. Аналогично, доход от реализации всей продукции В составит 15х2 усл. ед. Учитывая, что доход от реализации продукции должен быть максимальным, целевая функция задачи будет иметь вид:

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

Смысл первого ограничения состоит в том, что фактический расход ресурса R1 на производство продукции А и В, равный 6х1+6х2 (здесь 6х1 - количество единиц ресурса R1, идущего на изготовление х1 единиц продукции A; 6х2 - количество единиц ресурса R1, идущее на изготовление х2 единиц продукции В) не должен превышать запаса этого ресурса на предприятии, равного 36 ед. Аналогичный смысл имеют 2-е и 3-е ограничения только для ресурсов R2 и R3 соответственно.

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

Таким образом, построена математическая модель нашей задачи как задачи линейного программирования:

Начнем решение задачи с построения области допустимых решений (рис.2.3)

В первую очередь отобразим в прямоугольной системе координат условия неотрицательности переменных. В двумерном пространстве уравнению соответствует прямая линия, а неравенству - полуплоскость, лежащая по одну сторону от прямой. Прямые х1=0 и х2=0 совпадают с осями координат. Полуплоскости x1>0,x2>0 лежат соответственно справа от оси Oх2 и выше оси Oх1. Множество точек, удовлетворяющих одновременно неравенствам представляют собой пересечение построенных полуплоскостей вместе с граничными прямыми и совпадают с точками первой четверти.

Теперь рассмотрим ограничения задачи. Построим по порядку прямые:

    6x1+6x2=36 или х1+х2=6 (а) 4х1+2х2=20 или 2х2+х2=10 (б) 4х1+8х2=40 или х1+2х2=10 (в)

И определяем, с какой стороны от этих прямых лежат полуплоскости, точки которых удовлетворяют строгим неравенствам:

    6x1+6x2 4x1+2x2 4x1+8x2

Для определения полуплоскости решений первого неравенства возьмем произвольную точку плоскости, не лежащую на прямой 6х1+6х2=36, например (0;0), и подставим ее координаты в неравенство.

В результате подстановки получили верное числовое неравенство 0< 36, и это означает, что начало координат лежит в полуплоскости решений первого неравенства. Сторона, в которой располагается полуплоскость от прямой, указывается штриховой.

Аналогично строим полуплоскость решений остальных неравенств.

X2

б)

a) N2

в) M

*6

в

0 N

C x1

6

D

Рис.2.3

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

Теперь нужно среди точек построенного многоугольника найти такую, в которой целевая функция Z=12x1+15x2 достигает максимального значения. Для этого построим прямую, заданную уравнением 12х1+15х2=0, которая является линией нулевого уровня функции Z.

Направление возрастания линейной функции Z=12x1+15x2 указывает вектор с началом в точке (0;0) и концом в точке М1(12,15), координаты которой равны коэффициентам при соответствующих переменных функции Z.

Для нахождения оптимального плана нужно "передвигать" линию нулевого уровня Z параллельно самой себе в направлении вектора до точки ее "последней встречи" с многоугольником, которая и является оптимальным планом задачи. В нашем случае это вершина В многоугольника OABCD - точка пересечения прямых (а) и (в). Координаты ( ) точки найдем, решив систему уравнений.

откуда х1*=2, х2*=4.

Найдем соответствующее значение целевой функции:

усл. ед.

Ответ. Для обеспечения максимального дохода от реализации готовой продукции предприятию необходимо выпустить 2 ед. продукции вида А и 4 ед. продукции вида В. При таком плане доход от реализации составит 84 усл. ед.

Геометрический метод решения ЗЛП обладает рядом достоинств: он прост, нагляден, позволяет быстро и легко получить ответ. Однако только геометрический метод решения никак не может удовлетворить ни математиков, ни экономистов. Возможны "технические" погрешности, которые неизбежно возникают при приближенном построении графиков. Второй недостаток геометрического метода заключается в том, что многие величины, имеющие четкий экономический смысл (такие, как остатки ресурсов производства, избыток питательных веществ и т. п.), не выявляются при геометрическом решении задач. Но самое главное - геометрический метод неприемлем для решения практических задач. Поэтому необходимы аналитические методы, позволяющие решать ЗЛП с любым числом переменных и выявить экономический смысл входящих в них величин.

Похожие статьи




Геометрическая интерпретация и графическое решение ЗЛП - Экономико-математические методы

Предыдущая | Следующая