MET-ЧМ-Часть-2

31

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

a11x1 + a12x2 ≤ a1

Оно, как известно, определяет на плоскости одну из двух частей (полу- плоскостей), на которые прямая a11x1 + a12x2 = a1 , разбивает плоскость. При

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

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

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

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

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

Линия f(x,y) = c (c = const) при любом значении постоянной c представляет собою прямую, перпендикулярную вектору grad f . Считая c параметром, получаем семейство параллельных прямых (называемых линия- ми постоянного значения, или линиями уровня функции). Нас интересуют, в соответствии с нашей задачей, те точки допустимой обласи, которые принад- лежать линии уровня с наибольшим значением c по сравнению с его значе-

32

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

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

В качестве примера рассмотрим задачу о распределении ресурсов. Пример 7.1. Имеется 300 кг металла, 100 м2 стекла и 160 человеко-

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

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

выполняться неравенство

Таким образом, математически задачу можно сформулировать так: Найти maxZ = 10x1 + 12x2 при ограничениях

x1 ³ 0, x2 ³ 0

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

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

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

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

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

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

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

f(x1,x2 ) = 10x1 + 12x2 .

Выберем внутреннюю точку многоугольника решений M0(x1, x2 ), на- пример x1 = 10, x2 = 30 , и вычислим значение целевой функции

Z0 = f(10, 30) = 10 × 10 + 12 × 30 = 460.

Уравнение 10x1 + 12x2 = Z0 определяет на плоскости геометрическое место точек, в которых прямая f(x1,x2 ) принимает постоянное значение Z0 .

34

Меняя значение Z0 , получаем различные прямые, однако все они параллель- ны между собой, т.е. образуют семейство параллельных прямых. Эти прямые перпендикулярны вектору grad f = 10 e1 + 12 e2 (ei - координатный вектор i -ой оси). Вектор grad f указывает направление, двигаясь в котором, мы пе-

36

ЛИТЕРАТУРА

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 с.