Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 11
Текст из файла (страница 11)
Выбор хв в качестве иачаль- пых базисных переменных эквивалентен умножению системы (4) слева на матрицу (5) где свВ ' обозначено через я. 1'езультатом умножения (4) на (5) слева является уравнение где относительные оценки сг задаются посредством с;=ст — яа;=со — гд где г;=лань с аоо — свВ ')о О св — свВ 'Р( ВоЬ 1 ВгХ 'Н:1 63 2,6. геомгтгичес!»Ая инткгпгятхция а с» появляются в пулевой строке текущей таблицы. Базис является допустимым, если В 'Ь ) О, и оптимальным, если с» ~0 для всех 7. Каждая строка умножается на вектор текущих цеп л =- = (л»,..., л ) и вычитается из строки коэффициентов стоимости для того, чтобы исключить коэффициенты стоимости при базисных переменных.
Пусть имеется следу»ощая задача: минимизировать з = сх прн условиях Ах(Ь, х)0. Вводя слабые переменные, ее можно записать в виде [1, А[ =Ь. Метод исключения по строкам для матрицы А" = [1, А[ эквивалентен умножению Аа слева на В ', где  — базис (В— подматрица А): В-»Аа = [В-', В-'А[. Таким образом, матрица, полученная на мосте единичной, является обратной для текущего базиса. Более того, относительные оценки, расположенные над единичной матрицей 1, равны [ — свВ '[ или ( — л), так как ст = с»в — свВ 'ам и коэффициенты стоимости прн слабых переменных равны нулю, т.
е. с; = О, а столбцы матрицы 1 есть единичные векторы ее Заметим, что з = свхв — — сэВ 'Ь = лЬ, т. е. на кан»- дом шаге вычислений значение целевой функции равно произведению вектора текущих цен матрицы 1 на исходный вектор Ь. Например, в табл. 2.2 значение целевой функции равно 21/2 = И + + ( — О) 2 + ( — 1/2) $; в табл. 2.3 опо равно 3 = И + ( — 3) 2 + + ( — 2) 1; в табл.
2.6 равно 9 =- 37 + ( — 8) —, + ( — О) 4, в табл. 7 15 2 7 равно 3 = 37 + ( — 2) — + [ — -) — . 7 » 36» 15 2 '» 574' 2.3. Геометрическая интерпретация симплекс-метода Рассмотрим неравенство х» + хз ( Ь» при условиях х» ) О, хз» О. Область решений этого неравенства показана на рис. 2.1. Зто неравенство можно преобразовать в уравнение введением слабой переменной г». Тогда получим следующую систему: х» + + хз + 㻠—— Ь», х» ~ )О, хз «в О, г» ~ )О. Областью решений этой системы является треугольник, показанный на рис.
2.2. ГЛ. 2, СИМПЛЕКС-МЕТОД Каждой точке треугольной области рис. 2.2. соответствует точка области рис. 2.1. Соответствие можно установить, проектируя зту треугольную область на плоскость хы хз. Если придать слабой переменной 8~ постоянное значение с, то х~ и хз должны удовлетворять уравнеыпю х, + хз = — Ь| — с, которое является уравнением прямой, параллельной х~ + хз = Ьы Если слабая переменная равна нулю, то х~ -",— хз = Ьы Таким образом, зпачение Р в с.
2.2. Р и с. 2.1. слабой перомоыыой может служить мерой близости точки треугольной области к границе х~ + хз = Ь) полупространства, определяемого исходным неравенством. Рассмотрим задачу линейного програмиироваыия: минимизировать з = с~х, + сзхз +... + с„х„ при условиях Ах» Ь (А есть (т Х и)-матрица), х )~ О. Векторы х лежат в и-мерном пространстве. Вводя слабые перемеп- НЫЕ 8Ы..., 8уд И ПОЛатаы Х =- (ХЫ ..., Хд, 8Ы..., 8щ), ПОЛУ- чаем минимизировать з = с*ха (2) при условиях Азха = Ь, х* )~ О, хм гвомктенчнскля инта»и»италия где А* = (А, — 1) и с* = (см ..., с„, О,..., 0). Поскольку теперь имеется т уравнений с и + т переменными, размерность множества решений системы (2) равна и + л» вЂ” т = и. Вершиной множества решений системы (1) является точка, в которой и неравенств из т + и неравенств (1) выполняются как равенства, т.
е. и компонент вектора ха равны нулю. Эти компоненты являются лебазисными переменными. Процесс выделения переменных с нулевыми значениями эквивалентен вычеркиванию в матрице А столбцов, соответствующих этим переменным. Остальные компоненты вектора х~ получаются решением т уравнений с т неизвестными. Пусть х есть ш-мерный вектор, компоцептами которого являются базисные переменные, а  — базис; тогда х = В 'Ь.
Если х )~ О, то х — вершипа множества решений. Если х ~ О, то эта точка является пересечением п гиперплоскостей вне множества решений. Для того чтобы решить задачу (2) при помощи симплекс- метода, используется метод исключения Гаусса, в результате чего получается система, эквивалентная системе (2). Эта система имеет вид 1ха + В 'Ххк —— — В 'Ь, где  — базис, а целевая функция выражается через пебазисные переменные.
Для допустимого базиса хв ) О, так что можно рассматривать хв как слабые переменные. В пространстве небазисных переменных можно рассмотреть т неравенств В 'Мхк ( В 'Ь; точка хм = О соответствует началу координат. Симплекс-метод начинает с допустимой вершины и затеи переходит в соседнюю вершину так, чтобы значение целевой функции «улучшилось». Необходимыми условиями являются: 1) соседняя вершина должна быть допустимой; 2) значепие целевой функции в соседней вершине долин«о быть «лучше», чем в предыдущей. В пространство векторов хк возрастание от нуля одной из небааисных переменных, прн котором остальные пебазиспые переменные остаются равными пулю, соответствует движению из начала координат но одной из координатных осей. При этом, поскольку и — 1 небазисных переменных равны нулю, и — 1 ограничений задачи выполняются как равенства. Другими словами, все соседние вершины начала координат (которые соответствуют текущему решению) связаны с началом координат п — 1 ребрами выпуклого многогранника.
Возрастание от пуля некоторой небазисной перемепной может привести к тому, что эта переменная станет базисной. Для того чтобы получить в качестве решения вершину, необходимо заменить одну из базисных переменных на пебазисную. Пусть ха — яебазисная переменная и аа — соответствующий вектор-столбец. Если ха принимает значение О, то текущие базисные цеременные х принимают значения х (О) = = В '(Ь вЂ” Оаа). Когда О возрастает от нуля, значение х (О) также меняется, подчиняясь при этом требованию х (О) ) О, т.
е. 5 т. хт Гл. х симплвкс-мктод 0 меняется в границах О ~ 0 ( Ом„,. Когда 0 = 0 „, одна из компонент х (9) становится равной нулю. Геометрически увеличение 0 соответствует перемещению вдоль одной из координатных осей до тех пор, пока не будет достигнута другая вершина. Если двигаться дальше, то будет нарушено условие х; ) О. (Заметим, что х; ) О соответствует одному из неравенств В 'Ххл В 'Ь.) Поскольку целевая функция з вырви~естся теперь через слхл, условие сл ~ )О влечет за собой оптимальность таблицы.
Если для пебазисной переменной с; ( О, то возрастание от нуля атой кеременной улучшает значение целевой функции. Таким образом, в симклекс-методе всегда начинают с локальной координатной системы с началом координат, соответствующим текущему решению, и перемещаются вдоль ребра к соседней вершине, в которой значение целевой функции улучшается. После перехода в новую вершину рассматривается повая система координат с началом в атой вершине.
Если движение осуществляется согласно критерию выбора пип с~ ( О, то зто соответствует спуску по самому крутому ребру из пересекающихся в начале координат. Велнчипа изменения целевой функции за одну итерацию определяется как углом наклона (крутизной) ребра, так и длиной ребра. Более точно, величина изменения целевой функции за одну итерацию равна шш ~=~ для данного у. !Чаю .н 2.6. Зкономическая интерпретация симплекс-метода Рассмотрим задачу 3 из з 1.1: ыиннмизировать в=сх при условиях Ах =Ь, х>О.
Пусть А = (В, Х), где В является допустимым базисом. Тогда задачу (1) можно переписать следующим образом: минимизировать г = евх + слх при условиях (2) Вхв+ Мхл = Ь, хв, хл) О. Положив хл = О и хв = В 'Ъ, получим допустимое решение задачи (2). Величина х = свхв = саВ 'Ь представляет собой оценку затрат, а вектор хв = (хю..., х ) дает ненулевые интенснвпости использования процессов, соответствующих векторам а„...,а. 2.г.
зкономичкскья ицтвгпгктхция Рассмотрим наряду с первым другое химическое производство с вектором ограничений Ьв (объемом выпуска продукции), где имеется т процессов, каждый из которых представлен единичным вектором ег (г = 1,..., т). Тогда г-й процесс необходимо осуществлять с интенсивностью Ь~, поскольку только один процесс ег производит г-й вид продукта. Общая стоимость работы т процессов при использовании технологий с интенсивностями х",,..., х„* имеет следующий вид: ~ с~'хг*=~~' с,*Ь;. г г Если сз = сз В ' и Ь' = Ь, то по отношению к производству с заданным выходом продукции Ь экснлуатационпые расходы второго производства будут такими же, как и в предыдущем случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
