рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии

МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии - раздел Информатика, Министерство Образования, Науки, Молодежи И Спорта Украины Националь...

МИНИСТЕРСТВО ОБРАЗОВАНИЯ, НАУКИ, МОЛОДЕЖИ И СПОРТА УКРАИНЫ

НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ УКРАИНЫ

«КиЕвский ПолИтехнИчЕСКий Институт»

 

 

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

 

МетодичЕСКИЕ УКАЗАНИЯ

Для самостоятельной работы

по дисциплине «Математические методы исследования операций»

 

для студентов специальности

«Информационные управляющие системы и технологии»

 

Утверждено

На заседании кафедры автоматизированных систем обработки информации и управления Протокол № 1 от 29.08.2012

 

 

Киев 2012

Симплекс-метод. Методические указания для самостоятельной работы по дис­циплине «Математические методы исследования операций» для студентов специальности «Информационные управляющие системы и технологии» / Сост.: Е.Г. Жданова. – К.: НТУУ “КПИ”, 2012. – 70 с.

 

Учебное издание

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

 

МетодичЕСКИЕ УКАЗАНИЯ

Для самостоятельной работы

по дисциплине «Математические методы исследования операций»

 

для студентов специальности

«Информационные управляющие системы и технологии»

 

 

Составитель Жданова Елена Григорьевна

 

Ответственный редактор В.А. Тихонов

Рецензенты: C.Ф. Теленик

В.Н. Кузнецов


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

 

 

Содержание

1. Формы ЗЛП................................................................................................................................... 4

2. Эквивалентность различных форм ЗЛП............................................................................. 5

3. Основные свойства ЗЛП.......................................................................................................... 8

4. Идея симплекс – метода......................................................................................................... 12

5. Преобразованная задача....................................................................................................... 12

6. Способ перехода от одного ДБР к другому....................................................................... 14

7. Условие оптимальности ДБР................................................................................................ 16

8. Схема симплекс-метода......................................................................................................... 18

9. Табличный симплекс-метод.................................................................................................. 21

9.1. Схема табличного симплекс-метода...................................................................... 22

10. Примеры реализации табличного симплекс-метода................................................... 23

11. Искусственное начальное решение.................................................................................. 34

11.1. М - метод...................................................................................................................... 35

11.2. Двухэтапный метод................................................................................................... 38

12. Вырожденность....................................................................................................................... 46

12.1 Вырожденное оптимальное решение................................................................... 46

12.2. Промежуточное вырожденное решение............................................................. 48

13. Альтернативные оптимальные решения........................................................................ 56

14. Неограниченность пространства решений и целевой функции............................... 59

15. Отсутствие допустимых решений..................................................................................... 63

16.Задания для контрольной работы...................................................................................... 68

Список литературы...................................................................................................................... 70

 


Формы ЗЛП

называется задачей линейного программирования (ЗЛП). Основными допущениями, принимаемыми при построении линейных моделей, является пропорцио­нальность, аддитивность,…

Эквивалентность различных форм ЗЛП

Правила преобразования различных форм ЗЛП: а) максимизация целевой функции эквивалентна минимизации целевой функции ; б) ограничение-неравенство «≤» с помощью введения неотрицательной переменной можно заменить системой:

Пример 2.1

Привести ЗЛП к канонической форме:

z = 3x1 – x2 → max,

x1 + 2x2 ≥ 6,

– 2x1 + 7x2 ≥ 8,

3x1 – 8x2 ≤ 15,

– 4x1 + x2 = 10,

x1 , x2 ≥ 0.

Решение

x1 + 2x2 – s1 = 6, s1 ≥ 0.  

Пример 2.2

Привести ЗЛП к ЗЛП в канонической форме, в которой направление оптимизации - максимизация:

z = 3x1 – 5x2 → min,

4x1 + 7x2 ≤ 6,

5x1 + 2x2 ≥ 8,

3x1 – 3x2 ≥ 5,

x1 , x2 ≥ 0.

Решение

Для изменения направления оптимизации нужно умножить целевую функцию задачи на (–1)). В первое ограничение введём остаточную переменную, а в два последних – избыточные переменные. Каноническая форма задачи выглядит таким образом:

z = –3x1 + 5x2 + 0s1 + 0s2 + 0s3max,

4x1 + 7x2 + s1 = 6,

5x1 + 2x2 – s2 = 8,

3x1 – 3x2 – s3 = 5,

x1, x2, s1, s2, s3 ≥ 0 .

 

Пример 2.3

Привести к канонической форме ЗЛП.

max z = 13x1 – 20x2,

x1 + 2x2 ≤ 6,

-2x1 + 7x2 ≥ 8,

x1 , ≥ 0,

x2 <=> 0.

Решение

Целевая функция будет иметь вид: max z = 13x1 – 20(x2+ – x2–).  

Упражнения

2) Укажите, какая из ниже приведенных задач является стандартной формой задачи…  

Основные свойства ЗЛП

Теорема (о существовании решения). Если допустимое множество X ЗЛП не пусто, а значение её конечно, то эта задача имеет решение.   Определение. Множество, образованное пересечением конечного числа полупространств и гипер­плос­костей, если оно не…

Преобразованная задача

Рассмотрим ЗЛП в канонической форме:

Пусть нам известно некоторые ДБР x системы ограничений (8). Не теряя общности, предположим, что первые m столбцов матрицы A образуют базис данного ДБР.

Обозначим через B базисную матрицу для ДБР x (первые m столбцов матрицы A), а через N – матрицу, составленную из остальных столбцов матрицы A. Тогда

В соответствии с представлением (10) разобьем вектор x на подвекторы xB и xN, т.е.

где xB – вектор базисных переменных, а xN – вектор небазисных переменных.

Систему (8) можно записать в виде:

Так как матрица B – невырожденная, то она имеет обратную матрицу B–1 тогда

Система (12) эквивалентна системе (11).

Теперь разобьем вектор c на подвекторы cB и cN, в соответствии с разбиением (10) матрицы A.

Тогда задачу (7)–(9) можно записать в виде:

Подставим значение xB в ЦФ задачи:

Тогда исходная задача может быть представлена в виде:

Получили так называемую преобразованную задачу. Обозначив

можно записать преобразованную задачу следующим образом:

Так как xN=0, то xB принимает числовое значение β, а ЦФ – значение cBTβ. Однако, в преобразованную задачу включаются все члены правых частей уравнений (не смотря на то, что xN=0), т.к. они указывают на то, что произойдет с ЦФ и xB, если один из элементов вектора xN увеличивается, начиная с нуля.

Иногда задачу (13)-(15) называют диагональной формой исходной задачи, соответствующей ДБР x, а система (14) называется диагональной системой относительно переменных x1,x2,…,xm. Система названа диагональной, потому что представима в виде:

Очевидно, что наше ДБР .

 

Способ перехода от одного ДБР к другому

и запишем систему ограничений преобразованной задачи по столбцам: .

Условие оптимальности ДБР

Обозначим этот вектор через dN. Его j-ый элемент определяется так: Если относительная оценка (dN)j, то небазисной переменной (xN)j положительна или равна нулю, но значение ЦФ не…

Схема симплекс-метода

Рассмотренные в разделах 6-7 способы перехода от одного ДБР к другому и теоремы ЛП, позволяют построить так называемый симплекс-метод решения ЗЛП в канонической форме, который имеет сле­дующую схему:

 

Шаг 0. Построение начального ЗЛП.

Пусть задано ДБР x0 исходной ЗЛП (такое ДБР называется начальным). Пусть данному ДБР соот­ветствует базис ß, вектор базисных переменных xB=B–1β, небазисных переменных xN, базисная матрица B, небазисная матрица N.

Шаг 1. Вычисление компонент вектора относительных оценок небазисных переменных.

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

Если выполняется dN≥0, то прекратить вычисления – текущее ДБР является решением исходной задачи. Иначе – перейти на шаг 3.

Шаг 3. Выбор небазисной переменной (xN)p, вводимой во множество базисных переменных.

Выбрать p, для которого (dN)p<0 (обычно p соответствует максимальная по модулю отрицательная компонента dN).

Шаг 4. Выбор базисной переменной, выводимой из множества базисных переменных.

Вычислить a*p=B–1a*p (пересчет столбца вводимого в базис).

Если a*p<0, то прекратить вычисления – целевая функция не ограничена сверху.

Выбрать q, для которого выполняется , т.е. переменная (xB)q будет выведена из множества базисных переменных.

Шаг 5. Операция замещения.

Построить базис нового ДБР путем замены q-го столбца a*p текущего базиса ß на столбец a*p. Построить новые базисную матрицу B и небазисную матрицу N. Найти новые значения базисных переменных xB=B–1b и ЦФ cBTβ.

Перейти на шаг1.

 

 

Пример 4

Дана система ограничений:

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

,

,

. ?

если да , то какие решения им соответствуют:

Решение. Базисом β матрицы А называется набор из линейно-независимых столбцов β= .

Решение называется допустимым базисным решением если оно является базисным и все его компоненты не отрицательны.

В нашей задаче m=3, n=5. То есть количество претендентов на базис в нашей задаче будет не более, чем .

а) Рассмотрим первое множество векторов -. Составим матрицу из этих векторов, если её детерминант будет отличен от нуля, то эти векторы составляют базис:

.

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

Соответствующее базисное решение имеет вид:

- небазисные переменные переменные

b) Рассмотрим множество векторов - .

Теперь составим матрицу из соответствующих векторов и найдём её определителю:

Значит множество векторов является базисом. Найдём соответствующее ему базисное решение, для этого выпишем уравнения системы с учетом того, что :

Итак, данному базису соответствует решение:

базисные переменные
небазисная переменная
базисная переменная
небазисная  

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

с) Рассмотрим множество векторов -.

Составим матрицу из этих векторов,

Значит множество векторов является базисом.

Выпишем уравнения системы с учетом того, что :

Таким образом, соответствующее базисное решение таково:

- небазисые переменные
- базисные переменные
- базисная переменная

Итак, базису соответствует решение, у которого одна переменная отрицательна, следовательно, имеем недопустимое базисное решение.

 

Табличный симплекс-метод

, ,

Схема табличного симплекс-метода

Шаг 0. Начальный шаг

Построить начальное ДБР исходной задачи.

Построить соответствующую этому ДБР симплекс-таблицу.

 

Шaг 1. Проверка условия оптимальности

ЕСЛИ коэффициенты z-строки

неотрицательны - в случае задачи на максимум

(неположительны - в случае задачи на минимум),

ТО прекратить вычисления: текущей симплекс-таблице соответствует оптимальное ДБР.

 

Шаг 2. Выбор переменной, вводимой в базис.

Среди коэффициентов выбрать отрицательный.

Пусть мы выбрали .

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

 

Шаг 3. Выбор переменной, выводимой из базиса

ЕСЛИ все коэффициенты ведущего столбца неположительные, то прекратить вычисления: целевая функция не ограничена сверху.

ИНАЧЕ выбрать переменную , которой соответствует минимум в выражении

.

-ая строка называется ведущей.

Элемент таблицы на пересечении ведущих строки и столбца называется ведущим элементом.

Шаг 4. Переход к новому ДБР

В столбце «Базисные переменные» в q-ой строке записать переменную .

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

 

Перейти на шаг 1.

 

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

Рассмотрим реализацию симплекс-метода на следующем примере.

Пример 10.1

Приведем задачу к канонической форме. Для этого введем в ограничения остаточные переменные .

Пространство решений данной задачи показано на рис.1.

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

 

 
 

Рисунок 1

Каждую точку пространства решений задачи (20)-(24) можно определить с помощью переменных x1,x2,s1,s2,s3,s4, фигурирующих в модели канонической формы. Заметим, что при si=0 (i=1,…,4), ограничения модели эквивалентны равенствам, которые представляются соответствующими ребрами пространства решений. Например, при s1=0 первое ограничение принимает вид равенства –2x1+x2=2, которое представляется ребром BС. Увеличение переменных si будет соответствовать смещению допустимых точек с границ пространства решения в его внутреннюю область.

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

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

Таблица 2

Вершина Переменные
нулевые ненулевые
A x1,x2 s1,s2,s3,s4
B s1,x1 x2,s2,s3,s4
C s1,s2 x1,x2,s3,s4
D s2,s3 x1,x2,s1,s4
E s3,s4 x1,x2,s1,s2
F s4,x2 x1,s1,s2,s3

 

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

– каноническая модель содержит m=4 основных уравнений и n=6 неизвестных, поэтому в каждой из вершин две (n-m) переменные должны иметь нулевые значения;

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

Приступим к рассмотрению табличного симплекс-метода для решения задачи (20)-(24).

В качестве начального ДБР используется решение, в котором n-m=6-4=2 переменные должны быть небазисными, т.е. принимаются равными нулю. При этом должна быть обеспечена допустимость полученного решения. В рассмотренном случае подстановка x1=x2=0 сразу приводит к следующему результату s1=2, s2=4, s3=36, s4=8, т.е. решение допустимо. Поэтому ДБР (0, 0, 2, 4, 36, 8)T, которому соответствует точка А(0,0), можно использовать как начальное допустимое решение. Преобразовав уравнение целевой функции так, чтобы его правая часть стала равной нулю, можно убедиться, что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение (это имеет место во всех случаях, когда начальный базис состоит из остаточных переменных).

Полученные результаты удобно представить в виде таблицы.

Таблица 3

БП x1 x2 s1 s2 S3 s4 Решение
z -1 -3/2
s1 -2
s2
s3
s4

 

Условие оптимальности. Если в задаче максимизации (минимизации) все небазисные переменные в z-уравнении имеют неотрицательные (неположительные) коэффициенты, полученное решение является оптимальным.

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

Анализируя z-уравнение, видно, что обе небазисные переменные x1,x2, равные нулю, имеют отрицательные коэффициенты. Это эквивалентно наличию положительных коэффициентов при этих переменных в исходной целевой функции. Так как мы имеем дело с задачей максимизации, значение z может быть улучшено при увеличении либо x1, либо x2. Применяя условие оптимальности к исходной таблице, выбираем в качестве вводимой в новый базис переменную x2.

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

Выводимая переменная должна быть выбрана из совокупности текущих базисных перемен­ных: s1,s2,s3,s4. Процедура выбора исключаемой переменной предполагает проверку условия допустимости. В качестве выводимой переменной выбирается та из переменных текущего базиса, которая первая обращается в ноль при введении вводимой переменной.

Пусть x2 увеличилось на 1, это приведет к следующему:

– s1 уменьшится на 1;

– s2 уменьшится на 1;

– s3 уменьшится на 7;

– s4 уменьшится на 1.

Пусть x2 увеличилось на 2, тогда:

– s1 уменьшится на 2 (и станет равной 0);

– s2 уменьшится на 2 (и станет равной 2);

– s3 уменьшится на 14 (и станет равной 22);

– s4 уменьшится на 2 (и станет равной 6).

При этом переменная s1 обратится в ноль. Дальнейшее увеличение x2 приведет к тому, что переменная s1 станет отрицательной, а это значит, что решение станет недопустимо. Предел роста переменной x2: 2/1=2.

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

Следующий шаг симплекс-метода – получение нового ДБР.

 

Процесс получения нового ДБР осуществляется методом Жордана-Гаусса и включает вычислительные процедуры двух типов:

 

Тип 1. Формирование ведущего уравнения:

 

Тип 2. Формирование всех других уравнений, включая z –уравнение:

Итерация 1.

В нашем примере ведущая строка (s1-строка) делится на 1, т. к. ведущий элемент равен 1. В табл.4 показана новая ведущая строка, где вводимая (небазисная ) переменная x2 заменила исключаемую переменную s1. В столбце “Решение” получаем значение переменной x2 (=2).

Таблица 4

БП x1 x2 s1 s2 s3 s4 Решение
z              
x2 -2
s2              
s3              
s4              

 

 

Вычисляем элементы остальных строк таблицы.

 

Z-строка.

–(–3/2) × Новая ведущая строка:(-3 3/2 3/2 0 0 0 | 3) =Новая z-строка:(-4 0 3/2 0 0 0 | 3) БП x1 x2 …  

Контрольные вопросы

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

2. Пользуясь графическим представлением пространства решений ЗЛП (см. рисунок 1), определить, сколько потребуется итераций для нахождения оптимального решения (точка E), если в исходной симплекс-таблице в качестве вводимой в базис переменной будет выбрана x1.

3. Используя таблицу 10, содержащую оптимальное решение задачи, определите исключаемую переменную и соответствующее изменение величины z, если в качестве новой базисной переменной будет выбрана:

3.1) переменная s3,

3.2) переменная s4.

4. Какой вывод следует из результатов вопроса в)?

5. На рисунке 2 показано пространство допустимых решений трёхмерной задачи ЛП с вершинами A, B, … , J.

5.1) Являются ли следующие пары вершин смежными: (A, B), (B, D), (E, H), (A, I)?

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

 

A®B®G®H.

A®E®I®H.

A®C®E®B®A®D®H.

 

x3

D G

J H


F B

A I x1

 
 


CE

Рисунок 2

 

6. Пусть в задаче ЛП, которой соответствует пространство допустимых решений, показанное на рис.2, все ограничения являются неравенствами типа “≤”, а все исходные переменные задачи (т.е. x1, x2 и x3) неотрицательны. Обозначим через s1, s2, s3 и s4 дополнительные (неотрицательные) переменные, ассоциируемые с ограничениями, представленными плоскостями CEIJF, BEIHG, DFJHG и IJH соответственно. Определите базисные и небазисные переменные для каждой вершины пространства допустимых решений.

7. Пусть в задаче ЛП, для которой пространство допустимых решений представлено на рис. 2, реализация симплекс-метода начинается в точке A. Определите вводимую переменную на первой итерации симплекс-метода, а также её значение и значение целевой функции, если целевая функция имеет следующий вид:

a) Максимизировать z = x1 – 2x2 + 3x3.

b) Максимизировать z = 5x1 + 2x2 + 4x3.

c) Максимизировать z = -2x1 + 7x2 + 2x3.

d) Максимизировать z = x1 + x2 + x3.

Искусственное начальное решение

В рассмотренной ранее вычислительной схеме симплекс-метода для получе­ния начального базисного решения использовались остаточные переменные. Однако, когда исходное ограничение записано в виде "=" или имеет знак "≥", нельзя сразу же получить допустимое начальное ба­зисное решение. Покажем это на примере.

Пример 11.1

Запишем в канонической форме:

Таким образом, имеем 3 уравнения, содержащих 4 неизвестных. Это означает, что каждо­му базисному решению соответствует одна небазисная переменная (равная нулю). В отличие от случая, когда каждое уравнение содержит остаточную переменную, в данной ситуации уже нельзя быть уверенным в том, что при нулевом значении одной из переменных все базисные переменные будут неотрицательными. При выборе переменной, которой следует придать нулевое значение, можно использовать метод проб и ошибок.

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

Идея использования искусственных переменных достаточно проста. Она предполагает вклю­чение неотрицательных переменных в левую часть каждого из уравнений, не содержащих “очевидных” начальных базисных переменных (т.е. тех переменных, которые входят только в одно уравнение с положительным коэффициентом, а в симплекс-таблице им соответствуют единичные столбцы [0 0 1 0 … 0]T).

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

Для построения требуемой схемы вычислений можно применить следующий прием: наложить “штраф” за использование искусственных переменных, вводимых в целевую функцию. Разработаны два тесно связанных между собой метода получения стартовой точки, в которых ис­пользуются “штрафование” искусственных переменных:

1) М-метод (или метод больших штрафов);

2) двухэтапный метод.

 

М - метод

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

Двухэтапный метод

Например: М=100000. Тогда коэффициенты в z-уравнении примера 2: (-4+700000) и (-1+400000). Из-за большой величины М вклад исходных ко­эффициентов (4… Двухэтапный метод позволяет избежать этих затруднений. При использовании этого… Введение искусственных переменных может интерпретироваться как введение в модель полезных для нас изменений (невязок).…

Вырожденность

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

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

Вырожденное оптимальное решение

Пример 12.1

 
 

 

Графическое решение. Рассмотрим рисунок, иллюстрирующий графический способ решения задачи (рис.12.1).

Рисунок 12.1

 

Через точку оптимума (x1=3, x2=4) проходят три прямые. Задача содержит только две переменные, поэтому такую точку обычно называют переопределенной, так как для ее идентификации необходимы только две прямые. Отсюда следует, что одно из ограничений модели является избыточным. Исходя из того, что некоторые ресурсы не нужны для достижения поставленной цели, может оказаться весьма полезной для практической реализации результатов исследования. Не существует надежных способов обнаружения избыточных ограничений непосредственно из данных исходной задачи.

Табличный симплекс-метод. Для того чтобы построить начальную симплекс-таблицу нужно привести задачу к канонической форме. Так как все ограничения задачи имеют вид ”меньше либо равно”, то для приведения к канонической форме необходимо добавить остаточные переменные s1, s2, s3к ограничениям (25), (26), (27) соответственно.

После приведения к канонической форме задача примет вид:

Запишем начальную симплекс-таблицу.

Итерация 0.

Таблица 16

БП x1 x2 s1 s2 s3 Решение Отношения
z -2 -3  
s1
s2
s3

Переменная x2 вводится в базис. Переменная s2 выводится из базиса.

Итерация 1.

Таблица 17

БП x1 x2 s1 s2 s3 Решение Отношения
z -2  
s1 -1
x2
s3 -3

Переменная x1 вводится в базис. Переменная s1 выводится из базиса.

Итерация 2.

Таблица 18

БП x1 x2 s1 s2 s3 Решение
z
x1 -1
x2
s3 -2 -1

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

 

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

 

С точки зрения теории решения ЗЛП, вырожденность приводит к следующим двум последствиям:

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

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

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

 

Промежуточное вырожденное решение

Пример 12.2

 

Графическое решение.

Как видно на рис.3 через точку оптимума проходят две прямые. Однако, при выполнении итераций симплекс-метода (двигаемся в сторону наибольшего увеличения целевой функции), вначале мы попадаем в точку x1=4, x2=0, где имеет место вырожденность решения, так как через эту точку проходят три прямые.

 

Рис.12.2

 
 

Табличный симплекс-метод. Приведем нашу систему к канонической форме.

Итерация 0.

Таблица 19

БП x1 x2 s1 s2 s3 s4 Решение Отношения
z -5 -4  
s1
s2
s3
s4

Переменная x1 вводится в базис, переменная s3 выводится из базиса.

Итерация 1.

Таблица 20

БП x1 x2 s1 s2 s3 s4 Решение Отношения
z -4  
s1 -1
s2 -2
x1
s4 -4

Переменная x2 вводится в базис. Переменная s2 выводится из базиса.

Итерация 2.

Таблица 21

БП x1 x2 s1 s2 s3 s4 Решение Отношения
z -3  
s1 -1
x2 -2
x1
s4 -1 -2

Переменная s3 вводится в базис. Переменная s1 выводится из базиса.

Итерация 3.

Таблица 22

БП x1 x2 s1 s2 s3 s4 Решение
z
s3 -1
x2 -1
x1 -1
s4 -3

 

Хотя состав базисных и небазисных переменных на итерациях 1 и 2 различен, значения всех переменных и целевой функции не изменяется, а также имеются базисные переменные равные нулю. Следовательно, здесь имеет место вырожденность. На итерации 3 целевая функция увеличивается, ни одна из базисных переменных не равна нулю, все переменные z-строки больше либо равны нулю, то есть, получаем оптимальное невырожденное решение.

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

 

Особые случаи, возникающие при применении двухэтапного мтода

Рассмотрим примеры особых случаев, которые встречаются при решении задачи двухэтапным симплекс-методом. Пример 12.3 (Вырожденность). Пусть имеем математическую модель:

Контрольные вопросы

1. Сколько избыточных ограничений соответствует вершине пространства решений для ЗЛП с двумя переменными, если на некоторой итерации симплекс-метода три базисные переменные равны нулю?

2. Сколько гиперплоскостей должно проходить через угловую точку в случае n-мерной ЗЛП, чтобы соответствующее решение было вырожденным?

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

 

Альтернативные оптимальные решения

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

Пример 13.1

 
 

Графическое решение.

Рис.4

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

Табличный симплекс-метод.

Приведем задачу к канонической форме:

Итерация 0.

Таблица 23

БП x1 x2 s1 s2 s3 Решение Отношения
z -1 -1  
s1
s2 13,5
s3 -1

 

Переменная x1 вводится в базис. Переменная s3 выводится из базиса.

Итерация 1.

Таблица 24

БП x1 x2 s1 s2 s3 Решение Отношения
z -2  
s1 -1
s2 -2 2,7
x1 -1

 

Переменная x2 вводится в базис. Переменная s1 выводится из базиса.

 

Итерация 2.

Таблица 25

БП x1 x2 s1 s2 s3 Решение Отношения
z  
x2 1 / 2 -1 / 2
s2 -7 / 2 3 / 2
x1 1 / 2 1 / 2

Переменная s3 вводится в базис. Переменная s2 выводится из базиса.

Итерация 3.

Таблица 26

БП x1 x2 s1 s2 s3 Решение
z
x2 -2 / 3 1 / 3
s3 -7 / 3 2 / 3
x1 5 / 3 -1 / 3

 

Оптимум, соответствующий точке B (z=6), получен на итерации 2. Каким образом по результатам этой итерации можно узнать о наличии альтернативных оптимальных решений? Рассмотрим z-строку. Нулевые значения коэффициента небазисной переменной s3 свидетельствует о том, что ее включение в базис не изменит значения целевой функции, но приведет к изменению значений других переменных. Именно это и происходит на итерации 3, когда s3 вводится вместо s2. В результате имеем новое оптимальное решение, соответствующее точке C.

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

B: x1=1, x2=5,

C: x1=5, x2=1.

Полагая 0≤ λ ≤1, можно выразить координаты каждой точки отрезка BC:

 

Признак наличия бесконечного множества решений ЗЛП. Нулевое значение коэффициента небазисной (-ых) переменной (ых) в z-строке.

 

Неограниченность пространства решений и целевой функции

Пример 14.1

Графическое решение.

 
 

Рис.5

 

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

 

Табличный симплекс-метод. Приведем задачу к каноническому форме:

 

Запишем начальную симплекс-таблицу.

 

Таблица 27

БП x1 x2 s1 s2 Решение
z -1 -1
s1 -1
s2 -4

 

Как видно из полученной таблицы, отрицательные коэффициенты z-строки при переменных x1и x2 равны по абсолютной величине. Следовательно, можно на этом шаге вводить в базис как переменную x1 так и переменную x2. Рассмотрим x1.

Итерация 0.

Таблица 28

БП x1 x2 x1 x2 Решение Отношения
z -1 -1  
s1 -1
s2 -4

`

Переменная x1 вводится в базис. Переменная s2 выводится из базиса.

Итерация 1.

Таблица 29

БП x1 x2 x1 x2 Решение
z -5
s1 -2
x1 -4

 

На второй итерации возникла ситуация: имеется отрицательный коэффициент z-строки при переменной x2. Заметим, однако, что во всех ограничениях коэффициенты при x2 отрицательны (переменные s1 и x1 не могут быть выведены из базиса, т.к. имеют отрицательные коэффициенты в ведущем столбце). Это означает, что x2 можно бесконечно увеличивать, не нарушая ни одного из ограничений модели. Так как прирост переменной x2 на 1 приводит к увеличению функции z на 5, становится ясно, что при неограниченном возрастании x2 будет неограниченно увеличиваться и значение целевой функции z. Поэтому, не приводя дальнейших вычислений, можно заключить, что решение сформулированной задачи не ограниченно.

Теперь вернемся к начальной симплекс-таблице. Будем вводить в базис переменную x2 и посмотрим, изменится ли ситуация.

Итерация 0.

Таблица 30

БП x1 x2 s1 s2 Решение Отношения
z -1 -1  
s1 -1
s2 -4

 

Переменная x2 вводится в базис. Переменная s1 выводится из базиса.

Итерация 1.

Таблица 31

БП x1 x2 s1 s2 Решение
z -3/2 1/2
x2 -1/2 1/2
s2 -1

 

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

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

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

Контрольные вопросы

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

2. Всегда ли можно выявить факт неограниченности решения на начальной итерации симплекс-метода?

 

Отсутствие допустимых решений

С точки зрения практики отсутствие допустимых решений следует рассматривать как свидетельство того, что модель построена некорректно, так как…

Пример 15.1


Графическое решение.

 
 

Рис.6

На рисунке, иллюстрирующем графическое решение, видно, что области допустимых решений, определяемые ограничениями (41) и (42), не пересекаются. Из этого следует, что данная задача не имеет допустимых решений.

Табличный симплекс-метод. Так как не все ограничения задачи имеют вид ”≤”, то для приведения к канонической форме необходимо:

– добавить остаточные переменные s1, s2 к ограничениям (41), (42) соответственно. Причем переменную s2 вводим со знаком "-", так как ограничение (42) имеет вид ”≥”;

– в ограничение (42) добавить искусственную переменную R. Также вводим R в целевую функцию с коэффициентом -M, где M>>1.

После приведения к канонической форме задача примет вид:

Выразим из ограничения (45) R:

Подставим в целевую функцию:

 

Составим симплекс-таблицу.

Итерация 0.

Таблица 32

БП x1 x2 s1 s2 R Решение Отношения
z -2-M -1-M M -3M  
s1
R -1

Переменная x1 вводится в базис. Переменная s1 выводится из базиса.

Итерация 1.

Таблица 33

БП x1 x2 s1 s2 R Решение
z 3+M 2+M M 4-M
x2
R -1 -1 -1

 

Коэффициенты z-строки положительны, следовательно, имеем оптимальное решение. Однако искусственная переменная остается в базисе, а это свидетельствует о том, что данная задача не имеет допустимых решений.

Признак отсутствия допустимых решений ЗЛП. В оптимальном решении ЗЛП искусственные переменные имеют не нулевое значение.

 

Пример 15.2 (Отсутствие допустимых решений).

 

Пусть имеем математическую модель:

max z= 4x1 + 3x2 (12.26)

2x1 + 3x2 £ 6 (12.27)

3x1 + 2x2 ³ 12 (12.28)

x1,x2 ³0 (12.29)

Приведем задачу к канонической форме:

max z= x1 + x2 + 0s1 +0s2 (12.30)

2x1 + 3x2 +1s1 = 6 (12.31)

3x1 + 2x2 -1s2 = 12 (12.32)

x1,x2 ,s1,s2³0 (12.33)

(4.12.27)
(4.12.28)
x2
x1
– Рис.4.12.4

 

Этап 1

1. Вводим искусственные переменные в ограничения типа “³” и “=”. В нашей задаче это ограничение (12.28).

Тогда модель (12.30)-(12.33) будет иметь такой вид:

min z= 4x1+ 3x2 +0s1 +0s2 +0R1 (12.34)

2x1+ 3x2 +1s1 = 6 (12.35)

3x1+ 2x2 -1s2 +R1 = 12 (12.36)

x1,x2 ,s1,s2³0 (12.37)

2. Выразим R1 из уравнения (12.36):

R1 = 12 - 3x1- 2x2 +1s2

Получим такую целевую функцию:

r = R1 = 12 - 3x1- 2x2 +1s2

Перепишем целевую функцию в виде:

r + 3x1 + 2x2 -1s2 = 12

 

3. Построим начальную таблицу двухэтапного симплекс-метода.

 

Базисные переменные x1 X2 S1 s2 R1 Решение  
r(min) -1  
Z -4 -3  
s1 2
R1 -1

 

Согласно условия оптимальности вводим в базис переменную x1 и, согласно условия допустимости, выводим из базиса переменную s1. Получим таблицу:

Базисные переменные x1 x2 s1 s2 R1 Решение
r(min) -5/3 -3/2 -1
z
x1 3/2 1/2
R1 -5/2 -3/2 -1

На данном этапе все коэффициенты r-строки отрицательные, то есть минимум найден, но искусственная переменная находится в базисе и минимум функции не равен 0. Это свидетельствует о том, что данная задача не имеет допустимых решений.

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

Или так: Если минимальное значение новой целевой функции найдено, и хотя бы одна искусственная переменная не выведена из базиса, то начальная задача не имеет допустимых решений, закончить расчет.

 


Задания для контрольной работы

Найти решение ЗЛП.

 

N a b c d * e f g Ù h k l L m  
1. ³ £          
2. ³ £          
3. £ -1 ³          
4. -1 -3 ³ -4 £          
5. £ -4 ³          
6. -1 £ -1 ³          
7. -1 ³ £          
8. ³ £          
9. ³ £          
10. -1 ³ £          
11. ³ 3/2 £          
12. ³ £          
13. £ -6 £ £  
14. -2 ³ £ -1 ³  
15. -2 3/2 ³ -2 ³ 3/2 3/4 £  
16. £ -1 3/2 ³          
17. £ -1 ³          
18. £ -1 ³          
19. £ ³          
20. £ ³          
21. £ ³          
22. £ -4 ³          
23. -2 ³ -1 £         *
24. £ -1 ³         *
25. -4 -2 £ -2 ³         *
26. -2 3/2 ³ -4 £         *
27. -5 -10 £ ³         *
                               
28. £ ³ -2 £  
29. -2 -4 £ ³ £  
30. -3 -1 £ ³ £  
31. ³ -4 £          
32. -2 £ ³          
33. -1 £ ³          
34. -1 £ ³          
35. -1 £ -3 £          
36. -2 £ -1 ³          
37. 3/2 ³ -2 £          
38. 3/2 ³ -4 £         *
39. -10 £ ³         *
40. ³ -1 £         *
41. ³ -1 ³         *
42. -1 £ ³         *
43. -3 £ 3/2 ³ -2 £  
44. ³ -2 ³ 3/2 3/4 ³ *
45. ³ ³ ³ *
46. £ ³          
47. £ -3 ³          
48. -1 ³ £          
49. £ ³          
50. -2 ³ -1 ³          
51. £ ³          
52. £ -3 ³          
53. £ -1 ³          
54. -2 ³ -2 ³          
55. £ -1 -2 ³          
56. -1 ³ -2 £          
57. £ ³          
58. £ ³ -1 ³  
59. -2 -1 ³ £ £  
60. £ -2 ³ ³ *

 

 

Список литературы

1. Акоф Р., Сасиени М. Основы исследования операций. – М.: Мир, 1971. – 533 с.

2. Ашманов С.А. Линейное программирование. – М.: Наука, Гл. ред. физ.-мат. литературы, 1981.– 340 с.

3. Вагнер Г. Основы исследования операций: В 3-х т. – М.: Мир, 1973. – Т. 2. – 501 с.

4. Вентцель Е.С. Исследование операций: задачи, принципы, методология. – М.: Наука, Гл. ред. физ.-мат. лит-ры, 1980. – 208 с.

5. Емольев Ю.М., Ляшко И.И., Михалевич В.С., Тюптя В.И. Математические методы исследования операций. – К.: Вища шк., 1978. – 312 с.

6. Исследование операций: В 2-х т. Т.1. Методологические основы и математические методы. /Под ред. Дж. Моудера, С. Элмаграби. – М.: Мир, 1981. – 712 с.

7. Калихман и. Л. Линейная алгебра и программирование. – М.: Высш. шк., 1967. – 428 с.

8. Курицкий Б.Я. Оптимальное решение? – Это очень важно! – Л.: Машиностроение, 1984. – 126с.

9. Ляшенко И.Н., Карагодова Е.А., Черникова Н.В. Шор Н.З. Линейное и нелинейное программирование. – К.: Вища шк., 1975. – 372 с.

10. Муртаф Б. Современное линейное программирование. Теория и практика. – М.: мир, 1984. – 224 с.

11. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. – М.: Мир, 1985. – 512 с.

12. Таха Х. Введение в исследование операций: В 2-х т. – М.: мир, 1985.

– Конец работы –

Используемые теги: методические, указания, дисциплине, Математические, Методы, исследования, операций, Информационные, управляющие, системы, технологии0.088

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: МетодичЕСКИЕ УКАЗАНИЯ по дисциплине Математические методы исследования операций Информационные управляющие системы и технологии

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

МЕТОДИЧЕСКИЕ УКАЗАНИЯ по технико-экономическому обоснованию дипломных проектов и работ специальности 220200 Автоматизированные системы обработки информации и управления Методические указания для специальности 2202 Автоматизированные системы обработки инфо
Российский химико технологический университет... им Д И Менделеева... Новомосковский институт Издательский центр...

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

Методическая разработка по дисциплине: Информационные системы и технологии в учете
Министерство образования науки молодежи и спорта Украины... Харьковская национальная академия городского... Жилищно коммунальный техникум...

Лекции по дисциплине Устройство и функционирование информационных систем Раздел 1. Информационные системы. Основные понятия и классификация
Раздел Информационные системы Основные понятия и классификация... Тема Информационные системы Основные понятия и... В данной теме рассматриваются общие понятия относящиеся к операционным системам определяются их типы и базовые...

Методические указания к семинарским занятиям Методические указания по самостоятельной работе Банк тестовых заданий в системе UniTest
ВСЕОБЩАЯ ИСТОРИЯ ИСКУССТВА... Учебная программадисциплины gt Курс лекций Методические... Лекция Основные понятия истории искусства ч...

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ИЗУЧЕНИЮ ДИСЦИПЛИНЫ, ВЫПОЛНЕНИЮ САМОСТОЯТЕЛЬНОЙ РАБОТЫ И ВЫПОЛНЕНИЮ РЕФЕРАТОВ Информационные технологии в коммерческой деятельности
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ... ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ... Институт управления...

МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторным работам по дисциплине: «Релейная защита и автоматикаэлектроэнергетических систем»
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования... тюменский государственный нефтегазовый университет... Институт кибернетики информатики и связи...

МЕТОДИЧЕСКИЕ УКАЗАНИЯ МЕТОДИЧЕСКИЕ УКАЗАНИЯ УЧЕБНО-ИССЛЕДОВАТЕЛЬСКИХ РАБОТ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ...

ДОКЛАД по дисциплине Теория игр и исследование операций На тему: Теория игр, графический метод в теории игр
МИНОБРНАУКИ РОССИИ... ФГБОУ ВПО ВОСТОЧНО СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕХНОЛОГИЙИ УПРАВЛЕНИЯ...

МЕТОДИЧЕСКИЕ УКАЗАНИЯ по курсу ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ В ПРОЕКТИРОВАНИИ СТВОЛЬНОГО ОРУЖИЯ
Федеральное государственное бюджетное образовательное учреждение... Высшего профессионального образования... ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ...

0.036
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам