Шапорев С.Д. Дискретная математика - файл n7.doc

приобрести
Шапорев С.Д. Дискретная математика
скачать (1595.4 kb.)
Доступные файлы (14):
n1.doc1008kb.24.06.2000 17:47скачать
n2.doc580kb.29.02.2000 18:08скачать
n3.doc957kb.07.03.2000 15:50скачать
n4.doc492kb.24.06.2000 17:37скачать
n5.doc1198kb.19.04.2000 15:24скачать
n6.doc985kb.19.04.2000 21:35скачать
n7.doc771kb.07.05.2000 17:26скачать
n8.doc992kb.08.05.2000 16:38скачать
n9.doc217kb.08.05.2000 19:26скачать
n10.doc1581kb.26.03.2000 20:59скачать
n11.doc1011kb.31.03.2000 22:04скачать
n12.doc1025kb.31.03.2000 22:09скачать
n13.doc1691kb.05.04.2000 16:10скачать
n14.doc960kb.09.04.2000 12:05скачать

n7.doc





(6.6.2)

Найдем ее минимум при условиях симплекс – методом. В этой задаче допустимое базисное решение легко находится. Действительно, набор может служить набором свободных неизвестных. Тогда решение вида является допустимым.

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

(6.6.3)

является равенство нулю минимума вспомогательной целевой функции

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

Рассмотрим следующий пример.

Найти при ограничениях



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

Выбираем из строки наибольший элемент. Этот элемент равен семи. Следовательно, перейдет из свободных в базисные переменные. Разделим теперь элементы столбца со свободными членами на соответствующие элементы столбца со стрелкой над ним: 10/0=?, 5/2=2.5, 18/5=3.6, 33/7=4.714. Выбираем наименьшее число, это 2.5. Следовательно, перейдет в свободные переменные. Поставим в строке с стрелку вбок. Число, обратное разрешающему элементу , поставим в нижнюю поло-


Базис-

ные пе-

ремен-

ные

Свободные переменные

Свобод-

ные

члены













10

0

1

0

0

0

2

0

0

0

1

0



5

2.5

0

0

2

1/2

0

0

3

1.5

1

0.5



18

-12.5

4

0

5

-5/2

0

0

0

-7.5

2

-2.5



33

-17.5

5

0

7

-7/2

2

0

3

-10.5

4

-3.5



0

0.75

-0.4

0

-0.3

0.15

-0.5

0

-0.8

0.45

-0.2

0.15


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


Базис-

ные пе-

ремен-

ные

Свободные переменные

Свобод-

ные

члены













10

-1.375

1

-1/4

0

0.625

2

0

0

1.875

1

0.125



2.5

0

0

0

1/2

0

0

0

1.5

0

0.5

0



5.5

1.375

4

1/4

-2.5

-0.675

0

0

-7.5

-1.875

-0.5

-0.125



15.5

-6.875

5

-5/4

-3.5

3.125

2

0

-7.5

9.375

0.5

0.625



0.75

0.55

-0.4

0.1

0.15

-0.25

-0.5

0

-0.35

-0.75

-0.05

-0.15


же правила и перейдем к третьей таблице. Именно: 10/1=10, 2.5/0=?, 5.5/4=1.375, 15.5/5=3.1. Минимальное значение равно 1.375, то есть разрешающий элемент . Третья таблица имеет следующий вид.

Базис-

ные пе-

ремен-

ные

Свободные переменные

Свобод-

ные

члены













8.625

4.3125

-0.25

-0.125

0.625

0.3125

2

0.5

1.875

0.9375

1.125

0.5063



2.5

0

0

0

0.5

0

0

0

1.5

0

0.5

0



1.375

0

0.25

0

-0.625

0

0

0

-1.875

0

-0.125

0



8.625

-8.625

-1.25

0.25

-0.375

-0.3125

2

-1

1.875

-1.875

1.125

-1.125



1.3

1.1506

0.1

-0.0625

-0.1

0.1506

-0.5

0.25

-1.1

0.4875

-0.1

0.2813


Четвертая таблица получается аналогичным образом.


Базис-

ные пе-

ремен-

ные

Свободные переменные

Свобод-

ные

члены













4.3125


-0.125


3.125


0.5


0.9375


0.5625




2.5


0


0.5


0


1.5


0.5




1.375


0.25


-0.625


0


-1.875


-0.125




0


-1


-1


-1


0


0




2.456


0.0375


0.056


0.25


-0.631


0.181



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

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

2). В строке с оставшейся все элементы неположительны. Это возможно только тогда, когда свободные и их можно не выводить в базис. Тогда и , следовательно, найдено оптимальное базисное решение.

Продолжим решение примера дальше. Выбросим из таблицы столбцы с и строку с . Столбцы с можно было выбрасывать и раньше, не учитывая их совсем, так как из свободных переменных обратно в базисные переходить не должны. Получим следующую симплекс – таблицу с допустимым базисным решением.


Базис-

ные пе-

ремен-

ные

Свободные переменные

Свобод-

ные

члены







4.313

-1.568

0.938

-0.627

0.563

-0.314



2.5

1.668

1.5

0.667

0.5

0.334



1.375

3.128

-1.875

1.251

-0.125

0.626



2.456

1.053

-0.631

0.421

0.181

0.211


Находится , поэтому из строки с целевой функцией выбираем наименьший элемент. Этот элемент равен –0.631, таким образом, разрешающий элемент . Последняя симплекс – таблица будет такой:


Базис-

ные пе-

ремен-

ные

Свободные переменные

Свобод-

ные

члены







2.745

-0.627


0.249




1.668


0.667


0.334




4.503


1.251


0.501




3.508


0.421


0.392



Дальнейшее движение к максимуму невозможно, так как в строке с целевой функцией нет больше ни одного отрицательного коэффициента. Итак,


§ 6.7. Двойственность в линейном программировании

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

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

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

Ресурс

Продукция





































































































Составить план выпуска продукции, обеспечивающий ее максимальный выпуск по стоимости.

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



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



Многие задачи линейного программирования первоначально ставятся в виде исходных или двойственных задач, поэтому имеет смысл говорить о паре двойственных задач линейного программирования.
§ 6.8. Симметричные и несимметричные двойственные задачи.
В несимметричных двойственных задачах система ограничений исходной задачи задается в виде равенств, а двойственной – в виде неравенств, причем в последней переменные могут быть и отрицательными. Исходная задача записывается в виде

при

(6.8.1)

Двойственная задача в этом случае формируется следующим образом

при

(6.8.2)

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

Исходная задача записывается в виде: найти при следующих ограничениях



Двойственная задача формулируется аналогично: при ограничениях



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


Несимметричные задачи

Исходная задача

Двойственная задача








Несимметричные задачи

Исходная задача

Двойственная задача





Симметричные задачи










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

1). Каждому -му ограничению исходной задачи соответствует переменная двойственной задачи, и, наоборот, каждому -му ограничению двойственной задачи соответствует переменная исходной задачи.

2). Матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием.

3). Свободные члены ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи; аналогично коэффициенты целевой функции исходной задачи совпадают со свободными членами системы ограничений двойственной задачи.

4). Если целевая функция исходной задачи максимизируется, то целевая функция двойственной задачи минимизируется и наоборот.

5). Если в исходной задаче ограничения – неравенства записываются со знаком , то в двойственной задаче со знаком и наоборот.

6). Если на -ю переменную исходной задачи наложено условие неотрицательности, то -е ограничение двойственной задачи будет неравенством, в противном случае -е ограничение будет равенством; аналогично связаны между собой ограничения исходной задачи и переменные двойственной задачи.

Рассмотрим пример. Построить двойственную задачу к следующей задаче линейного программирования.

(6.8.3)

Исходная задача задана в форме 4 (смотрите предыдущую таблицу). Здесь Двойственная задача

будет сформулирована следующим образом

(6.8.4)
§ 6.9. Теоремы двойственности.
Теорема 1. Если из пары двойственных задач одна обладает оптимальным планом, то и другая задача имеет решение, причем для экстремальных значений линейных функций выполняется соотношение или . Если линейная функция одной из задач не ограничена, то другая не имеет решения.

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

Положения второй теоремы могут быть еще более конкретизированы. Именно для симметричной двойственной задачи справедлива

Теорема 3. Для оптимальности допустимых планов пары двойственных задач



необходимо и достаточно, чтобы они удовлетворяли системе уравнений:



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

Теорема 4. В оптимальном решении двойственной задачи значения переменных численно равны частным производным для исходной задачи.

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

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

(6.9.1)

где - элементы матрицы , обратной матрице базиса оптимального плана. Матрица базиса оптимального плана содержит элементы , то есть

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

(6.9.2)

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

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

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

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

Один из самых простых методов устранения зацикливания, так называемый -

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации