Шапорев С.Д. Дискретная математика - файл n8.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скачать

n8.doc





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


Базис-ные пе-

ремен-

ные

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

Своб.

члены




























































































































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


Базисные пе-

ремен-

ные

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

Свободные члены




























































































































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

Если в этой таблице было более чем одно минимальное отношение , то в новой таблице эти отношения будут различные ( - номер разрешающего столбца), например . Так как , то разрешающий элемент определяется однозначно. Можно показать, что ввиду достаточной малости оптимальному решению новой задачи с возмущенными при помощи свободными членами соответствует оптимальное решение исходной задачи, получаемое из оптимального решения измененной задачи при .
§ 6.11. Целочисленное программирование.
Часто в задаче линейного программирования требуется, чтобы решение было целочисленным, причем предполагаются тоже целыми. Симплекс – метод приводит непосредственно к целочисленному решению лишь для немногих задач. В общем же случае для отыскания оптимального целочисленного решения требуются специальные методы. Они заключаются в подборе дополнительных линейных ограничений, обеспечивающих целочисленность решения.

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

Обратимся опять к геометрической интерпретации. Рассмотрим множество целоцисленных точек многогранника ограничений. Если бы удалось заменить многогранник выпуклой оболочкой его целочисленных точек, то получаемое симплекс – методом оптимальное решение этой видоизмененной задачи было бы, очевидно, целочисленным. Однако построить такую выпуклую линейную оболочку в общем случае трудно. Поэтому обычно строят промежуточный многогранник, охватывающий ее и содержащийся в исходном многограннике ограничений. Построение может осуществляться путем введения на каждом шаге дополнительного ограничения, которое, уменьшая исходный многогранник (отсекая его некоторую часть), не исключает из него целочисленных точек. Гиперплоскость дополнительного линейного ограничения проходит хотя бы через одну целочисленную точку. Через конечное число шагов метод приводит к новой задаче, оптимальное решение которой является одновременно оптимальным целочисленным решением исходной задачи. Этот подход называется методом отсечения. Известны несколько модификаций подобных алгоритмов.

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

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

(6.11.1)

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

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

Вычислим . Так как не целые, то



Тогда Обозначим через величину . Она будет целочисленна и неотрицательна. Действительно,

(6.11.2)

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

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

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

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


Базис-ные пе-

ремен-

ные

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

Своб.

члены










































































































































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

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

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

Рассмотрим числовой пример.

Найти

Сначала решим обычную задачу линейного программирования без учета требования целочисленности. Найдем допустимый вектор, составив и решив дополнительную задачу линейного программирования по алгоритму, описанному в § 6.6.



Исходная симплекс – таблица будет иметь следующий вид.

Базисные

переменные

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

Свободные

члены











6

3

1

1/2

2

1/2

1

1/2

0

0



9

-6

3

-1

2

-1

0

-1

1

0



15

-12

4

-2

4

-2

1

-2

1

0



0

-3

1

-1/2

1

-1/2

0

-1/2

0

0


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


Базисные

переменные

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

Свободные

члены









3

-3/4

1/2

-1/4

1/2

1/4

0

-1/4



3

3/2

2

1/2

-1

-1/2

1

1/2



3

-3

2

-1

-1

1

1

-1



-3

-3/4

1/2

-1/4

-1/2

1/4

0

-1/4


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


Базисные

переменные

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

Свободные

члены







9/4


3/4


-1/4




3/2


-1/2


1/2




-15/4


-1/4


-1/4



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