36220

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

Доклад

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

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

Русский

2013-09-21

93.5 KB

23 чел.

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


 

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

27408. Методика изучения сезонных изменений в природе 23.5 KB
  важны уроки обобщения ставят всё по местам = проведение сложных сравнений обощающего характера углубляет расширяет кругозор восприятие природы как целого Помогают: дидактич схемы наглядно показывают связи таблицы эстетика рассматривание художественных произведений: картин стихов музыкальных произведений Чайковский времена года Пример урок Осенние явления природы: беседа о состоянии неживой природы высота Солнца световой день t небо влажность почему произошли изменения анализ содержания установление...
27409. Значение уроков технологии, изобразительного искусства, музыки в системе начального общего образования 39.5 KB
  Источниками полноценного развития ребенка выступают два вида деятельности освоение прошлого опыта человечества за счет приобщения к современной культуре. самостоятельно реализация своих возможностей благодаря творческой деятельности способствует проявлению самодеятельности самореализации воплощению собственных идей. В творческой деятельности решаются поисковотворческие задачи с целью развить способности ребенка. под способностями понимаются индивидуально психологические и двигательные особенности индивида Способность к...
27410. Формирование регулятивных универсальных учебных действий у младших школьников на уроках технологии 31.5 KB
  Регулятивные УУД обеспечивают обучающимся организацию своей учебной деятельности: целеполагание что известно и неизвестно; планирование определение последовательности промежуточных целей с учётом конечного результата; составление плана и последовательности действий; прогнозирование предвосхищение результата и уровня усвоения знаний его временных характеристик; контроль в форме сличения способа действия и его результата с заданным эталоном; коррекция; оценка; саморегуляция. Специфика технологии: ...
27411. Формирование познавательных универсальных учебных действий у младших школьников на уроках технологии 25.5 KB
  Познавательные УУД: общеучебные логические постановка и решение проблемы.Общеучебные: самостоятельное выделение и формулирование познавательной цели; поиск и выделение необходимой информации структурирование знаний; выбор наиболее эффективных способов решения задач в рефлексия способов и условий действия контроль и оценка процесса и результатов деятельности;формы уд для формирования ууд: учебное сотрудничество творческая проектная учебноисследовательская деятельность контрольнооценочн и рефлексивная Д Познават общеучебные ууд...
27412. Формирование коммуникативных универсальных учебных действий у младших школьников на уроках технологии 26.5 KB
  Коммуникативные УУД: ‒ планирование учебного сотрудничества с учителем и сверстниками определение цели функций участников способов взаимодействия; ‒ постановка вопросов инициативное сотрудничество в поиске и сборе информации; ‒ разрешение конфликтов выявление идентификация проблемы поиск и оценка альтернативных способов разрешения конфликта принятие решения и его реализация; ‒ управление поведением партнёра контроль коррекция оценка его действий; ‒ умение с полно и точно выражать мысли в соответствии с...
27413. Сравнительная характеристика современных программ и учебно-методических комплектов по технологии для начальной школы с учетом требований ФГОС НОО 32 KB
  УМК Перспективная начальная школа практикоориентированная направленность содержания обучения; применение знаний полученных при изучении других образовательных областей и тематические пересечения с образовательными предметами для решения технических и техно логических задач применение полученного опыта практической деятельности для выполнения домашних трудовых обязанностей. УМК Гармония; УМК Классическая начальная школа; Учебники из серии Маленький мастер Издательство АСТПРЕСС ШКОЛА; учебники образовательной системы Школа...
27414. Формирование культуры труда у младших школьников на уроках технологии 29 KB
  КУЛЬТУРА ТРУДА комплексная качественная характеристика состояния труда. Включает рациональную организацию труда благоприятные условия труда использование передовых технологий высокий профессионализм работника партнерские отношения между участниками совместного труда. способствует: сохранению здоровья работника; развитию чувства удовлетворенности трудом хорошего настроения интереса и активности при выполнении работы; росту профессиональной квалификации; профессиональной и личной самореализации; освоению рациональных приемов труда новой...
27415. Конструирование и его организация на уроках технологии в начальных классах 33 KB
  Модель и моделирование техническое моделирование и конструирование на уроках технологии получают первоначальные сведения о моделях машинах знакомятся с технической терминологией производством рабочими профессиями. Конструирование по образцу предлагают образцы построек = обеспечивается прямая передача детям готовых знаний способов действий основанная на подражании. Конструирование по условиям определяют условия которым постройка должна соответствовать. начинать моделирование и конструирование следует с простейших изделий...
27416. Проектирование/моделирование, организация и методика проведения интегрированных уроков в процессе обучения искусству 36 KB
  Уроки художественноэстетического цикла должны создавать условия для формирования и развития художественной культуры обучающихся. На протяжении работы в школе в качестве учителя изобразительного искусства хотелось сделать уроки искусства более эмоциональными запоминающимися и плодотворными а главное заинтересовать обучающихся вызвать желание творить. Проникновение современных технологий в образовательную практику в том числе и в уроки искусства открывает новые возможности и перспективы. Интегрированные уроки изобразительного искусства и...