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. То есть, при любой замене получим недопустимый базис. Следовательно, задача не имеет допустимого решения.


 

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

16264. Вектороскоп 491.5 KB
  Лабораторная работа №8. Вектороскоп. 1 Цель работы: 1.1 Изучить параметры телевизионного сигнала системы PAL. 2 Литература: 2.1 Джакония В.Е. Телевидение. М.: Радио и связь 1980. 2.2 Телевизионная техника. Справочник./ Под редакцией Зубарева Ю.Б .и Глориозова Г.Л.М.: Ради...
16265. Видеомагнитофон 437 KB
  Лабораторная работа № 6 Видеомагнитофон 1 Цель работы: 1.1 Изучить конструкцию и элементы управления видеoмагнитофона формата VHS. 1.2 Проконтролировать работу ЛПМ в разных режимах работы видеомагнитофона. 2 Литература: 2.1 Джакония В.Е. Телевидение.М.: Радио и cвя
16266. Измерение параметров телевизионного тракта с помощью испытательных сигналов 2.15 MB
  Лабораторная работа №10 Измерение параметров телевизионного тракта с помощью испытательных сигналов Цель работы: Определение параметров телевизионного тракта с помощью испытательных сигналов. Научиться пользоваться генератором Г635. ...
16267. Телевизионные испытательные строки 1.01 MB
  Телевизионные испытательные строки Тракт телевизионного вещания очень специфичен: он отличается большой протяженностью и включает в себя огромное количество оборудования обслуживаемого различными службами. В тоже время необходимо знать характеристики не только
16268. Исследование кодера MPEG-2 552.3 KB
  Лабораторная работа №6.1 Исследование кодера MPEG2 1 Цель работы: Ознакомиться с назначением и характеристиками кодера PBI DCH3000EC 40. Ознакомиться с составом и назначением интерфейсов кодера PBI DCH3000EC 40. Ознакомиться с типовой схемой включения кодера PBI DCH3000EC 40. ...
16269. Исследование элементов синхрогенератора 610.5 KB
  Лабораторная работа №2 Исследование элементов синхрогенератора 1 Цель работы: Изучить принцип работы и выходные сигналы синхрокомплекта ПБ99. Исследовать форму и структуру сигналов на выходе синхрогенератора. 2 Литература: 2.1. Колин К....
16270. Исследование устройства декодирующего системы SECAM 681.5 KB
  Лабораторная работа №4 Исследование устройства декодирующего системы SECAM 1 Цель работы: Изучить принцип работы МЦ и СМЦ. Снять осциллограммы в контрольных точках. Сделать выводы о работоспособности блоков. 2 Литература: 2.1 Джакония...
16271. Исследование устройства кодирующего системы SЕCАМ 808 KB
  Лабораторная работа №3 Исследование устройства кодирующего системы SЕCАМ 1 Цель работы: Изучить состав устройства кодирующего ПБ29. Получить практические навыки по работе с устройством кодирующим. 2 Литература: 2.1 Джакония В.Е. Телевиде...
16272. Исследование спектра сигнала спутника Hot Biord 1.7 MB
  Лабораторная работа №4 Исследование спектра сигнала спутника Hot Biord 1 Цель работы: 1.1 Научиться пользоваться спутниковым ресивером. 1.2 Научиться настраиваться на выбранный транспондер и фиксировать его в памяти прибора DL4. 1.2 Научиться заносить данные прибора в ...