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

n5.doc





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

Найти

или в матричной форме

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

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


§ 6.2. Графический метод решения задачи линейного программирования.
Выясним алгебраический смысл системы равенств в задаче линейного программирования. Итак, каноническая задача:

Найти

(6.2.1)

или при

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

(6.2.2)

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





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

Ясно, что Тогда Пусть свободными переменными будут Выразим через них базисные переменные и целевую функцию Получим

Кроме того . Итак, исходную задачу можно перефразировать следующим образом.

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



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

Целевая функция тоже изобразится

прямой. Вектор нормали к целе-

вой функции . Видно,

что максимум достигается в точ-

ке многоугольника ограниче-

ний. Координаты этой точки на-

ходятся из системы уравнений

Отсюда

Значение целе-

вой функции в точке максимума

равно
§ 6.3. Определения и теоремы, лежащие в основе симплекс-метода.
Линейная функция (линейная форма) называется целевой функцией задачи линейного программирования.

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

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

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

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

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

называется множество точек

, удовлетворяющих уравнению

, где - фиксирован-

ная точка прямой, - направляющий

вектор, причем ||. Рассмотрим теперь

отрезок . Из рисунка видно, что

- аналог вектора .

Подставим эту формулу в предыдущее выражение, тогда Итак, уравнение отрезка имеет вид

(6.3.1)

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

Например, отрезок есть выпуклая комбинация двух векторов , так как

Множество точек называется выпуклым, если оно вместе с двумя любыми точками содержит все точки отрезка

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


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

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

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

Доказательство.

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

Следовательно, - допустимое решение.

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

Доказательство (для минимума целевой функции).

Пусть дан многогранник ограничений (смотри-

те рисунок слева). , ,…, - угловые точки,

а оптимальный план . Ели - угловая точка,

то теорема доказана. Если - внутренняя точка,

тогда ее можно представить как выпуклую линей-

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

Теорема 3. Если в множестве допустимых решений имеются крайние точки, то их число конечно.

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

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

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

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

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

рите рисунок слева). Видно, что целевая

функция достигает минимума в точке ,

область имеющей координаты . Мини-

допустимых мальное значение целевой функции в точ-

решений ке равно .



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

(6.5.1)

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

(6.5.2)

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

(6.5.3)

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

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