Казахской академии транспорта

 
 
ҚазККА Хабаршысы № 6 (73), 2011 
 
 
 
218
УДK 51:330.115 
Мусин Тамерлан Оспанович – доцент (г. Алматы, университет «Туран») 
ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ТРЁХМЕРНОЙ ЗАДАЧИ  
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 
Линейное  программирование – математический  метод,  позволяющий  описывать 
экстремум  целевой  функции,  когда  линейна  как  сама  функция,  так  и  ограничения, 
накладываемые на переменные управления [1]. 
Множество  планов  основной  задачи  линейного  программирования  (ЛП)  является 
выпуклым.  Непустое  множество  планов  называется  многогранником  решений,  а  всякая 
угловая  точка  многогранника  решений – вершиной.  Каждая  вершина  многогранника 
определяет опорный план [2]. Если задача имеет оптимальный план, то целевая функция 
достигает оптимума в одной из вершин многогранника решений. 
Если  задача  ЛП  в  стандартной  форме  содержит  не  более  двух  переменных,  то  её 
удаётся  решить  с  помощью  наиболее  простого  и  наглядного  геометрического  метода. 
Здесь областью допустимых решений (ОДР) является выпуклый многоугольник, который 
с  учётом  неотрицательности  переменных  находится  в  первом  квадрате  координатной 
плоскости 
x
1 
O
 
x
2
, а график целевой функции представляет собой прямую линию [3]. 
Рассмотрим  задачу  ЛП,  в  которой  число  переменных  равно  трём,  и  решим  её 
геометрическим  методом.  Область  допустимых  значений  представляет  собой  выпуклый 
многогранник,  а  целевая  функция  представляет  собой  плоскость.  В  этом  случае  каждое 
неравенство  геометрически  представляет  полупространство  трёхмерного  пространства, 
граничная плоскость которого 
a
i
1
·
x
1
 + 
a
i
2
·
x
2
 + 
a
i
3
·
x
3
 = 
b
i
. 
В стандартной форме задача ЛП выглядит так: 
(
)
max
3
3
2
2
1
1
→
⋅
+
⋅
+
⋅
=
x
c
x
c
x
c
Z
 
 
 
 
      (1)
 
при условиях 
⎩
⎨
⎧
=
≥
=
≤
⋅
+
⋅
+
⋅
.
3
,
1
,
0
;
,
1
,
3
3
2
2
1
1
j
x
k
i
b
x
a
x
a
x
a
j
i
i
i
i
 
 
 
          (2) 
Рассмотрим  плоскость  общего  положения.  С  учётом  тривиальных  ограничений 
0
,
0
,
0
3
2
1
≥
≥
≥
x
x
x
  рассматриваемая  плоскость  отсекает  на  осях  координат 
положительные  отрезки.  Уравнение  плоскости  в  отрезках  на  осях  координат  даёт 
наглядное  представление  о  её  положении  в  пространстве.  Для  этого  преобразуем  общее 
уравнение плоскости 
0
3
2
1
=
+
+
+
D
Cx
Bx
Ax
 в уравнение в отрезках: 
.
1
3
2
1
=
+
+
c
x
b
x
a
x
 
Таким  образом,  в  первом  октанте  пространства 
Ox
1
x
2
x
3
  образуется  треугольная 
пирамида (тетраэдр), одна вершина которой находится в начале координат, боковые грани 
лежат  на  координатных  плоскостях  и  основанием  её  является  плоскость  общего 
положения. Из последнего уравнения получаем отрезки на координатных осях. Соединив 
концы  этих  отрезков  прямыми  линиями,  получим  треугольник  следов  плоскости  общего 
положения. На рисунке 1 показаны аксонометрические проекции одной и двух пирамид. 
Заданные  ограничения  определяют  полупространства,  которые  пересекаясь, 
образуют общую часть, называемую многогранником решений. 

 
 
ҚазККА Хабаршысы № 6 (73), 2011 
 
 
 
219
 
 
 
 
 
 
 
 
 
 
   
a) 
 
 
 
      
b)   
 
 
 
c) 
Рисунок 1 – Аксонометрические проекции первого октанта трёхмерного пространства с 
плоскостями общего положения 
На  рисунке 1, 
a)  показана  ограничивающая  плоскость  общего  положения.  Эта 
плоскость  вместе  с  координатными  плоскостями  образует  треугольную  пирамиду 
(тетраэдр).  Допустимая  область  представляет  собой  пересечение  четырёх  замкнутых 
полупространств.  На  рисунке 1, 
b)  показаны  две  ограничивающие  плоскости  общего 
положения,  которые  образуют  с  координатными  плоскостями  две  пирамиды.  Причём, 
одна  пирамида  целиком  содержится  внутри  другой.  Здесь  область  допустимых  решений 
представляет  собой  только  одну  внутреннюю  пирамиду.  На  рисунке 1, 
c)  изображены 
также  две  ограничивающие  плоскости  общего  положения,  но  они  образуют  уже  две 
пересекающиеся пирамиды. Точки пересечений следов этих двух плоскостей дают концы 
ребра, являющегося линией пересечения двух граней. В этом случае допустимая область 
представляет собой пересечение пяти замкнутых полупространств, или пентаэдр. 
Для решения задачи ЛП необходимо исследовать только угловые точки (вершины) 
многогранника решений, т. е. только опорные планы. 
Рассмотрим следующую задачу. Найти максимум линейной функции 
(
)
max
20
12
15
3
2
1
→
+
+
=
x
x
x
Z
 
 
 
 
    (3) 
при условиях ограничениях 
⎪
⎪
⎩
⎪
⎪
⎨
⎧
≤
+
+
≤
+
+
≤
+
+
≤
+
+
,
144
6
3
4
,
320
16
5
8
,
84
2
3
2
,
108
4
4
3
2
1
3
2
1
3
2
1
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
 
 
 
 
          (4) 
.
0
,
0
,
0
3
2
1
≥
≥
≥
x
x
x
 
 
 
 
          (5) 
Каждое  из  условий  неотрицательности (5) задаёт  полупространство  с  граничной 
плоскостью. Это три координатные плоскости: 
x
i
 = 0, 
i = 1, 2, 3. Они образуют триэдр в 
первом октанте трёхмерного пространства. 
Линейная  функция (3) при  фиксированных  значениях 
Z  является  уравнением 
плоскости: 15
x
1
 + 12
x
2
 + 20
x
3
 = const.  Построим  многогранник  решений  системы 
ограничений (4) и плоскость линейной целевой функции (3) при 
Z = 0. 
Рассмотрим первое из неравенств (4) 
108
4
4
3
2
1
≤
+
+
x
x
x
 
 
 
 
 
       (6) 
Границей множества точек {
x
1
, 
x
2
, 
x
3
}, координаты которых удовлетворяют этому 
неравенству, служит плоскость 
x
3 
x
2 
x
1 
x
3 
x
2 
x
1 
x
3 
x
2 
x
1 
O

 
 
ҚазККА Хабаршысы № 6 (73), 2011 
 
 
 
220
108
4
4
3
2
1
=
+
+
x
x
x
   
 
 
 
       (7) 
Любая  плоскость  разделяет  трёхмерное  пространство  на  два  полупространства.  В 
частности,  плоскость (7) разделяет  на  такие  полупространства: 108
4
4
3
2
1
>
+
+
x
x
x
  и 
108
4
4
3
2
1
<
+
+
x
x
x
. 
Первому  полупространству  принадлежат  точки,  лежащие  выше  граничной 
плоскости,  а  второму – ниже.  Таким  образом,  условие (6) содержит  точки  второго 
полупространства  вместе  с  граничной  плоскостью.  Перепишем  общее  уравнение 
плоскости (7) в уравнение в отрезках: 
.
1
27
108
27
2
2
1
=
+
+
x
x
x
 
Точно также второе неравенство задаёт полупространство с граничной плоскостью 
1
42
28
42
84
2
3
2
3
2
1
3
2
1
=
+
+
⇔
=
+
+
x
x
x
x
x
x
, 
   (8) 
третье неравенство – полупространство с граничной плоскостью 
1
20
64
40
320
16
5
8
3
2
1
3
2
1
=
+
+
⇔
=
+
+
x
x
x
x
x
x
 
    
(9) 
и четвёртое неравенство – полупространство с граничной плоскостью 
1
24
48
36
144
6
3
4
3
2
1
3
2
1
=
+
+
⇔
=
+
+
x
x
x
x
x
x
. 
 
 
          (10) 
В  свою  очередь,  каждое  из  условий  неотрицательности  переменных  также  задаёт 
полупространство с граничной плоскостью 
x
i
 = 0, 
i = 1, 2, 3. 
На  рисунке 2, 
a  показан  многогранник,  ограниченный  тремя  координатными 
плоскостями и тремя плоскостями общего положения (7), (8) и (9), который представляет 
собой  пересечение  шести  замкнутых  полупространств,  или  гексаэдр.  С  учётом 
ограничивающей  плоскости (10) допустимая  область  представляет  собой  пересечение 
семи замкнутых полупространств, или гептаэдр (рисунок 2, 
b). На этом рисунке уравнения 
(7), (8), (9) и (10) изображают плоскости граней 
I, II, III и IV, соответственно. 
При  пересечении  первого  октанта  с  каждым  из  полуплоскостей (4) образуются 
четыре  пирамиды  (по  числу  нетривиальных  ограничений).  В  полученном  семействе 
пирамид каждая имеет одну общую вершину в начале координат (точка 
O) и три боковые 
грани,  лежащие  на  координатных  плоскостях.  Основаниями  этих  пирамид  служат 
вышеуказанные ограничивающие плоскости. 
В  общем  случае,  ни  одна  из  четырёх  пирамид,  гранями  которых  служат  участки 
координатных плоскостей, не содержит в себе ни одну другую, но имеет с каждой из них 
общую  часть [4]. Поэтому  в  результате  пересечения  этих  четырёх  пирамид  образуется 
выпуклый  многогранник,  имеющий  семь  граней  (участки  трёх  координатных  и  четырёх 
граничных плоскостей), т. е. гептаэдр. 
Итак,  система (4) при  условии (5) совместна  и  её  многогранник  решений 
ограничен. Тогда поставленной задаче ЛП можно дать следующую интерпретацию. Найти 
вершину многогранника решений, в которой плоскость 15
x
1
 + 12
x
2
 + 20
x
3
 = const опорная 
и целевая функция 
Z при этом достигает максимума. 

 
 
ҚазККА Хабаршысы № 6 (73), 2011 
 
 
 
221
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рисунок 2 – Многогранники решений, образованные тремя и четырьмя граничными 
плоскостями 
Значения 
Z  возрастают  в  направлении  нормального  вектора 
k
j
i
n
20
12
15
+
+
=
 
плоскости уровня, поэтому плоскость 
Z = 0 передвигаем параллельно самой себе в этом 
направлении.  При  некоторых  значениях const эта  плоскость  может  пересекаться  с 
допустимой  областью,  тем  самым  все  точки  этого  пересечения  являются  допустимыми 
решениями, при других – не иметь с ней общих точек. 
Координаты  вершин  многогранника  находим,  решая  систему  из  трёх  уравнений 
плоскостей  трёх  смежных  граней.  В  нашей  задаче  многогранник  решений  (рисунок 3) 
имеет 10 вершин (1 вершина – начало координат; 3 вершины находятся на координатных 
осях; 3 вершины – на  координатных  плоскостях  и  ещё 3 вершины – в  пространстве 
первого октанта). 
Вершины  гептаэдра,  находящиеся  на  координатных  осях,  имеют  следующие 
координаты: 
K
 
(27; 0; 0); 
L
 
(0; 28; 0); 
M
 
(0; 0; 20). Вершины, находящиеся на координатных 
плоскостях: 
A
 
(24; 12; 0); 
B
⎟
⎠
⎞
⎜
⎝
⎛
19
4
14
;
19
10
18
;
0
; 
C
 
(14; 0; 13).  Вершины,  находящиеся  в 
пространстве первого октанта: 
E
 
(18; 12; 6); 
F
 
(6; 16; 12); 
G
 
(15; 8; 10). 
На рисунке 3, 
a, b и c показаны плоскости уровня: Z = 420, Z = 510 и Z = 525. 
Все  рисунки  выполнены  в  ортогональной  диметрической  проекции,  которая  даёт 
наиболее естественное восприятие изображения объёмных тел. 
x
1 
30 
III
II
 
I
IV 
A
B 
C
K
M
L 
E 
F 
G
x
2 
30 
20 
x
1 
x
2
M
L 
K 
30 
30 
20 
A
B 
C 
D 
I 
II 
III
 
x
3
 
x
3

 
 
ҚазККА Хабаршысы № 6 (73), 2011 
 
 
 
222
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Рисунок 3 – Различные сечения многогранника решений (гептаэдра), получаемого при 
перемещении плоскости уровня параллельно самой себе 
A 
A 
M 
L 
x
1 
x
2 
x
3 
30 
40 
20 
30 
Плоскость уровня 
с отметкой Z = 525 
)
III 
II 
I 
IV 
A 
B 
C 
K 
M 
L 
E 
F 
G 
x
1 
x
2 
x
3
30 
40 
20 
30 
Плоскость уровня 
с отметкой Z = 420 
a
)
)
M 
L 
x
1 
x
2 
x
3 
30 
40 
20 
30 
Плоскость уровня 
с отметкой Z = 510 
III 
II 
I 
B 
C 
K 
G 
IV 
F 
E 
III 
II 
I 
B 
C 
K 
F 
G 
E 
IV 

 
 
ҚазККА Хабаршысы № 6 (73), 2011 
 
 
 
223
Самое  большое  число  вершин  при  четырёх  нетривиальных  ограничениях  и  трёх 
тривиальных  определяется  числом  сочетаний  без  повторений  из  семи  элементов  по  три 
35
!
3
!
4
!
7
!
3
)!
3
7
(
!
7
3
7
=
⋅
=
⋅
−
=
C
 [5]. Остальные 25 возможных  вершин  расположены  вне 
получившегося допустимого многогранника. 
Вычисленные  значения  целевой  функции  Z  в  каждой  вершине  многогранника 
приведены в таблице 1 в порядке возрастания. 
Таблица 1 – Значения целевой функции в вершинах многогранника решений 
O
 
(0; 0; 
0) 
L
 
(0; 28; 0) 
M
 
(0; 0; 
20) 
K
 
(27; 0; 
0) 
C
 
(14; 0; 
13) 
Z
O
 = 0 
Z
L
 = 336 
Z
M
 = 400 
Z
K
 = 405 
Z
C
 = 470 
A
 
(24; 12; 
0) 
B
⎟
⎠
⎞
⎜
⎝
⎛
19
4
14
;
19
10
18
;
0
G
 
(15; 8; 
10) 
F
 
(6; 16; 
12) 
E
 
(18; 12; 
6) 
Z
A
 = 504 
Z
B
 = 
19
10
506
 
Z
G
 = 521 
Z
F
 = 522 
Z
E
 = 534 
 
Из рисунка 3 видно, что значение функции цели Z можно увеличивать до тех пор, 
пока  плоскость  уровня  не  поднимется  до  вершины  E
 
(18; 12; 6).  В  этой  вершине  и 
достигается  максимальное  значение  целевой  функции:  Z = 15·18 + 12·12 + 20·6 = 534. 
Оптимальное решение задачи получилось целочисленным, хотя условие целочисленности 
было не обязательным. 
Вывод. 
Геометрическая  интерпретация  трёхмерной  задачи  ЛП  даёт  наглядное 
представление  о  процессе  её  решения.  Использование  средств  компьютерной  графики  и 
анимации в решении 3-D задачи поможет в доступном изложении графического метода и 
демонстрации  его  применимости  на  простых  примерах.  Результаты  этой  работы 
демонстрировались  на  лекциях  и  практических  занятиях  по  дисциплине  «Методы  и 
модели  управления»  для  специальности 5B070400 – Вычислительная  техника  и 
программное обеспечение. 
ЛИТЕРАТУРА 
1.  Покровский В.В. Математические методы в бизнесе и менеджменте: Учебное пособие. 
– М.: БИНОМ. Лаборатория знаний, 2008. – 110 с. 
2.  Фомин Г.П.  Математические  методы  и  модели  в  коммерческой  деятельности. – М.: 
Финансы и статистика; ИНФРА-М, – 2009. – 640 с. 
3.  Шапкин А.С., Шапкин В.А. Математические методы и модели исследования операций: 
учебник. – М.: Издательско-торговая корпорация «Дашков и K°», 2010. – 400 c. 
4.  Математические  методы  и  модели  исследования  операций:  учебник  для  студентов 
вузов,  обучающихся  по  специальности 080116 «Математические  методы  в  экономике»  и  другим 
экономическим специальностям / Под ред. проф. В. А. Колемаева. – М.: ЮНИТИ-ДАНА, 2008. –  
592 с. 
5.  Die Kleine Enzyklopädie Mathematik. – Leipzig: VEB Bibliographisches Institut Leipzig, 
1974. – 740 p. 
 
 
 
 
 
 

 
 
ҚазККА Хабаршысы № 6 (73), 2011 
 
 
 
224
УДК  621.396 
Кулымбаева Маржан Шолпанкуловна – к.ф-м.н, доцент (г. Алматы КазАТК) 
Темірханұлы Мұңал  – магистрант  (г. Алматы, КазАТК) 
ИССЛЕДОВАНИЕ МЕТОДОВ ПОВЫШЕНИЯ НАДЕЖНОСТИ 
ВОЛОКОННО-ОПТИЧЕСКИХ КАБЕЛЬНЫХ МАГИСТРАЛЕЙ 
В  статье  рассматриваются  проблемы  повышения  надежности  линейных  трактов 
систем  передачи,  которые  обусловлены  воздействием  различных  внешних  факторов, 
способных  вызвать  повреждения  линейно-кабельных  сооружений,  необходимостью 
проведения плановых и внеплановых ремонтно-восстановительных работ (РВР). 
Основным  критерием  оценки  эффективности  проведения  указанных  видов  работ 
является  время  восстановления  связи  на  участке  повреждения  и  достижение  высоких 
значений коэффициента готовности кабельной магистрали (КМ). 
В последние годы проблема надежности, включающая в себя весьма широкий круг 
вопросов,  связанных  с  проектированием,  производством  и  эксплуатацией  технических 
средств,  приобретает  все  большее  значение.  Являясь  новым  направлением,  которое 
занимается  изучением  явлений,  протекающих  во  времени  и  приводящих  к  нарушению 
нормальной  работы  тех  или  иных  изделий  или  устройств,  теория  надежности  создает 
основы  для  расчета  надежности,  изыскивает  способы  ее  повышения  при  разработке, 
изготовлении  и  эксплуатации  изделий,  определяет  способы  контроля,  а  также  методику 
сбора, учета и анализа статистических сведений, характеризующих надежность. 
Оценка надежности требуется как для действующих или проектируемых кабельных 
линий,  так  и  для  проверки  кабеля  как  промышленного  изделия.  Оценка  надежности 
действующих  или  проектируемых  кабельных  линий  решается  на  основе  сбора  и 
обработки эксплуатационных статистических данных о количестве, характере и причинах 
повреждений.  Основная  трудность,  возникающая  при  этом,  состоит  в  решении  ряда 
серьёзных 
организационных 
вопросов. 
Проверка 
надежности 
выпускаемых 
промышленностью  кабельных  изделий  является  более  сложной  и  наименее  решенной 
задачей.  Такая  проверка  может  производиться  различными  методами:  например,  путем 
лабораторных, полигонных или специальных полевых испытаний. 
Под  надежностью  изделия  или  устройства  обычно  понимается  его  способность 
сохранять  необходимое  качество  при  определенных  условиях  и  времени  эксплуатации. 
Под  безотказностью  кабельной  линии  понимается  ее  способность  работать  без  отказов 
(повреждений). 
Кабели  связи  являются  изделиями,  имеющими  способность  восстановления  при 
повреждении.  В  связи  с  широким  внедрением  новых  типов  кабелей  связи,  имеющих 
различные  конструкции  оболочек  и  изоляции  жил,  существенное  значение  приобретает 
такая  характеристика,  как  сохранность.  Под  сохранностью  кабеля  понимается  его 
свойство находиться в исправном состоянии в процессе хранения и транспортировки. 
Поставленные  в  работе  задачи  обусловили  необходимость  рассмотрения,  прежде 
всего, современных тенденций развития сетей и средств электросвязи.[1] 
Исследование  особенностей  совершенствования  сетей  и  средств  электросвязи 
позволило  выявить  три  важнейших  направления:  цифровизация,  оптиковизация  и 
компьютеризация. 
Преимущества  цифровых  систем  передачи  (ЦСП)  перед  аналоговыми  системами 
передачи  (АСП)  и  принципы  технической  реализации  ЦСП  известны  уже  несколько 
десятков  лет.  Однако  практически  цифровизация  сетей  полностью  раскрыла  свои 
преимущества  немногим  более 20 лет  назад,  в  основном  с  появлением  новой  техники 
проводной  связи – волоконно-оптических  систем  передачи  (ВОСП).  Процесс 

жүктеу/скачать 8,59 Mb.

Достарыңызбен бөлісу: