36220

Теоретические основы линейного программирования. Симплекс-метод. Метод искусственного базиса

Доклад

Математика и математический анализ

Канонической формой задачи ЛП называется такая ее запись при которой 1 целевая функция должна быть минимизирована; 2 все искомые переменные должны быть неотрицательны; 3 все ограничения кроме неотрицательности переменных имеют вид равенства. Оптимальные значения переменных от такой замены не изменятся. 2 Если в исходной задаче на какойто параметр хj не наложено условие неотрицательности то можно сделать замену переменных положив где – новые переменные удовлетворяющие условию неотрицательности. 3 Преобразование неравенств в...

Русский

2013-09-21

93.5 KB

22 чел.

6 Вопрос

Теоретические основы линейного программирования. Симплекс-метод. Метод искусственного базиса.

7.2. Теоретические основы решения задач ЛП

Выпуклые множества

Def.  Пусть a, b  En – две произвольные точки. Отрезком [a, b] называется множество точек с (), определяемое соотношением: с() = a + (1–)b.         0    1.

Def. Множество S называется выпуклым, если a, b  S    [a, b]  S.

Обобщением понятия “отрезок” является понятие выпуклой оболочки.

Def. Пусть имеем k точек a1, … аk  En. Их выпуклой оболочкой называется множество точек, определяемое соотношением:

1a1 +…+kak  En, 0  j , .                                 (6.1)

При фиксированных j выражение (1) называется выпуклой комбинацией (это одна точка). При n = 2, 3 геометрическим образом выпуклой оболочки является, соответственно, многоугольник на плоскости и многогранник в пространстве с k вершинами.

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

Пример – углы многоугольников на плоскости.

Каноническая форма задачи ЛП. Метод решения задачи ЛП будем излагать в предположении, что она приведена к канонической форме.

Def. Канонической формой задачи ЛП называется такая ее запись, при которой

1) целевая функция должна быть минимизирована;

2) все искомые переменные должны быть неотрицательны;

3) все ограничения (кроме неотрицательности переменных) имеют вид равенства.

Привести произвольную задачу ЛП к канонической форме достаточно просто.

1) Если в исходной задаче целевую функцию q надо максимизировать, то достаточно изменить знак функции, положив q1 = – q  mix. Оптимальные значения переменных от такой замены не изменятся.

2) Если в исходной задаче на какой-то параметр хj не наложено условие неотрицательности, то можно сделать замену переменных, положив , где – новые переменные, удовлетворяющие условию неотрицательности. Тогда при  будет хj  0, а при  будет хj  0.

3) Преобразование неравенств в равенства достигается введением вспомогательных неотрицательных переменных. Если имеем неравенство вида      …  bi, то к левой части неравенства надо прибавить вспомогательную переменную: … + xn+i = bi. Если имеем неравенство вида …  bi, то от левой части неравенства надо отнять вспомогательную переменную: … – xn+i = bi.

Пример 7.2. Имеем задачу: найти максимум q = 2х1 + 3х2 при ограничениях

.

Преобразуем к канонической форме. Положим х1 = у1 – у2;  х2 = у3 – у4. Отсюда

q1 = –2(у1 – у2) – 3(у3 – у4)  min.

.

Базисные решения. Пусть имеем задачу ЛП в канонической форме:

q = c1 x1 + c2 x2 + … + cn xn  min

a11 x1  + a12 x2  + …  + a1n xn = b1

a21 x1  +  a22 x2  + … + a2n xn = b2                                (7.1) 

………………..

  am1 x1 + am2 x2 + … + amn xn = bm . 

Будем предполагать, что rank A = m, где А – матрица системы (7.1). Это возможно только если число уравнений m меньше числа неизвестных n. Тогда система (7.1) имеет бесконечное множество решений. Чтобы выделить из этого множества какое-нибудь определенное решение, надо зафиксировать nm произвольных неизвестных и решить полученную систему относительно m оставшихся.

Def. Будем называть решение системы (7.1) допустимым, если в нем все значения xj неотрицательны, т.е. удовлетворяют ограничению, принятому в канонической форме задачи ЛП.

Особое место среди всех возможных решений системы занимают так называемые базисные решения.

Def. Решение системы (7.1) называется базисным, если в нем nm фиксированных переменных принимают нулевые значения. Если базисное решение является допустимым, но оно называется базисным допустимым.

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

Вспомогательные утверждения. Следующие утверждения играют важную роль в теории ЛП.

Лемма 7.1. Если система (7.1) имеет допустимые решения, то она имеет и допустимые базисные решения.

Лемма 7.2. Область D допустимых решений системы (7.1) является выпуклым множеством.

Лемма 7.3. Для того, чтобы точка х  D была угловой, необходимо и достаточно, чтобы ее координаты образовывали базисное допустимое решение системы (7.1).

Основная теорема ЛП. Данная теорема позволяет построить численную процедуру решения задачи ЛП.

Теорема 7.1. Если целевая функция q задачи ЛП имеет конечный минимум, то он достигается в одной из базисных точек.

Доказательство. Пусть система (7.1) имеет k допустимых базисных решений: x1, x2 ,…, xk, в которых целевая функция принимает значения q1, q2,…, qk, соответственно. Пусть x = 1x1 +…+ kxk – любая допустимая не угловая точка. Тогда q(x) = 1q1 +…+ kqk. Пусть q J = min {q j} (если минимум достигается одновременно при нескольких значениях j, выбираем любое из них). Так как при любом j выполняется неравенство q J   q j, то q(x) = 1q1 +…+ kqk      1qJ +…+ kqJ = qJ(1 +…+ k) = qJ. Следовательно, минимум q(x) достигается в точке xJ – базисное решение, в котором q(xJ) = qJ, что и требовалось доказать.

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

7.3. Симплекс-метод

Симплекс-метод – численная процедура решения задачи ЛП, разработанная Г. Данцигом в 50-х годах 20 века. Название обусловлено тем, что первые задачи, решаемые этим методом, имели областью D допустимых решений n-мерный симплекс – многогранник с n +1 вершинами. Впоследствии процедура была распространена на общий случай. Рассмотрим простейший вариант метода, не предусматривающий возможности зацикливания, потери точности и других трудностей, встречающихся при решении задач ЛП уже средней сложности.

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

Исходные предпосылки. Как и ранее, будем предполагать, что в системе (7.1) n > m = rank A, и, следовательно, в матрице А нет линейно зависимых строк. В противном случае линейно зависимые строки следует исключить из А.

Def.  Параметры из набора x1, x2 ,…, xn, равные 0 в базисном решении, будем называть небазисными переменными, остальные параметры будем называть базисными переменными. Совокупность базисных переменных называется базисом.

Число базисных переменных всегда равно rank А, т.е. m.

Поиск решения начинается в предположении, что система (7.1) разрешена относительно базисных переменных, т.е. если x1, x2 ,…, xm – базисные переменные, то система (7.1) приведена к виду:

x1 =  b1 – (a1m+1 xm+1  + a1m+2 xm+2  + …  + a1n xn )

 x2 =  b2 – (a2m+1 xm+1  + a2m+2 xm+2  + …  + a2n xn )                   (7.5) 

………………..

      xm =  bm – (am m+1 xm+1  + am m+2 xm+2  + …  + am n xn ).

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

q = c0 + cm+1 xm+1 + cm+2 xm+2  + …  +  cn xn  min.

Замечание. В (7.5) использованы те же обозначения для коэффициентов, что и в (7.1), хотя в этих выражениях они различаются. Кроме того, обращаем внимание на знак “” перед скобками – в дальнейших выкладках знаки коэффициентов ai j определяются, исходя из его наличия.

Очевидно, базисным решением системы (7.5) является x0 = (b1, b2, …, bm, 0, …, 0)T и q(x0) = c0, которое получается при обнулении всех переменных в правой части. Данное решение будет допустимым, если bi  0 для всех i. Систему (7.5) назовем исходной симплекс-таблицей. На последующих итерациях симплекс-метода осуществляется переход к новым базисным решениям. Для этого надо поменять набор базисных переменных, т.е. положить отличными от 0 другие параметры. Особенность симплекс-метода состоит в том, что такой переход производится заменой только одного параметра. То есть среди небазисных переменных выбирается некоторый параметр хJ, который переводится в базис, а из базиса одновременно с этим выводится  некий параметр хK, чтобы количество базисных переменных не изменилось. Эта особенность метода позволяет сменить базис максимально экономно с точки зрения объема вычислений.

Выбор хJ для перевода в базис. Цель данной операции – выбрать для перевода такой параметр, чтобы в новой базисной точке значение целевой функции улучшилось, т.е. уменьшилось.  В исходной базисной точке x0 все небазисные переменные равны 0. Если параметр хj перевести в базис, то он станет положительным. Следовательно, целевая функция при этом уменьшится, если      сj < 0. Причем, чем сj больше по модулю, тем сильнее будет уменьшение функции.

Выбор хK для вывода из базиса. Пусть хK найден. Чтобы обновить базис надо из К-го уравнения симплекс-таблицы выразить хJ:

.  (7.6)

Выражение (7.6) подставим в остальные уравнения системы (7.5) и целевую функцию. Получим при i = 1,… K – 1, K + 1,…, m:

.    (7.7)

.

Новое базисное решение будет допустимым, если   i. Следовательно, должно быть . Правое неравенство должно выполняться, чтобы свободный член в выражении (7.6) был также неотрицательным. Поскольку в (7.5) bi  0, то должно также быть ai J > 0 для всех i. Все перечисленные требования будут удовлетворены, если номер К выбирать из условия:

.                                (7.8)

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

Условие отсутствия конечного решения. Предположим теперь, что при любом j, таком, что cj < 0, среди ai j нет положительных ни при каком i. Это означает, что из базиса нельзя вывести ни один из базисных параметров. С другой стороны, раз среди cj есть отрицательные, то оптимальный базис не найден. Такая ситуация означает, что конечного оптимального решения не существует, т.е. lin q (x) = – . Так бывает, когда D не ограничена.

7.4. Метод искусственного базиса (М-метод)

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

    .

В данном примере единичную матрицу образуют 1 и 3 столбцы.

Если такой матрицы нет, то ее достраивают, вводя искусственные переменные, при этом используют следующее правило: если среди ограничений имеем неравенство …  bi и bi  0, или равенство … = bi также при bi  0, то в левую часть этого ограничение добавляем + хn+i , а в целевую функцию добавляем + Мхn+i , где М – произвольное большое число, такое что М >> max | cj |, например, можно положить М = 100 ( max | cj | + 1). Неравенства типа …  bi не требуют добавления искусственных переменных, т.к. их функции могут выполнять вспомогательные переменные, добавляемые при приведении задачи ЛП к канонической форме. Если какие-то bi < 0, то это неравенство следует умножить на – 1.

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

Пример 7.5. Пусть имеем задачу:

               .

Из последней системы невозможно вывести искусственный параметр x5 ни заменой его на x1 т.к.  достигается при i = 1, ни заменой на x4 т.к. при этом ai j < 0. То есть, при любой замене получим недопустимый базис. Следовательно, задача не имеет допустимого решения.


 

А также другие работы, которые могут Вас заинтересовать

44253. Особенности перевода языковых элементов, отражающих агрессивное состояние человека с китайского на русский язык 242 KB
  Данная работа посвящена исследованию особенностей перевода языковых элементов отражающих агрессивное состояние человека с китайского на русский язык. Таким образом актуальность работы в способах перевода языковых элементов выражающие агрессивное состояние человека. Объектом данного исследования являются языковые элементы выражающие агрессивное состояние человека а предметом – способы перевода языковых элементов выражающих агрессивное состояние человека. Целью данного исследования является выявление оптимальных способов перевода...
44254. Реконструкция аккумуляторного участка в РДАУП Автобусный парк № 1 г. Витебска 719.5 KB
  Расчёт годового объёма работ. Расчет годового объема работ по ТОТР вспомогательных работ работ по самообслуживанию. Реконструкцию необходимо проводить таким образом чтобы обеспечить нормальную работу действующих зон и участков. В Витебске работает более 30 автобусных маршрутов.
44255. Годинники, засновані на підрахунку періодів коливань від задаючого генератора за допомогою електронної схеми і виведення інформації на цифровий дисплей 545 KB
  В умовах подальшого технічного прогресу, що характеризується інтенсивним використанням електроніки та мікропроцесорної техніки, сучасний спеціаліст в будь-якій галузі науки й техніки повинен бути ознайомлений із основними функціональними пристроями електроніки, які становлять основу усіх систем керування технологічними процесами.
44256. ЧЕТЫРЕХЭТАЖНАЯ БЛОК-СЕКЦИЯ НА 12 КВАРТИР 1.01 MB
  Кладка стен осуществляется на цементно-песчаном растворе. Толщина наружных стен определяется на основании теплотехнического расчета. Изначально толщина наружной стены предполагается равной 510 мм. Такая толщина необходима для обеспечения устойчивости по отношению к ветровым и ударным нагрузкам, а также для увеличения тепло- и звукоизоляционной способности стен
44257. Расчет канализационной сети 110 KB
  Общесплавными называют системы канализации при которых все сточные воды бытовые производственные и дождевые сплавляются по одной общей сети труб и каналов за пределы городской территории на очистные сооружения. Раздельными называют системы канализации при которых дождевые и условно чистые производственные воды отводят по одной сети труб и каналов а бытовые и загрязненные производственные сточные воды по другой одной или нескольким сетям. Характеристика наружной канализационной сети Наружной канализационной сетью называют...
44258. Расчёт многопустотной плиты перекрытия 355.5 KB
  Расчетные данные Для бетона класса В 30 Rb=17 МПа; Rbser=22 МПа; Rbt=12 МПа; Rbt ser=18 МПа; Eв=29000 МПа для тяжелого бетона с тепловой обработкой Для напрягаемой арматуры класса АтIV: Rsn=590 МПа; Rs=510 МПа; Rs=405 МПа; Es=19105 МПа. Для арматуры сварных сеток и каркасов из проволоки класса ВрI: R=360 МПа; Rs=265 МПа; Es=1.7105 МПа. Rвр=05 В=30=0530=15 МПа.
44259. Разработка жидкостный ракетный двигатель первой ступени ракетоносителя, работающего на топливе Керосин и О2ж 3.15 MB
  Объектами разработки являются конструкция камеры компоновочная схема и пневмогидравлическая схема двигателя. В процессе работы произведён выбор системы подачи схемы и основных параметров системы характеризующих совершенство процессов в камере сгорания и сопле проведен тепловой расчет камеры определены параметры системы подачи выполнено...
44260. АНАЛІЗ РОЗВЯЗУЮЧИХ ВЛАСТИВОСТЕЙ ІМПЕДАНСНИХ СТРУКТУР З РЕАКТИВНИМ ІМПЕДАНСОМ 8.48 MB
  Значення коефіцієнта придушення. Аркуш 5 Значення коефіцієнта придушення. Ефективність запропонованої неоднорідної імпедансної смуги була оцінена в досить вузькому частотному діапазоні у зв'язку з чим не зрозуміло як буде поводитися коефіцієнт придушення за границями цього діапазону. Коефіцієнт придушення імпедансної смуги.
44261. Создание ИТ инфраструктуры внутри организации ОАО «ИПРОМАШПРОМ» 6.33 MB
  ИТ инфраструктура гарантирует: бесперебойную работу сети; адекватную скоростью расширения без перестройки; возможность управления ИТ инфраструктурой.1 LN WLN Wireless re Network вид локальной вычислительной сети LN использующий для связи и передачи данных между узлами высокочастотные радиоволны а не кабельные соединения.2 WLN CN Cmpus re Network кампусная сеть объединяющая локальные сети близко расположенных зданий на ограниченной территории студенческий городок. WN Wide re Network – сети объединяющие территориально...