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

В случае двух переменных задачи ЛП могут быть решены графически. Пусть дана задача:

…

(7.5)

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

Рассмотрим сначала одно линейное неравенство с двумя переменными:

Оно, как известно, определяет на плоскости одну из двух частей (полуплоскостей), на которые прямая , разбивает плоскость. При этом соответствующая полуплоскость включает и граничную прямую (замкнутая полуплоскость). Чтобы определить, какую именно из двух замкнутых полуплоскостей определяет данное неравенство, достаточно подставить в него координаты одной какой-нибудь точки, не лежащей на граничной прямой. Если неравенство удовлетворяется, то искомая полуплоскость та, в которой лежит взятая точка, а если не удовлетворяется - то противоположная ей.

Пусть допустимая область задачи линейного программирования (7.1) оказалась непустой (многоугольник MNPO на рис. 7.1).

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

Определяем градиент функции :

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

Линия при любом значении постоянной представляет собою прямую, перпендикулярную вектору . Считая параметром, получаем семейство параллельных прямых (называемых линиями постоянного значения, или линиями уровня функции). Нас интересуют, в соответствии с нашей задачей, те точки допустимой обласи, которые принадлежать линии уровня с наибольшим значением по сравнению с его значениями для всех других линей уровня, пересекающихся с допустимой областью. Увеличение соответствует перемещению линии уровня вдоль . Следовательно, чтобы найти оптимальные точки допустимого множества задачи на максимум, нужно перемещать линии уровня в направлении вектора , начиная с какого-нибудь фиксированного положения, при котором она пересекается с допустимой областью (точка А на рис. 7.1) до тех пор, пока она не перестанет пересекаться с ней. В точке области допустимых значений, в которой функция достигает максимума, линия уровня покидает D. Поэтому, если мы найдем проекцию D на направление , то точка максимума будет проектироваться на конец полученного отрезка. Пересечение допустимой области с линией уровня в том ее положении, когда дальнейшее перемещение дает пустое пересечение, и будет множеством оптимальных точек задачи линейного программирования (на рис. 7.1 это единственная точка N).

Аналогично, при уменьшении соответствующая линия уровня покинет D в точке минимума , и эта точка проектируется на начало отрезка-проекции D на направление .

В качестве примера рассмотрим задачу о распределении ресурсов.

Пример 7.1. Имеется 300 кг металла, 100 м² стекла и 160 человеко-часов рабочего времени; из них изготавливают изделия двух наименований А и Б; стоимость одного изделия А равна 10 $, для его изготовления нужно 4 кг металла, 2 м² стекла и 2 человеко-часа рабочего времени; стоимость одного изделия Б равна 12 $, для его изготовления нужно 5 кг металла, 1 м² стекла и 3 человеко-часа рабочего времени; требуется спланировать производство так, чтоб произвести изделия с максимальной стоимостью.

Решение. Допустим, что предприятие выпускает единиц продукции вида A и единиц продукции вида B. Для этого потребуется кг единиц металла. Так как в наличии имеется всего 300 кг металла, то должно выполняться неравенство

кг

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

м²

чел.-час.

При этих условиях доход Z, получаемый предприятием, составит

(7.6)

Таким образом, математически задачу можно сформулировать так:

Найти при ограничениях

(7.7)

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

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

Вычертим эти прямые (рис 7.2).

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

Полуплоскости в пересечении дают многоугольник решений OPRF. При этом, любая точка из внутренности многоугольника удовлетворяет всем неравенствам (7.7).

Рассмотрим линейную функцию (7.6)

.

Выберем внутреннюю точку многоугольника решений , например , и вычислим значение целевой функции

.

Уравнение определяет на плоскости геометрическое место точек, в которых прямая принимает постоянное значение .Меняя значение , получаем различные прямые, однако все они параллельны между собой, т.е. образуют семейство параллельных прямых. Эти прямые перпендикулярны вектору ( - координатный вектор ‑ой оси).Вектор указывает направление, двигаясь в котором, мы переходим от меньших значений функции к большим. Теперь должно быть ясным, что оптимальное решение определяется точкой R(35, 30) (рис.7.2), и наибольшее значение функции равно

.

Итак, оптимальное решение задачи найдено: , .

Следует выпускать 35 единиц продукции вида А и 30 единиц продукции вида Б. Максимально возможный доход составит 710 $.

 

Пример 7.2. Решить задачу примера 7.1 с помощью программы Excel.

Задачи ЛП в Excel решаются с помощью надстройки «Поиск решения».

Порядок решения.

1) Ввести данные задачи в рабочий лист (рис. 7.3);

2) Ввести в ячейки B2, C2 начальный план, например 0 0

3) В ячейку D4 – формулу расчета затрат первого вида ресурсов (на ячейки плана абсолютные ссылки): =B4*$B$2+C4*$C$2

4) Скопировать формулу в ячейки D5:D6

5) В ячейку E8 – формулу расчета дохода: =B8*$B$2+C8*$C$2

 

	A	B	C	D	E
		А	Б
	план
				использовано	всего
	металл
	стекло
	чел.-час.
	стоимость
Рис. 7.3. Решение задачи ЛП с помощью программы Excel. Ввод данных.

 

6) Вызвать окно Поиск решения. В настройках указать (рис. 7.4):

Установить целевую ячейку $E$8

Равной максимальному значению

Изменяя ячейки $B$2:$C$2

 

Рис. 7.4. Настройки окна «Поиск решения» для задачи ЛП.

 

7) Нажать кнопку Добавить. Добавить ограничения на ресурсы (рис. 7.5) $D$4:$D$6<=$E4$E6

8) Нажать кнопку Добавить. Добавить условие неотрицательности переменных плана $B$2:$C$2>=0

9) Нажать кнопку OK.

Рис. 7.5. Добавление ограничения к задаче ЛП.

10) Нажать кнопку Выполнить.

11) Подтвердить сохранение найденного решения.

12) Рабочий лист изменился и содержит решение (рис. 7.6):

	A	B	C	D	E
		А	Б
	план
				использовано	всего
	металл
	стекло
	чел.-час.
	стоимость
Рис. 7.6. Решение задачи ЛП с помощью программы Excel. Результаты поиска решения.

Следует выпускать 35 единиц продукции вида А и 30 единиц продукции вида Б. Максимально возможный доход составит 710 $.

ЛИТЕРАТУРА

1. Калиткин Н.П. Численные методы. М.: Наука, 1978. - 512 с.

2. Турчак Л.И., Плотников П.В. Основы численных методов: Учебное пособие. М.: ФИЗМАТЛИТ, 2003. – 304 с.

3. Васильев А.Н. Научные вычисления в Microsoft Excel. М.: Издательский дом "Вильямс", 2004. – 512 с.

4. Ларсен У.Р. Инженерные расчеты в Excel. М.: Издательский дом "Вильямс", 2004. – 544 с.

5. Попов В.И. Численные методы расчета мостовых конструкций на ЭВМ. М.: 1981. – 78 с.

6. Ф.Г.Ахмадиев, Ф.Г.Габбасов, И.Н.Гатауллин, Р.Ф.Гиззятов, Р.И.Ибятов, Х.Г.Киямов. Методические указания к лабораторным работам по курсу «Информатика» для всех специальностей. Численные методы. Часть 1. КГАСУ, 2008г., 34с.

7. Ф.Г.Ахмадиев, Ф.Г.Габбасов, И.Н.Гатауллин, Р.Ф.Гиззятов, Р.И.Ибятов, Х.Г.Киямов. Методические указания к лабораторным работам по курсу «Информатика» для всех специальностей. Численные методы. Часть 2. КГАСУ, 2008г., 35с.