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


 

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

35081. Теория государства и права. Конспект лекций 1.58 MB
  Предмет и методология теории государства и права. Место и роль теории государства и права в системе других наук. Основные категории и структура курса теории государства и права.
35082. Туристско-рекреационные районы, их иерархия и типология 634.5 KB
  Чаще всего аттрактивиость обусловливается всем комплексом факторов и в этом случае такие комплексноаттрактивные районы особенно привлекательны для туристов и туристского бизнеса. Задача рекреационной географии и туристского рерсурсоведения заключается сейчас не только в том чтобы найти и оцепить новые ресурсы в местах до сих пор не освоенных туристской отраслью а обогатить туристский потенциал уже освоенных мест обустроенных туристскими учреждениями доступными для потенциальных туристов. Нахождение в них туристов носит скорее...
35083. ПРАВО ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ 562 KB
  ОБЩИЕ ПОЛОЖЕНИЯ ПРАВА ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ. Понятие предмет и функции права интеллектуальной собственности. Система права интеллектуальной собственности. Источники права интеллектуальной собственности.
35084. Управление человеческими ресурсами. Конспект лекций 143.75 KB
  Структура персонала организации определяется по категориям – руководители специалисты служащие рабочие. Все категории персонала разделяются по профессиям специальностям квалификационным признакам и характеризуются специфическим местом в системе управления особенностями профессиональной подготовки. Разработка и проведение кадровой политики Оплата и стимулирование труда Групповое управление взаимоотношение в коллективе и с профсоюзами Социально психологические аспекты управления Принципы подбора и расстановки персонала Формы оплаты...
35085. Управлінське документування: Кредитно – модульний курс 292.5 KB
  Важливим завданням є створення і функціонування системи документів як робочого інструменту будьякої сфери. Зараз перед державою та суспільством постало багато нових завдань і значно зріс обсяг інформації стали жорстокішими вимоги до якості документів термінів їх виконання та доведення до виконавців.1 Призначення та класифікація документів Документ – це засіб закріплення різними способами на відповідному матеріалі інформації про факти події явища об’єктивної дійсності та розумову діяльність людини. Під час...
35086. Понятие и юридическая структура административного правонарушения в области таможенного дела 180 KB
  Законодательство различает посягательства в сфере таможенного дела в зависимости от различных степеней тяжести на преступления и проступки. Под административными правонарушениями в области таможенного деланарушениями таможенных правил понимаются именно проступки.1 КоАП России административным правонарушением признается противоправное виновное действие бездействие физического или юридического лица за которое КоАП России и законами субъектов РФ к административным правонарушениям в сфере таможенного дела – не применимо установлена...
35087. ВАЛЕОЛОГИЯ. Учебник для вузов 2.92 MB
  Так в части требований к уровню подготовленности выпускника педагогического вуза определены следующие условия: владение системой знаний о взаимосвязях физического психического и социального здоровья человека и общества; обладание организационнодеятельностными умениями необходимыми для самоанализа развития своих творческих способностей и повышения квалификации; осознание здоровья как ценности владение знаниями и умениями по охране здоровья и безопасности жизнедеятельности; представление о взаимодействии организма и среды месте...
35088. Формирование лихорадочных реакций в фило- и онтогенезе 74.33 KB
  Интеграция температурных сигналов и температуры самого гипоталамуса формирует эффекторные импульсы проходящие преимущественно по симпатическим нервам и определяющие состояние обмена веществ интенсивность периферического кровообращения дрожь одышку. Особое место в биохимии опухолей занимает изучение обмена углеводов и выработки энергии. Нарушение регуляции обмена веществ основного обмена ТИПИЧЕСКИЕ НАРУШЕНИЯ ОБМЕНА ВЕЩЕСТВ. НАРУШЕНИЯ РЕГУЛЯЦИИ ОБМЕНА ВЕЩЕСТВ Обмен веществ или метаболизм в организме определяется наследственными...
35089. Інформаційне забезпечення юридичної діяльності 3.25 MB
  Вступ В розділах посібника користувачі зможуть отримати поглибленні знання: зі створення інформаційних систем ділового та юридичного призначення у середовищі СУБД MS Access зі створювання електронних шаблонів з полями форм для юридичних та інших документів зі створення серійних документів на основі злиття табличних даних та зразка основного документа зі створювання та використовування макросів для автоматизації підготовки документів у MS Word та MS Excel. До виконання завдань необхідно обов'язково ознайомитися з теоретичними основами баз...