Файл: Тихомиров В.И. Линейное программирование в организации и планировании путевого хозяйства конспект лекций для студентов специальности Стр-во ж. д., путь и путевое хоз-во учеб. пособие.pdf

Третий шаг:

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

з;?

ОСНОВНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

ИМЕТОДЫ ЕЕ РЕШЕНИЯ

§1. Основная задача линейного программирования

1.Формулировка основной задачи

Эту систему перепишем в таком виде:

х, > 0 , ха > 0, .. ., хп> 0.

Найти максимум (минимум) формы (31) при выполнении условий (32). Другими словами, среди решений системы (32) надо отыскать такое, для которого форма (31) принимает на­ ибольшее (или наименьшее значение).

2. Геометрическая интерпретация

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

Геометрическое изображение дает ясное представление о ходе решения задачи линейного программирования. Прежде чем перейти к изложению геометрической интерпретации, на-

36

до геометрически осмыслить те три звена, из которых состоит задача линейного программирования: 1) целевую функцию; 2) систему линейных ограничений; 3) требование неотрица­ тельности искомых параметров. С этой целью мы будем далее рассматривать геометрические образы, возникающие на ко­ ординатной плоскости двух переменных — Х\ и х2.

3. Геометрический смысл линейных неравенств

Как известно, линейное уравнение а1х ]+ а2х2 = Ь изобража­ ется на плоскости Ох]Х2 прямой линией I, все точки которой имеют координаты Х\ и х2, удовлетворяющие этому уравнению.

alx l + a2x2^.b, а для точек другой а\Хх+ а2х2^ Ь .

Для того чтобы узнать, с какой стороны от прямой I выра­ жение aiX'| + a2x'2 меньше 6 н с какой стороны оно больше, чем 6, достаточно в выражение а\Х]+а2х2 вместо х { и х2 под­ ставить координаты какой-нибудь точки, не лежащей на пря­ мой 1.

Пусть, например, имеем неравенство 3x1+ 2.v2^ 6 . Очевидно, сначала надо построить прямую /, соответствую­

щую уравнению 3xi + 2х2 = 6. Эта прямая легко строится по двум точкам, которые находятся из решения уравнения путем последовательного .приравнивания х, и х2 нулю.

В данном случае х, = 2, х2=3. Следовательно, / отсекает на оси Х\ отрезок ОА,= 2, и на оси х2 отрезок ОЛ2 = 3 (рис. 4).

37

Встает вопрос: с какой стороны от полученной прямой бу­

в которой лежит точка М и которая показана на рис. 4 штри­

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

Например, система неравенств:

Х\ -f-х2 7

х 1-f-Зх2 9

изображается областью, заполняющей угол АМВ (рис. 5).

38

Система неравенств

Гjc, > О

1Х2 О,

выражающих требование неотрицательности параметров за­ дачи линейного программирования, изображается первым квадрантом координатной плоскости Ох,хг (рис. 6).

Для случая любого числа линейных неравенств:

Xj j £Z2a X2 ^

®mi M "Ь ^m2Xj ^

Можно сказать, что она изображается на плоскости неко­ торой многогранной областью и во многих случаях оказывает­ ся многоугольником (рис. 7).

4. Геометрический смысл целевой функции

Рассмотрим целевую функцию:

39

прямую линию /, которая называется линией уровня функции

Z = С \ Х 1~Ь С2%2'

Ci.Vi+ C2A'2= Const.

Если эту константу будем увеличивать (или уменьшать), то прямая / будет перемещаться параллельно самой себе и в

Q

циент К = ---- 1 . Как узнать, в каком направлении надо пе-

ленный вопрос, достаточно по предыдущему правилу узнать, с какой стороны от прямой / целевая функция Z —clx I + c2x2 больше или меньше фиксированной константы.

Теперь имеется все, чтобы дать геометрическое истолко­ вание задачи линейного программирования. Итак, каждое не­ равенство

у ^ - а ^ х , - . . — О

системы (32) определяет в евклидовом л-мерном простран­ стве полупространство, состоящее из точек.'с (х,........ хп), расположенных «по одну сторону» от плоскости yt = — ап ху—

— . .. — а1пхп — 0 и на самой этой плоскости. Точки же, при­ надлежащие всем полупространствам (32), т. е. множество всех решений системы (32) как пересечение выпуклых мно­ жеств, образует некоторый выпуклый многогранник й.

Значение функции 2(д:)= с,л'1*-...+ спх„ в точке ;с'(х\,... ,х'п) можно рассматривать как уклонение точки х '(х ',,. . . , х'п) от плоскости с , х, + . .. я- спхп = 0 (а).

При этом под уклонением данной точки от этой плоскости понимается число, которое получим, подставив в левую часть уравнения (а) вместо хь ..., л+ координаты х',, . . . , х'п этой точки. Так например, уклонение точки х(2,—3, 7) от пло­ скости 2xi—х2 + Зх3 = 0 .равно 2-2—1(—3)+3-7=28.

Уклонение точки х от плоскости (а) пропорционально рас­ стоянию от точки х до этой плоскости.

Таким образом, геометрический смысл задачи линейного программирования заключается в отыскании в многогранни­ ке Q точки, которая наиболее (или наименее) уклонена от плоскости (а). В случае двухмерного пространства имеем кар­ тину, изображенную на рис. 8.

40