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

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

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

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

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

Таким образом, наибольшее значение Z достигается в вершине, через которую проходит линия уровня, соответствующая наибольшему значению Z.

Для графического решения задачи ЗЛП используют следующий алгоритм:

1. Записывают уравнения граничных прямых a_i1x₁+a_i2x₂=b_i (i = 1,…,m) и строят их на плоскости X₁OX₂ по двум точкам.

2. Отмечают полуплоскости, соответствующие ограничениям - неравенствам. Для этого берут «пробную» точку, через которую не проходит граница полуплоскости (часто берут, если прямая не проходит через начало координат, точку (0,0)), и ее координаты подставляют в соответствующее ограничение - неравенство. Если полученное неравенство верное, то искомой будет полуплоскость, содержащая «пробную» точку; в противном случае, искомой будет полуплоскость, которой данная точка не принадлежит.

3. Заштриховывают многоугольник, определяемый системой ограничений. Для этого определяют общую часть ранее отмеченных m полуплоскостей, лежащую в первой четверти (следует из условий неотрицательности переменных).

4. Строят вектор  и одну из прямых семейства  (чаще всего Z = 0). Если выбранный для построения многоугольника масштаб не позволяет построить , то вместо него строят вектор  (в случае, если длина  слишком мала для построения) или  (в случае, если длина  слишком велика для построения), где .

5. В случае необходимости параллельным переносом линию уровня следует расположить таким образом, чтобы многоугольник находился впереди линии уровня по направлению .

6. Определяют экстремальную точку, соответствующую вершине многоугольника, путем параллельного перемещения прямой Z = с в направлении вектора . Это будет наиболее удаленная вершина многоугольника, в которой линия уровня пересекается с многоугольником.

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

Замечание: Если у функции требуется найти минимальное значение, то линию уровня Z = cперемещают в направлении вектора  (или перемещают в направлении , но находят первую вершину пересечения линии уровня с многоугольником).

В зависимости от особенностей области допустимых решений и взаимного расположения области и вектора  при решении задачи линейного программирования возможны различные случаи. Рассмотрим их.

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

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

На рисунке а) функция достигает минимума в точке А, а максимума – в любой точке отрезка ВС (альтернативный оптимум); на рисунке б) максимум достигается в точке А, минимума функция не имеет; на рисунке в) функция не имеет ни минимума, ни максимума.

Пример 1

Решить графически ЗЛП:

Решение

Каждое неравенство исходной системы ограничений определяет полуплоскость. Запишем уравнения граничных прямых для этих полуплоскостей.

(1) 2х1 + 5х2 = 20				(2) 8х1 + 5х2 = 40				(3) 5х1 + 6х2 = 30
х1	0	10		х1	0	5		х1	0	6
x2	4	0		x2	8	0		x2	5	0

Построим прямые.

Каждая прямая разбивает плоскость на две полуплоскости. Для выбора полуплоскостей, определяемых каждым неравенством, подставим координаты «пробной» точки (0;0) в каждое неравенство. Получаем:

2 × 0 + 5 × 0 £ 20 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0).

8 × 0 + 5 × 0 £ 40 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0).

5 × 0 + 6 × 0 £ 30 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0).

Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: х₁,х₂³ 0. Заштрихуем полученный пятиугольник.

Построим линию уровня Z = 0: 50х₁ + 40х₂ = 0

х1	0	4
x2	0	-5

Вектор определяет направление наибольшего возрастания функции Z. Построим из начала координат вектор . Этот вектор также показывает направление наибольшего возрастания функции.

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

–

Точка А получается в результате пересечения прямых (2) и (3). Для нахождения ее координат решим систему:

8х₁ + 5х₂ = 40 ´ 5

5х₁ + 6х₂ = 30 ´ 8

_________________

-23x₂ = -40

Ответ: .

Пример 2

Пусть имеются два пункта, расстояние между которыми равно 1000 км. Между ними необходимо осуществить связь, имеющую 12 телефонных, 31 телеграфных и 18 фототелеграфных каналов с помощью кабелей двух типов, обладающих следующими характеристиками:

 

Каналы	Количество каналов для кабеля типа
	I	II
Телефонные	1	3
Телеграфные	5	4
Фототелеграфные	2	3
Стоимость 1 км кабеля (в у.е.)	12	16

Определить необходимое количество кабелей каждого типа для осуществления связи с наименьшими затратами. Решить задачу графически.

Решение

Введем переменные: x₁ – количество кабеля типа I, x₂ – количество кабеля типа II. По определению эти переменные должны быть неотрицательны. При связи, использующей x₁ кабелей I типа и x₂ кабелей II типа, могут использоваться x₁+3x₂ телефонных каналов, 5x₁+4x₂ телеграфных каналов и 2x₁+3x₂ фототелеграфных каналов. Для осуществления связи необходимо наличие не менее требуемого количества каналов. Получаем ограничения на количества имеющихся каналов:

Затраты на осуществление связи, имеющей x₁ кабелей I типа и x₂ кабелей II типа, составят: (12x₁+16x₂)×1000=12000x₁+16000x₂ условных единиц. Получаем математическую модель задачи:

Решим задачу графически. Каждое неравенство исходной системы ограничений определяет полуплоскость. Запишем уравнения граничных прямых для этих полуплоскостей.

(1) х1 + 3х2 = 12				(2) 5х1 + 4х2 = 31				(3) 2х1 + 3х2 = 18
х1	0	12		х1	0	6,2		х1	0	9
x2	4	0		x2	7,8	0		x2	6	0

Построим прямые.

Каждая прямая разбивает плоскость на две полуплоскости. Для выбора полуплоскостей, определяемых каждым неравенством, подставим координаты «пробной» точки (0;0) в каждое неравенство. Получаем:

0 + 3 × 0 ³ 12 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0).

5 × 0 + 4 × 0 ³ 31 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0).

2 × 0 + 3 × 0 ³ 18 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0).

Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: х₁,х₂³ 0. Заштрихуем полученный неограниченный четырехугольник ABCD.

Построим линию уровня Z = 0: 12000х₁ + 16000х₂ = 0

 

х1	0	4
x2	0	-3

Вектор определяет направление наибольшего возрастания функции Z. Построим из начала координат вектор . Этот вектор также показывает направление наибольшего возрастания функции.

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

–

Точка B получается в результате пересечения прямых (2) и (3). Для нахождения ее координат решим систему:

5х₁ + 4х₂ = 31´3

2х₁ + 3х₂ = 18´4

_________________

7x₁ = 21

Ответ: Для осуществления связи с наименьшими затратами необходимо 3 кабеля I типа и 4 кабеля II типа. При этом минимальные затраты составят 100 000 у.е.

⇐ Предыдущая12345678910Следующая ⇒