Меню Рубрики

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

Тема: Построение экономической модели с использованием симплекс-метода .

Моделирование как метод научного познания.

Моделирование в научных исследованиях стало применяться еще в
глубокой древности и постепенно захватывало все новые области научных
знаний : техническое конструирование , строительство и архитектуру ,
астрономию , физику , химию , биологию и , наконец , общественные науки
. Большие успехи и признание практически во всех отраслях современной
науки принес методу моделирования ХХ в . Однако методология
моделирования долгое время развивалась независимо отдельными науками .
Отсутствовала единая система понятий, единая терминология . Лишь
постепенно стала осознаваться роль моделирования как универсального
метода научного познания .

Термин «модель» широко используется в различных сферах
человеческой деятельности и имеет множество смысловых значений .
Рассмотрим только такие «модели», которые являются инструментами
получения знаний .

Модель — это такой материальный или мысленно представляемый объект,
который в процессе исследования замещает объект-оригинал так, что
его непосредственное изучение дает новые знания об объекте-оригинале .

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

Главная особенность моделирования в том , что это метод
опосредованного познания с помощью объектов-заместителей . Модель
выступает как своеобразный инструмент познания , который исследователь
ставит между собой и объектом и с помощью которого изучает интересующий
его объект . Именно эта особенность метода моделирования определяет
специфические формы использования абстракций , аналогий , гипотез ,
других категорий и методов познания .

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

Моделирование — циклический процесс . Это означает , что за первым
четырехэтапным циклом может последовать второй , третий и т.д. При
этом знания об исследуемом объекте расширяются и точняются, а исходная
модель постепенно совершенствуется . Недостатки , обнаруженные после
первого цикла моделирования , бусловленные малым знанием объекта и
ошибками в построении модели , можно исправить в последующих циклах .
В методологии моделирования , таким образом , заложены большие
возможности саморазвития .

Фирма , производящая некоторую продукцию осуществляет её
рекламу двумя способами через радиосеть и через телевидение . Стоимость
рекламы на радио обходится фирме в 5 $ , а стоимость телерекламы — в
100$ за минуту .

Фирма готова тратить на рекламу по 1000 $ в месяц . Так же
известно , что фирма готова рекламировать свою продукцию по радио по
крайней мере в 2 раза чаще , чем по телевидению .

Опыт предыдущих лет показал , что телереклама приносит в 25
раз больший сбыт продукции нежели радиореклама .

Задача заключается в правильном распределении финансовых
средств фирмы .

X1 — время потраченное на радиорекламу .

X2 — время потраченное на телерекламу .

Z — искомая целевая функция , оражающая максимальный сбыт от 2-ух видов
рекламы .

Max Z = X1 + 25X2 ;

Использование графического способа удобно только при решении задач ЛП с
двумя переменными . При большем числе переменных необходимо применение
алгебраического аппарата . В данной главе рассматривается общий метод
решения задач ЛП , называемый симплекс-методом .

Информация , которую можно получить с помощью
симплекс-метода , не ограничивается лишь оптимальными значениями
переменных . Симплекс-метод фактически позволяет дать экономическую
интерепритацию полученного решения и провести анализ модели на
чувствительность .

Процесс решения задачи линейного программирования носит
итерационный характер : однотипные вычислительные процедуры в
определенной последовательности повторяются до тех пор , пока не будет
получено оптимальное решение . Процедуры , реализуемые в рамках
симплекс-метода , требуют применения вычислительных машин — мощного
средства решения задач линейного программирования .

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

В гл 2 было показано , что правая и левая части ограничений
линейной модели могут быть связаны знаками . Кроме того ,
переменные , фигурирующие в задачах ЛП , могут быть неотрицательными или
не иметь ограничения в знаке . Для построения общего метода решения
задач ЛП соответствующие модели должны быть представлены в некоторой
форме , которую назовем стандатрной формой линейных оптимизационных
моделей . При стандартной форме линейной модели

Все ограничения записываются в виде равенств с неотрицательной правой
частью ;

Значения всех переменных модели неотрицательны ;

Целевая функция подлежит максимизации или минимизации .

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

Исходное ограничение , записанное в виде неравенства типа ) ,

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

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

5X1 + 100X2 0 , в результате чего исходное
неравенство обращается в равенство

5X1 + 100X2 + S1 = 1000 , S1 => 0

Если исходное ограничение определяет расход некоторого ресурса ,
переменную S1 следует интерпретировать как остаток , или
неиспользованную часть , данного ресурса .

Рассмотрим исходное ограничение другого типа :

Так как левая часть этого ограничения не может быть меньше правой , для
обращения исходного неравенства в равенство вычтем из его левой части
избыточную переменную S2 > 0 . В результате получим

X1 — 2X2 — S2 = 0 , S2 => 0

Правую часть равенства всегда можно сделать неотрицательной , умножая
оби части на -1 .

Например равенство X1 — 2X2 — S2 = 0 эквивалентно равенству — X1 + 2X2
+ S2 = 0

Знак неравенства изменяется на противоположный при умножении обеих
частей на -1 .

Например можно вместо 2 — 4 , неравенство X1 —
2X2 0

Любую переменную Yi , не имеющую ограничение в знаке , можно
представить как разность двух неотрицательных переменных :

Такую подстановку следует использовать во всех ограничениях , которые
содержат исходную переменную Yi , а также в выражении для целевой
функции .

Обычно находят решение задачи ЛП , в котором фигурируют переменные
Yi’ и Yi’’ , а затем с помощью обратной подстановки определяют величину
Yi . Важная особенность переменных Yi’ и Yi’’ состоит в том , что при
любом допустимом решении только одна из этих переменных может принимать
положительное значение , т.е. если Yi’>0 , то Yi’’=0, и наоборот . Это
позволяет рассматривать Yi’ как остаточную переменную , а Yi’’ — как
избыточную переменную , причем лишь одна из этих переменных может
принимать положительное значение . Указанная закономерность широко
используется в целевом программировании и фактически является
предпосылкой для использования соответсвующих преобразований в задаче
2.30

Целевая функция линейной оптимизационной модели , представлена в
стандартной форме , может подлежать как максимизации , так и минимизации
. В некоторых случаях оказывается полезным изменить исходную целевую
функцию .

Максимизация некоторой функции эквивалентна минимизации той же
функции , взятой с противоположным знаком , и наоборот . Например
максимизация функции

эквивалентна минимизации функции

Эквивалентность означает , что при одной и той же совокупности
ограничений оптимальные значения X1 , X2 , в обоих случаях будут
одинаковы . Отличие заключается только в том , что при одинаковых
числовых значениях целевых функций их знаки будут противоположны .

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

Общую идею симплекс-метода можно проиллюстрировать на
примере модели , посроенной для нашей задачи . Пространство решений
этой задачи представим на рис. 1 . Исходной точкой алгоритма является
начало координат ( точка А на рис. 1 ) . Решение , соответствующее этой
точке , обычно называют начальным решением . От исходной точки
осуществляется переход к некоторой смежной угловой точке .

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

Каждая последующая угловая точка должна быть смежной с предыдущей . Этот
переход осуществляется по границам ( ребрам ) пространства решений .

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

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

Читайте также:  Коррекция зрения у работающих на компьютерах

Определим пространство решений и угловые точки агебраически . Требуемые
соотнощшения устанавливаются из указанного в таблице соответствия
геометрических и алгебраических определений .

Геометрическое определение Алгебраическое определение (
симплекс метод )

Пространство решений Ограничения модели стандартной формы

Угловые точки Базисное решение задачи в стандартной форме

Представление пространства решений стандартной задачи линейного
программирования .

Линейная модель , построенная для нашей задачи и приведенная к
стандартной форме , имеет следующий вид :

Z = X1 + 25X2 + 0S1 + 0S2

5X1 + 100X2 + S1 = 1000

X1=>0 , X2=>0 , S1=>0 , S2=>0

Каждую точку пространства решений данной задачи , представленную на
рис.1 , можно определить с помощью переменных X1 , X2 , S1 и S2 ,
фигурирующими в модели стандартной формы. При S1 = 0 и S2 = 0
ограничения модели эквивалентны равенствам , которые представляются
соответствующими ребрами пространства решений . Увеличение переменных S1
и S2 будет соответствовать смещению допустимых точек с границ
пространства решений в его внутреннюю область. Переменные X1 , X2 , S1 и
S2 , ассоциированные с экстремальными точками А , В , и С можно
упорядочить , исходя из того , какое значение ( нулевое или ненулевое )
имеет данная переменная в экстремальной точке .

Экстремальная точка Нулевые переменные Ненулевые переменные

А S2 , X2 S1 , X1

В S1 , X2 S2 , X1

С S1 , S2 X1 , X2

Анализируя таблицу , легко заметить две закономерности:

1. Стандартная модель содержит два уравнения и четыре

неизвестных , поэтому в каждой из экстремальных точек две ( = 4 — 2 )
переменные должны иметь нулевые значения .

2. Смежные экстремальные точки отличаются только одной пе-

ременной в каждой группе ( нулевых и ненулевых переменных ) ,

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

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

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

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

В этом состоит сущность свойства однозначности экстремальных

точек . На рис. 1 каждой неэкстремальной точке соответствует

не более одной нулевой переменной . Так , любая точка внутренней

области пространства решений вообще не имеет ни одной нулевой

переменной, а любая неэкстремальная точка , лежащая на границе ,

всегда имеет лишь одну нулевую переменную .

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

делить их алгебраическим методом. Будем считать , что линейная

модель стандартной формы содержит т уравнений и п ( т не могут рассматриваться

как ограничения на ресурсы . Скорее , ограничения такого типа отра-

жают то обстоятельство , что решение должно удовлетворять опре-

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

са или минимальных отклонений от установленных структурных

характеристик производства ( сбыта ) .

В модели , построенной для нашей задачи , фигурирует ограничение со
знаком 0 ) , однако , чтобы получить результат в общем виде , рассмотрим оба
случая .

Как изменится симплекс-таблица при изменении величины за-

паса ресурса на D1 ? Проще всего получить ответ на этот вопрос .

если ввести D1 в правую часть первого ограничения начальной сим-

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

ния , соответствующие последовательности итераций . Поскольку

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

ведущих элементов , то очевидно , что на каждой итерации D1 будет

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

Уравнение Значения элементов правой части на соответствующих итерациях

( начало вычислений ) 1 2 ( оптимум )

1 1000 1000 + D1 1000/55 + D1

Фактически вce изменения правых частей ограничений , обуслов-

ленные введением D1 , можно определить непосредственно по данным ,

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

на каждой итерации новая правая часть каждого ограничения пред-

ставляет собой сумму двух величин: 1) постоянной и 2) члена , ли-

нейно зависящего от D1 . Постоянные соответствуют числам , которые

фигурируют на соответствующих итерациях в правых частях ограничений
симплекс-таблиц до введения D1 . Коэффициенты при D1 во вторых слагаемых
равны коэффициентам при S1 на той же итерации . Так , например , на
последнеи итерации ( оптимальное решение ) постоянные ( 2455/11 ;
1000/55 ; 91/11 ) представляют собои числа , фигурирующие в правых
частях ограничении оптимальной симплекс-таблицы до введения D1.
Коэффициенты ( 27/110 ; 1/55 ; 1/110 ) равны коэффициентам при S1 в той
же симплекс-таблице потому , что эта переменная связана только с первым
ограничением . Другими словами , при анализе влияния изменений в правой
части второго ограничения нужно пользоваться коэффициентами при
переменной S2 .

Какие выводы можно сделать из полученных результатов?

Так как введение D1 сказывается лишь на правой части симплекс-

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

допустимость решения . Поэтому D1 не может принимать значений ,

при которых какая-либо из ( базисных ) переменных становится отри-

цательной . Из этого следует , что величина D1 должна быть огра-

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

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

рующей симплекс-таблице , т . е .

X1 = 1000/55 + ( 1/55 )D1 => 0 ( 1 )

X2 = 91/11 + ( 1/110 )D1 => 0 ( 2 )

Для определения допустимого интервала изменения D1 рассмо-

трим два случая .

Случай 1: D1 => 0 Очевидно , что оба неравнества при этом условии всегда
будут неотрицательными .

Случай 2: D1 — 1000/55 . Из этого следует , что D1 => — 1000

( 1/110 )D1 => — 91/11 . Из этого следует , что D1 => — 1000

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

сделать вывод , что при — 1000 0 Решаем неравенства : ( 1 )

( 50/55 )D2 — 1000/55 . Из этого следует , что D2 — 91/11 . Из этого следует , что D2 => — 200

Объединяя 2 уравнения для Случая 2 мы получим интервал для D2 .

Объединяя 2 случая мы получим интервал [ — 200 ; 20 ]

Максимальное изменение коэффициентов удельной

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

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

изменений коэффициентов удельной прибыли ( или стоимости ) .

Следует отметить , что уравнение целевой функции никогда не
используется в качестве ведущего уравнения . Поэтому лю-

бые изменения коэффициентов целевой функции окажут влияние

только на Z-уравнение результирующей симплекс-таблицы . Это

означает , что такие изменения могут сделать полученное решение

неоптимальным . Наша цель заключается в том , чтобы найти интер-

валы значений изменений коэффициентов целевой функции ( рас-

сматривая каждый из коэффициентов отдельно ) , при которых оп-

тимальные значения переменных остаются неизменными .

Чтобы показать, как выполняются соответствующие вычисле-

ния , положим , что удельный объем сбыта , ассоциированной с переменной

X1 изменяется от 1 до 1 + d1 где d1 может быть как положительным , так и
отрицательным числом . Целевая функция в этом случае принимает следующий
вид:

Z = ( 1 + d1 )X1 + 25X2

Если воспользоваться данными начальной симплекс-таблицы и

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

тельной симплекс-таблицы , то последнее Z-уравнение будет выгля-

деть следующим образом:

Базисные переменные X1 X2 S1 S2 Решение

Z 0 0 27/110+1/55d1 5/22-50/55d1 2455/11+1000/55d1

Коэффициенты при базисных переменных X1 , X2 и остаточных я равными нулю
. Это уравнение отличается от Z-уравнения до введения d1 , только
наличием членов , содержащих d1 . Коэффициенты при d1 равны
кoэффициентам при соответствующих переменных в Z-уравнении
симплекс-таблицы для полученного ранее оптимального решения

Базисные переменные X1 X2 S1 S2 Решение

X1 1 0 1/55 -50/55 1000/55

Мы рассматриваем X1 — уравнение , так как коэффициент именно при

этон переменной в выражении для целевои функции изменился

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

ными при значениях d1 , удовлетворяющих условию неотрицатель-

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

базисных переменных в Z-уравнении . Таким образом , должны выполняться
следующие неравенства :

27/110 + 1/55d1 => 0

Из первого неравенства получаем , что d1 => — 13,5 , а из второго
следует что d1

На основании материала, рассмотренного выше, сделаем следующие выводы.

1) Область допустимых решений ЗЛП является выпуклым множеством с конечным числом угловых точек, т.е. многогранником или многоугольным множеством.

2) Существует такая угловая точка многогранника решений, в которой линейная функция достигает своего наименьшего (наибольшего) значения.

3) Каждой угловой точке многогранника решений соответствует опорный план, каждый из которых определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов A1,A2. An.

Читайте также:  Как правильно делать упражнения для зрения

Напомню, что опорным планом называется допустимое (если оно содержит лишь неотрицательные компоненты) базисное решение, т.е. если векторы Ai (i=1,2. m), входящие в разложение A1x1+A2x2+…+Anxn = B с положительными коэффициентами xi, являются линейно независимыми.

Для отыскания оптимального плана необходимо исследовать только опорные планы. Геометрически это соответствует перебору всех угловых точек многогранника решений. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний .

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

Такой перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на графическом примере. Пусть область допустимых решений изображается многоуголь­ником ABCDEGH. Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать 7 допустимых базисных решений, соответствующих семи угловым точкам мно­гоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к вершине В, а затем — к оптимальной точке С, т.е. перебрать только три вершины.

Схема, позволяющая осуществлять упорядоченный переход от одного опорного плана к другому, т.е. исходя из известного опорного плана задачи, за конечное число шагов получить ее оптимальный план, легла в основу универсального метода решения ЗЛП —симплексного метода. Если исходная задача не имеет такого плана или ее линейная функция не ограничена на многограннике решений, то симплексный метод позволяет установить это в процессе решения. Название метода произошло от понятия »симплекс» (лат. simplex — простой) — простейший выпуклый много­гранник в n-мерном пространстве с n+1 вершиной (например, тетраэдр в 3-мерном пространстве).

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

Для реализации симплексного метода — последовательного улучшения решения — необходимо освоить три основных элемента:

• способ определения какого-либо первоначального опорного плана задачи;

• правило перехода от одного опорного плана к другому, на котором значение целевой функции ближе к оптимальному;

• критерий проверки оптимальности найденного плана, позволяющий своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения.

Алгоритм симплекс-метода

Рассмотрим следующую ЗЛП.

Найти максимум целевой функции L=С+ ® max

при ограничениях где xj ³ 0 (j=1,2,…,n), bi ³ 0 (i=1,2,…m; m£n).

1. Приводим систему ограничений к виду, в котором какие-либо m переменных выражены через остальные, причем свободные члены этих выражений были неотрицательными, иначе говоря, разрешаем систему относительно какого-либо исходного базиса.

Предположим, для определенности, что система ограничений задачи содержит т единичных векторов, причем без ограничения общности можно по­ложить, что единичными являются первые т векторов, и, следовательно, переменные, которые выражены через остальные, — это x1,x2. xm, т.е. система ограничений имеет вид:

(1)

Далее приведем систему к следующему виду

(3),

где все свободные члены bi ³ 0, (i=1,2. m).

Переменные x1,x2. xm, находящиеся в левой части системы (3), называются базисными, а весь набор 1,x2. xm> — базисом; остальные переменные называются небазисными или свободными. Т.о. мы выразили базисные переменные через свободные.

2. Выражаем целевую функцию L через свободные переменные xm+1. xn, подставляя в L вместо базисных переменных их выражения через свободные из (3), и получаем первоначальный опорный план. Получим:

Т.к. все величины хi (i=1,2,…,n) должны быть неотрицательны, то наименьшие возможные значения свободных переменных — это значения, равные нулю. Положим все свободные переменные равными нулю: xm+1 = 0, . , xn = 0

и найдем из системы (3) значения базисных переменных:

Получим первоначальное базисное решение (опорный план) системы, отвечающее базису x1,x2. xm:

Оно будет вследствие (2) допустимым, а т.к. векторы, соответствующие базисным переменным, линейно независимы, то и опорным. Т. е. получим первоначальный опорный план. Геометрически данный план соответствует первоначальной угловой точке.

Подставим в максимизируемую целевую функцию L из (4) значения свободных переменных. Т.к. xm+1 = 0, . , xn = 0, то Lб = C.

Посмотрим, можем ли мы улучшить решение, т.е. увеличить целевую функцию L, увеличивая какие-нибудь из переменных xm+1, . , xn (уменьшать их мы не можем, т.к. они все равны нулю, а отрицательные значения переменных недопустимы). Это можно осуществить, перейдя к такому новому допустимому решению, в котором эта переменная будет базисной, а не равняться 0 как свободная.

Если оказалось, что все коэффициенты C¢m+1. C¢n в (4) отрицательны, то, увеличивая какие-то из переменных xm+1. xn сверх нуля, мы не можем увеличить L; значит, найденное нами базисное решение X=(b1,b2. bm,0. 0) оптимально.

3. Пусть среди коэффициентов, упомянутых в предыдущем пункте, т.е. среди чисел C¢m+1. C¢n имеются положительные, то увеличивая те из переменных xm+1, . , xn, коэффициенты при которых положительны, мы можем улучшить решение, т.е. увеличить L.

Для определенности в такой ситуации будем выбирать переменную, имеющую больший коэффициент. Пусть, например, это будет коэффициент C¢m+1 в формуле (4) при xm+1. Значит есть смысл увеличивать xm+1, т.е. перейти от данного опорного решения к другому, где переменная xm+1 ¹ 0, а вместо нее равна нулю какая-то другая. При таком переходе геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функции лучше.

Однако увеличивать xm+1 надо осторожно, так чтобы не стали отрицательными другие переменные x1,x2. xm, выраженные через свободные переменные, в частности через xm+1 формулами (3). Таким образом, должны выполняться следующие неравенства (при этом хm+2=0, хm+3=0,…, хn=0, как свободные переменные):

(5) откуда

Каждое уравнение определяет оценочное отношение – границу роста переменной хm+1, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при переменной хm+1при условии, что эти числа имеют разные знаки.

Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. Ясно, что если мы оставим остальные свободные переменные xm+2=0. xn=0, то x m+1 мы можем увеличивать только до значения, равного b¢i/ a¢i,m+1(i=1,2,…,m), а при дальнейшем увеличении xm+1 переменная xj станет отрицательной.

Каждое уравнение системы ограничений определяет конечное или бесконечное наибольшее возможное значение этой переменной – оценочное отношение.

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

Встречаются различные случаи оценки роста свободной переменной, которые зависят от знаков и значений свободного члена и коэффициента при свободной переменной xi (i=1,2,…,m). Сформулируем все возможные случаи. Обозначим: xm+1 – переводимая свободная переменная, b’i — свободный член, a’im+1 – коэффициент при xm+1. В общем виде уравнение xi = a¢i,m+1xm+1 + …+a¢i,nxn + b¢i определяет наибольшее возможное значение xm+1 по следующим правилам.

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

xm+1 мы можем увеличивать только до значения, равного b¢i/ a¢im+1, а при дальнейшем увеличении xm+1 переменная xj станет отрицательной.

Если во всех уравнениях (5) оценочное отношение xm+1, то max L = ¥ — задача решения не имеет.

Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. Поэтому выберем ту из переменных x1,x2. xm, которая раньше всех обратится в нуль при увеличении xm+1, т.е. ту, для которой величина b¢i/ a¢i,m+1 меньше всего.

Читайте также:  Каковы основные признаки характеризующие чс с медицинской точки зрения

Для этого найдем среди всех отношений (i=1,2,…,m) наименьшее; пусть это будет , k£m. Т. о., = min по всем i. Число ak,m+1 называется разрешающим элементом. Обозначим указанный минимум через r= . Если он достигается сразу при нескольких значениях i, то в качестве k берем любое из них. Очевидно,r ³ 0. Ясно, что теперь xm+1 можно увеличить до r (и не более, иначе xi станет

Дата добавления: 2016-11-23 ; просмотров: 950 | Нарушение авторских прав

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

Мы уже знакомы с геометрической интерпретацией задачи линейного программирования (п. 1.6.). Рассмотрим теперь симплекс-метод также с геометрической точки зрения. Суть дела проясняет следующая теорема.

Теорема. Каждое опорное решение канонической задачи ЛП. Является угловой точкой области допустимых решений. Наоборот, каждая угловая точка ОДР канонической задачи ЛП является опорным решением.

Доказательство. Докажем первое утверждение теоремы. Пусть — угловая точка. Пусть отрезок целиком лежит в ОДР, и его середина совпадает с :

(1)

Векторное равенство (1) равносильно системе равенств для координат

(2)

Если — свободная переменная опорного решения , то из (2) следует, что

(3)

Поскольку и — допустимые решения, то и Сумма двух отрицательных чисел может равняться нулю, только, если эти числа сами равны нулю:

и (4)

Это означает, что и также являются опорными решениями с тем же набором свободных и, следовательно, базисных переменных. Но такое решение может быть только одно. Следовательно, , то есть отрезок , представляет из себя точку. Таким образом, мы показали, что не существует отрезка целиком лежащего в ОДР и содержащего в качестве своей внутренней точки. Утверждение доказано.

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

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

Основные теоремы.

Рассмотрим систему линейных уравнений

(1)

и соответствующую ей расширенную матрицу

(2)

Пусть все свободные члены в (1) (и, следовательно, в (2)) неотрицательны:

(3)

Выделим некоторый, например, -тый столбец, который далее будем называть ведущим.

Определение 1. Если элемент , стоящий в — той строке ведущего — того столбца матрицы системы (1), положителен, то определим для этой строкидопустимое отношение , как отношение элемента столбца свободных членов к данному элементу ведущего столбца:

, (4)

. (5)

Определение 2. Строка с конечным минимальным допустимым отношением называется ведущей.

Определение 3. Элемент матрицы системы, стоящий на пересечении ведущей строки и ведущего столбца называется ключевым.

Пусть в нашем случае ведущей будет — тая строка. В матрице системы (2) ключевой элемент мы выделяем квадратными скобками. Ключевой элемент определяет одновременно ведущую строку и ведущий столбец. С помощью элементарных преобразований Гаусса, преобразуем матрицу системы (2) так, чтобы ведущий столбец стал базисным с единицей в ведущей строке. Для этого выполним следующую последовательность действий.

Вначале разделим ведущую строку на ключевой элемент. В результате получим ведущую строку вида:

(6)

Затем рассмотрим любую другую строку

(7)

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

. (8)

Из строки (8) вычтем ведущую строку (6). Получим строку:

. (9)

Поскольку — минимальное допустимое отношение, то свободный член полученной строки неотрицателен:

. (10)

Теперь рассмотрим строку с бесконечным допустимым отношением :

(11)

Чтобы в ведущем — том столбце этой строки получить ноль, прибавим к ней ведущую строку, умноженную на число . В результате получим строку вида:

. (12)

Ясно, что свободный член этой строки неотрицателен:

, (13)

поскольку и .

В результате всех преобразований получим матрицу системы следующего вида

(14)

Как видно из вышеприведённых рассуждений, при этом окажется, что все свободные члены расширенной матрицы системы (14) также неотрицательны, если неотрицательны все свободные члены расширенной матрицы системы (2).

Таким образом, доказана следующая важная теорема.

Теорема о минимальном допустимом отношении. Пусть в расширенной матрице системы линейных уравнений с неотрицательным столбцом свободных членов выделен ведущий столбец и определена ведущая строка с минимальным допустимым отношением. Если с помощью элементарных преобразований Гаусса из исходной матрицы получена новая матрица, ведущий столбец которой является базисным с единицей в ведущей строке, то столбец свободных членов полученной матрицы будет также неотрицательным.

Из теоремы о минимальном допустимом отношении следует, что с помощью описанной в п.1.8 операции однократного замещения симплекс-таблица преобразуется в новую симплекс-таблицу.

Теорема об оптимальности опорного решения.

Пусть — опорное решение канонической задачи ЛП,

целевая функция зависит только от свободных переменных и все её коэффициенты отрицательны или равны нулю. Тогда — оптимальное решение этой задачи.

Доказательство. Без ограничения общности, можно считать свободными переменные . Тогда целевая функция имеет вид

(15)

. (16)

Из условия (16) и неотрицательности переменных следует, что для любого из области допустимых решений справедливо неравенство:

. (17)

Поскольку все свободные переменные опорного решения равны нулю, то справедливо равенство:

, (18)

Из (17) и (18) следует, что — оптимальное решение. ч.т.д.

Замечание. Условие (16) равносильно тому, что все коэффициенты индексной строки симплекс-таблицы, кроме, быть может, свободного члена, неотрицательны.

Изложим теперь суть симплекс-метода (см. п.1.8-1.9). Исходным пунктом метода служит первая симплекс-таблица. Ей соответствует опорное решение (или угловая точка; см. п.1.9), оптимальность которого проверяется с помощью признака оптимальности. Если решение не оптимально, то выполняется операция однократного замещения, которая приводит к новой симплекс-таблице. Если алгоритм симплекс метода не останавливается (из-за невозможности выбора ведущей строки или возврата в одну из предыдущих угловых точек), через конечное число шагов будет найдено оптимальное решение. Это следует из того, что опорных решений конечное число.

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

. (19)

Иначе, существовали бы минимальное допустимое отношение и соответствующая ему ведущая строка. Перенесём ведущий столбец в правую часть системы линейных ограничений:

Положив все свободные переменные, кроме , равными нулю получим систему:

(20)

В силу условий (3) и (19) система (20) определяет допустимое решение рассматриваемой задачи ЛП для любого неотрицательного значения переменной . Поскольку целевая функция задачи зависит только от свободных переменных, из которых все, кроме переменной , равны нулю, то :

Так как для ведущего — того столбца , то:

.

Это доказывает, что соответствующая задача линейного программирования не имеет оптимального решения.

Подробно зацикливание, то есть возврат в одну из предыдущих угловых точек, мы обсуждать не будем. Отметим только, что при повторе ранее уже полученного опорного решения следует тем или иным способом изменить выбор ведущего столбца на текущем шаге. Например, можно на каждом шаге выбирать ведущий столбец случайным образом.

Из геометрической интерпретации задачи линейного программирования вытекает следующая теорема.

Теорема о достаточном условии существования оптимального решения задачи ЛП.

Если (многогранная) область допустимых решений задачи линейного программирования ограничена в направлении вектора роста целевой функции, то максимальное значение этой функции конечно и достигается в некоторой угловой точке ОДР.

Следствие. Если область допустимых решений задачи линейного программирования ограничена (является выпуклым многоугольником или многогранником), то оптимальное решение существует для любого вектора роста.

Последнее изменение этой страницы: 2016-08-11

Источники:
  • http://lektsii.org/11-35616.html
  • http://lectmania.ru/1x14b1d.html