Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. пособие

Подождите немного. Документ загружается.

ГЛАВА 3. ЛИНЕЙНЫЕ ЗАДАЧИ

оптимального распределения имеющихся ресурсов (или денег, или

материалов, или времени) для достижения определенной цели (наи-

большего дохода или наименьших издержек).

Пусть, например, отдел маркетинга на основе анализа рынка пре-

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

продуктов.

Ясно, что каждый из новых продуктов будет вносить в доход фир-

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

имеющихся в наличии ресурсов. Кроме того, следует учесть, что

для одновременного производства всех новых продуктов наличных

ресурсов, как правило, оказывается недостаточно.

У руководства фирмы возникает естественный вопрос: какие из

этих новых видов продуктов и в каком количестве следует произво-

дить?

Для подготовки содержательного ответа на вопрос — производ-

ство какого количества новых продуктов способно принести наи-

больший доход (в рамках имеющихся ресурсов) — во многих слу-

чаях может быть использовано линейное программирование.

Теперь о названии линейное программирование. Программирова-

ние в данном термине имеет смысл планирования. Линейное же озна-

чает, что ищется экстремум линейной целевой функции при линей-

ных ограничениях (линейных уравнениях и линейных неравенствах).

Тем самым линейное программирование имеет весьма мало обще-

го с программированием, используемым в computer science. Вместе

с тем вычислительные средства играют существенную роль в по-

вышении эффективности его приложений. Дело в том, что многие

реальные задачи линейного программирования содержат сотни неиз-

вестных, уравнений и неравенств, и их невозможно успешно решать

без современных быстродействующих компьютеров.

Укажем несколько общих ситуаций, в которых линейное програм-

мирование применяется часто и эффективно:

задачи о составлении смеси, цель которых заключается в выборе

наиболее экономичной смеси ингредиентов (руды, нефти, пищевых

продуктов и др.) при учете ограничений на физический или хими-

ческий состав смеси и на наличие необходимых материалов;

задачи производства, целью которых является подбор наиболее

выгодной производственной программы выпуска одного или несколь-

ких видов продукции при использовании некоторого числа ограни-

ченных источников сырья;

ГЛАВА 3. ЛИНЕЙНЫЕ ЗАДАЧИ

задачи распределения, цель которых состоит в том, чтобы орга-

низовать доставку материалов от некоторого числа источников к

некоторому числу потребителей так, чтобы оказались минимальны-

ми либо расходы по этой доставке, либо время, затрачиваемое на

нее, либо некоторая комбинация того и другого. В простейшем виде

это задача о перевозках (транспортная задача).

Рассматриваются и комбинированные задачи (например, в слу-

чае, когда какой-то товар производится в разных местах, задачи

производства и распределения объединяют в единую модель).

Наиболее распространенным методом решения задач линейного

программирования является так называемый

сгшплегсс-метод,

а наи-

более эффективным из известных — метод эллипсоидов.

В простейшем случае, когда число переменных равно двум, удо-

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

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

ет получать ответ без привлечения дополнительных средств и, что

особенно важно, раскрывает суть идей, лежащих в основе других

методов.

Другой важный класс линейных задач образуют задачи, своди-

мые к системам линейных уравнений, — это линейные задачи, огра-

ничения в которых имеют характер равенств.

Одним из наиболее простых и одновременно эффективных подхо-

дов к решению линейных систем является метод последовательного

исключения неизвестной.

3.1. Координаты

В этом разделе мы напомним некоторые геометрические факты, об-

суждая их и развивая в той мере, в какой они понадобятся нам чуть

позже.

Известно, что систематическое изложение метода координат, раз-

нообразные применения которого столь широки и естественны

сейчас, было предложено Рене Декартом (Descartes) еще в XVII в.

Основной идеей этого метода является налаживание тесных связей

между геометрическими объектами и числами. Напомним, как это

делается.

3.1. КООРДИНАТЫ

3.1.1. Декартовы координаты

Рассмотрим прямую. Отметим на ней точку (точка О) и укажем

стрелкой одно из двух возможных направлений перемещения вдоль

этой прямой (рис. 1). При помощи выбранного масштабного отрезка

(единицы измерения) мы можем поставить в соответствие каждой

точке этой прямой число, равное расстоянию от нее до точки О,

взятому со знаком плюс или минус в зависимости от того, с какой

стороны от точки О эта точка лежит (справа или слева). Например,

точке

М\

на рис. 2 соответствует число, равное 2, а точке

— чи-

сло, равное —3. Эти числа суть координаты рассматриваемых точек.

Рис. 1

Рис. 2

Рис. 3

Так вводится декартова координатная система на прямой (рис. 3).

Обозначение: М{х).

Предложенный Декартом подход позволяет описывать при помо-

щи чисел точки не только на прямой, но и на плоскости и даже в

пространстве.

Проведем на плоскости через фиксированную точку О две вза-

имно перпендикулярные прямые, укажем на каждой из них стрел-

кой одно из возможных направлений и выберем единый масштабный

отрезок (рис. 4). По правилу, указанному на рис. 5, поставим в со-

ответствие произвольной точке М упорядоченную пару чисел. Это

декартовы координаты точки М — абсцисса х и ордината у. При

ГЛАВА 3. ЛИНЕЙНЫЕ ЗАДАЧИ

этом говорят, что на плоскости введена декартова система коорди-

нат Оху, а оси Ох и Оу называют координатными осями.

Обозначение: М(х,у).

Декартова система координат Oxyz в пространстве вводится

сходным образом: каждой точке пространства по правилу, указан-

ному на рис. 6, приписывается упорядоченная тройка чисел — ее

координат; координата z называется аппликатой. Координатные оси

Ох, Оу и Oz взаимно перпендикулярны.

Обозначение: M(x,y,z).

Пример 1. Основой математического описания цвета является

экспериментально установленный факт, что любой цвет при некото-

рых строго стандартизированных условиях его рассмотрения мож-

но представить в виде смеси (суммы)

определенных

количеств трех

основных цветов красного (R), зеленого

(G)

и синего (В). То-

гда три числа,

описывающие

данный цвет, являются количествами

основных цветов в смеси, цвет которой зрительно неотличим от дан-

ного цвета. Например, цвет (С) создается смесью количества

цвета

R, количества g цвета G и количества Ь цвета В (рис. 7). Числа

г,

<?,

Ь — цветовые координаты данного цвета С — C(r,g,b). Так возни-

кает естественная математическая модель совокупности цветов —

трехмерное пространство, элементы которого суть разнообразные

цвета, трехмерное пространство цветов.

3.1.2. Прямые. Полуплоскости

Задание точки посредством упорядоченного набора чисел позволяет

описывать при помощи формул различные множества (это дает воз-

можность добавить к геометрическим рассуждениям действенный

3.1. КООРДИНАТЫ

аналитический аппарат) и, наоборот, привлекать к исследованию

разнообразных формул наглядные геометрические соображения.

Пример 2. Введем на плоскости координатную систему Оху и

рассмотрим множество точек

М,

координаты х и у которых связаны

равенством

Зх + 4у = 6.

Это прямая, пересекающая координатные оси Ох и Оу в точках

Р(2,0) и

Q(0,

3/2) соответственно

(рис.

8).

Вообще прямой на плоскости изображается любое соотношение

вида

Ах +

= С,

(1)

где х и у — переменные величины,

А, В

С — постоянные числа,

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

В самом деле, если В

0, то, перенося слагаемое, содержащее

переменную х, в правую часть, после деления на В получаем

у = кх + b

— уравнение прямой, записанное в более привычной для читателя

форме (рис. 9) (здесь к =

—А/В,

Ь =

С/В).

Однако формула (1) является более общей — она включает в

себя еще и вертикальные прямые: при В = 0 после деления на А

получаем

х = a

(здесь а =

С/А)

(рис. 10).

Замечание 1. Если обе части равенства умножить на одно и то же не

равное нулю число, то геометрический носитель этой связи (прямая)

останется прежним.

ГЛАВА 3. ЛИНЕЙНЫЕ ЗАДАЧИ

описывают одну и ту же прямую (первое из этих равенств получа-

ется из второго после умножения обеих его частей на 50).

Замечание 2. Соотношение (1) принято называть линейным в отли-

чие, например, от известного квадратичного у = х

При помощи формул можно описывать и другие множества.

Пример 3. Множество точек

М(х,

у) плоскости, у которых нео-

трицательна абсцисса х, описывается неравенством

— это правая полуплоскость (рис. 11). Множество точек

М(х,у),

которых неотрицательна ордината у,

— это верхняя полуплоскость (рис. 12).

На рис. 13 множество точек М(х,у), обе координаты которых не-

отрицательны, помечено двойной штриховкой:

0, у ^ 0.

Пример

Попробуем теперь изобразить все точки плоскости,

координаты х и у которых удовлетворяют неравенству

\Ъх +

4у

^ 14.

3.1. КООРДИНАТЫ

Начнем с уравнения

Оно описывает прямую

£,

которую легко можно построить по точ-

кам ее пересечения с осью Ох — точке

.4(14/15,0)

и с осью Оу —

точке

В(0,7/2)

(рис. 14).

Ясно, что если точка

М*(х*,у*)

не лежит на этой прямой, то

15а:*

Ау*

ф 14.

Это означает, что есть две возможности:

либо

15ж*

4у*

< 14,

либо

15ж*

4у*

> 14.

Рис.

Рис. 16

Но всякая прямая делит плоскость на две полуплоскости. Поэто-

му если координаты точек одной из полуплоскостей, порожденных

прямой

£,

удовлетворяют неравенству

15х

4у

< 14,

то для координат точек другой полуплоскости выполняется нера-

венство

Зак.

7492

ГЛАВА 3. ЛИНЕЙНЫЕ ЗАДАЧИ

Это означает, что каждому из неравенств

15х

+ Ау < 14

15ж

Ау

> 14

соответствует своя полуплоскость (рис. 15).

Теперь важно определить, какую именно из этих двух полуплос-

костей описывает заданное неравенство.

Чтобы найти полуплоскость, описываемую неравенством

15ж

14,

проще всего поступить следующим образом: взять начальную точку

0(0,0) и подставить ее (нулевые) координаты в левую часть этого

неравенства. Имеем:

0< 14.

Это означает, что начальная точка О лежит в искомой полуплоско-

сти (рис. 16).

Таким образом, геометрическое описание неравенства

1Ъх

получено.

Пользуясь аналогичными рассуждениями, можно описать на пло-

скости множество точек, координаты которых удовлетворяют нера-

венству

150ж

+ 200у

300 :

1) находим точки пересечения прямой

150х

2Щ

= 300

•

с координатными осями — это С(2,0) и

D(0,3/2)

(см. пример 2),

2) строим эту прямую (рис. 17),

3) находим, в какой из полуплоскостей, определяемых построен-

ной прямой, лежит начальная точка О(0, 0); так как

150

•

0 + 200

•

0 = 0 < 300,

то искомая полуплоскость точку О не содержит (рис. 18).

3.1. КООРДИНАТЫ

Подведем некоторые итоги.

На координатной плоскости Оху линейное уравнение вида

Ах +

= С

изображается прямой, а линейное неравенство

Ах +

С,

или

— полуплоскостью.

Для того чтобы узнать, какую именно полуплоскость описывает

заданное неравенство, для определенности

Ах

+ By ^ С,

необходимо сначала построить соответствующую прямую

Ах +

= С

(по точкам ее пересечения с координатными осями), а затем опре-

делить, по какую сторону от этой прямой лежит начальная точка

0(0,0). Если нулевые координаты удовлетворяют заданному нера-

венству, то полуплоскость, в которой лежит точка О(0, 0), является

искомой; если же не удовлетворяют, то искомой полуплоскостью бу-

дет та, которая точку О(0, 0) не содержит.

3.1.3. Пересечения прямых и полуплоскостей

Две произвольные прямые на плоскости могут пересекаться, быть

параллельными или совпадать.

ГЛАВА 3.

ЛИНЕЙНЫЕ

ЗАДАЧИ

Если на плоскости введена координатная система

Оху,

то пря-

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

ры прямых, заданных уравнениями, совсем не сложно определить,

каково их взаимное расположение, только по виду этих уравнений.

Пример 5. Непосредственным построением легко убедиться в

том, что прямые, заданные уравнениями

пересекаются (рис. 19а), прямые, заданные уравнениями

параллельны (рис. 195), а прямые, описываемые уравнениями

совпадают (рис. 19в).

Однако вглядитесь в эти уравнения чуть внимательнее, и вы по-

лучите те же ответы, не прибегая ни к построениям, ни к вычисле-

ниям.