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

n6.doc





.

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

Далее возможны два случая.

1). Все числа , то есть и, следовательно, Базисное решение оптимальное, задача решена.

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

(6.5.4)

так как все Целевая функция имеет аналогичный вид . Далее опять возможны два случая.

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

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

.

Целевая функция примет вид .

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

(6.5.5)

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

Отметим правила работы по симплекс – методу.

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

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

3). Составить следующую симплекс – таблицу и заполнить ее по своим правилам ( смотрите пример).


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

ремен-

ные

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































































































































4). Выбрать разрешающий элемент по правилу:

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

б). составить отношение везде, где ;

в). выбрать , например, при , - разрешающий элемент.

5). Перейти к следующей симплекс – таблице по правилам работы с симплекс – таблицей (смотрите пример).

6). Перейти к третьему пункту, составив предварительно новую симплекс – таблицу, и так далее до достижения оптимального плана.

Пример. Найти при

Перепишем систему в канонической форме, добавив две новые переменные базисных переменных две, свободных тоже две. Пусть базисными переменными будут , свободными - . Запишем задачу в виде (6.5.3).



Составим симплекс – таблицу и заполним ее. Цифры поставим в верхнюю половину


Базисные

перемен-

ные

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

Свободные

члены







1

2

1

2/3

-2

2/3



3

1

1

1/3

3

1/3



-1

-2

-2

-2/3

2

-2/3


клеточек. В последней строке есть положительное число, это Поставим над столбцом, в котором находится выделенный элемент, стрелку ?. Если бы в последней строке было несколько положительных элементов, то при нахождения минимума целевой функции необходимо выбирать наибольший положительный, а при нахождении максимума – наименьший отрицательный элемент. Поставленная стрелка указывает на ту свободную переменную, которая переходит в базисные. Найдем теперь ту базисную переменную, которую надо перевести в свободные. Для этого разделим элементы столбца со свободными членами на соответствующие элементы столбца со стрелкой над ним: 1:(-2)=-0.5, 3:3=1, -1:2=-0.5. Берем только те строки, где это отношение положительно и выбираем наименьшее число. Это вторая строка. Ставим около нее стрелку вбок. Итак, переменная будет из базисных переведена в свободные переменные. Разрешающий элемент , обведем его кружком. В нижнюю половину этой же клетки поставим обратную величину Умножим элементы этого столбца на , а элементы строки со стрелкой на . Обведем замкнутой линией верхние элементы строки со стрелкой и нижние элементы столбца со стрелкой. Умножим теперь последовательно элементы выделенной строки на первый элемент выделенного столбца и запишем результаты в нижние половинки первой строки. Так же поступим и с третьей строкой: умножим элементы выделенной строки на третий элемент выделенного столбца и результаты запишем в нижнюю половинку третьей строки. Перейдем к следующей симплекс – таблице. Прежде всего в эту таблицу запишем из предыдущей числа из выделенной строки и столбца. В них числа из нижних половинок клеток старой таблицы записываются в верхние половины клеток той же строки и столбца новой таб-


Базисные

перемен-

ные

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

Свободные

члены








3


5/3


2/3





1


1/3


1/3





-3


-8/3


-2/3



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

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

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

(6.6.1)

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

(6.6.2)

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

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