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

5. Все элементы новой таблицы делятся на разрешающий элемент ars.

П р и м е р. Для таблицы

один шаг обыкновенного Жорданова исключения с разреша­ ющими 2-й строкой и 3-м столбцом приводит к следующей таблице:

и окончательно получаем таблицу

2. Геометрический смысл обыкновенного Жорданова исключения

yt= ап а, + а,-2 *2 + • •• + а1п хп = 0 (t = 1, . .. , m)

рассматривать как уравнения плоскостей («—1)-мерных, про­

ходящих через начало координат. Для каждой точки х'(х',,...,х'„) величина у,{х')=ап х \ + . . . + ciinх 'п означает взятое с опреде­

30

ленным знаком взвешенное расстояние от точки х' до плоскости- yt => 0; термин «взвешенное расстояние» означает расстояние*.

,v(.v,, . . . . хп) задается своими я уклонениями от всех коорди­

координатных плоскостей (веса равны единице).

Один шаг Жорданова исключения с разрешающим элемен­ том ars означает замену координатной плоскости л^= 0. новой плоскостью уг =0 вообще говоря, уже не ортогональной остальным координатным плоскостям, так что в наборе коор­ динат (уклонений) каждой точки пространства уклонение от старой координатной плоскости x s =0 заменяется уклонением от новой координатной плоскости уг = 0.

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

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

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

В таких случаях систему (29) записывают в виде

У1 = — <*н(— х,) — ал (— х,) — ... — ain(— х„) (30)

и составляют таблицу (табл. 4).

31,

где для удобства обозначений положено

Один шаг модифицированного Жорданова исключения с раз­ решающим элементом ars означает переход к новой таблице

(табл. 5).

Эта таблица получается из предыдущей по правилам 1—5 обыкновенного Жорданова исключения, с тем лишь измене­ нием, что правила 1 и 3 меняются ролями, а именно:

2)остальные (кроме разрешающего) элементы разрешаю­ щей строки остаются без изменения;

3)остальные элементы разрешающего столбца меняют свои знаки.

Пр и м е р 1. Рассмотрим систему:

2а , + 2х -2 — А'з + а, — 4 = О 4а , + За, — л'з + 2а , — 6 = 0 8а , 4- 5а , — За3 + 4а, — 12 = 0

За , + За2 — 2а 3 -|- 2а , — 6 = 0

32

З а п и ш е м э т у с и с т е м у в ви д е :

—X, — Хо —х-3 -X., + 1

шающий столбец, получим таблицу

Следующий шаг сделаем с разрешающей второй строкой