- •Глава I. Линейное программирование.
- •Примеры задач линейного программирования.
- •Различные формы задачи лп
- •Определение 3. Каноническая задача лп называется симплексной, если:
- •Связь между различными типами задачи лп.
- •Вначале сведём общую задачу к однородной. В соответствии с определением 1 п.1.3 для этого достаточно каждое ограничение вида равенства:
- •1.5. Графический метод решения задачи лп.
- •1.6. Выпуклые множества на плоскости и в пространстве.
- •1.7. Геометрическая интерпретация однородной задачи линейного программирования.
- •1.8. Симплекс-метод решения задачи линейного программирования.
- •1.8.1. Пример решения задачи линейного программирования симплекс-методом.
- •Алгоритм симплекс-метода.
- •1.9. Геометрическая интерпретация симплекс-метода.
- •1.10. Основные теоремы.
- •1.11. Методы получения 1-го опорного решения.
- •1.12. Пара симметричных двойственных задач.
- •1.13. Правила перехода к двойственной задаче.
- •1.14. Теоремы двойственности.
- •1.15. Экономический смысл двойственных оценок. Методы нахождения двойственных оценок.
- •1.16. Условие устойчивости двойственных оценок.
- •Глава II. Транспортная задача
- •2.1. Замкнутая модель транспортной задачи.
- •2.2. Другие модели транспортной задачи.
- •Глава III. Игровые методы и модели.
- •3.1. Понятие об игровых моделях.
- •3.2. Постановка игровых задач.
- •3.3. Методы и модели решения игровых задач. Принцип минимакса.
- •3.4. Решения игр в смешанных стратегиях.
- •3.5. Геометрический метод.
- •3.6. Метод линейного программирования.
- •3.7. Игровые модели в условиях коммерческого риска.
- •3.8. Игровые модели в условиях коммерческой неопределенности.
- •Контрольные вопросы.
1.6. Выпуклые множества на плоскости и в пространстве.
Определение 1. Множество А Rn называется выпуклым, если с любыми своими двумя точками А оно содержит целиком отрезок их соединяющий:
А А. (1)
Пусть два вектора на плоскости х О у и пусть точка лежит на отрезке . Тогда вектор колинеарен вектору , направлен в одну сторону с ним и не превосходит его по длине. Эти условия могут быть записаны в виде равенства:
, (2)
где
Векторное равенство (2) равносильно системе:
(3)
Система (3) может быть преобразована в равносильную систему:
(4)
где Обозначим Тогда (4) примет вид:
(5)
где
В векторном виде система (5) примет вид:
где (6)
Определение 2. Выпуклой (линейной) комбинацией векторов называется выражение вида:
где все и
Равенство (6) показывает, что каждая точка отрезка является выпуклой комбинацией векторов
Теорема 1. Пересечение любого числа выпуклых множеств является выпуклым множеством.
Доказательство. Пусть - любое семейство выпуклых множеств. Пусть А – их пересечение:
Покажем, что множество А – выпукло. Пусть Тогда для каждого , поскольку А – пересечение всех . Так как - выпукло, то вместе с точками оно содержит и соединяющий их отрезок:
для всех Аi.
Но, отсюда, очевидно, следует, что каждая точка отрезка (а значит и сам отрезок) принадлежит пересечению множеств , то есть множеству А. Итак, А – выпуклое множество. Что и требовалось доказать.
Определение 3. Выпуклой оболочкой множества называется такое выпуклое множество , что:
,
- выпукло .
Лемма 1. Выпуклая оболочка множества А совпадает с пересечением всех выпуклых множеств, содержащих А.
Доказательство. Пусть В0 – пересечение всех выпуклых множеств, содержащих А. Тогда очевидно В0, содержит А. С другой стороны по теореме 1 множество В0 само выпукло. Отсюда следует, что В0= VA, поскольку выполнены свойства 1) и 2).
Лемма 2. Отрезок является выпуклой оболочкой своих концов .
Доказательство. Пусть , то есть множество А состоит из двух элементов . Отрезок является выпуклым множеством и содержит А. С другой стороны каждое выпуклое множество В, содержащее А, содержит по определению выпуклости и весь отрезок . Тем самым показано, что ч т.д.
Лемма 3. Если выпуклое множество содержит векторы , то оно содержит и любую их выпуклую комбинацию:
где
Доказательство. Докажем это по индукции. Для двух точек утверждение леммы практически было доказано выше, поскольку множество выпуклых комбинаций совпадает с отрезком и, следовательно, содержится в В. Пусть утверждение справедливо для всех . Покажем, что оно будет также справедливым и для .
Пусть где
Пусть
и .
Тогда
и
где По предположению индукции Так как и то . Лемма доказана.
Теорема 2. Выпуклая оболочка VA множества А Rn совпадает с множеством всех выпуклых комбинаций, состоящих из конечного числа векторов множества А.
Доказательство: Пусть В0 – множество всех таких комбинаций векторов множества А. Как следует из леммы 3 множество В0 содержится в любом выпуклом множестве В, содержащем А. Осталось показать, что само В0 – выпукло.
Пусть - два вектора множества В0. Тогда , , , .
Пусть - где и Достаточно показать, что , то есть что вектор сам является выпуклой комбинацией векторов из А0. Но это верно, поскольку:
- выпуклая комбинация векторов - так как и ч.т.д.
Отметим, что треугольник и пирамида являются выпуклыми оболочками своих вершин, и, следовательно, каждая их точка является выпуклой комбинацией векторов-вершин.
Определение. Выпуклая оболочка точки в - мерном линейном пространстве называется симплексом.
Предполагается, что точки лежат в общем положении, то есть не содержатся ни в какой гиперплоскости.
Рассмотрим некоторую точку Возможны следующие случаи расположения точки относительно множества В.
Первый случай. На каждой прямой l , проходящей через , можно найти отрезок , лежащий целиком в В и содержащий внутри себя:
. (7)
Второй случай. Существует содержащая прямая , на которой не существует отрезка , удовлетворяющего (7).
Если то ясно, что свойством (7) не обладает ни один отрезок . Если для некоторых прямых проходящих через точку отрезок удовлетворяющий (7), существует, а для других прямых нет, то называется граничной точкой множества В. Вблизи граничной точки лежат как точки множества В, так и точки ему не принадлежащие.
Третий случай.
Определение. Пусть точка и ни для одной прямой l содержащей , не существует отрезка , удовлетворяющего (7). В этом случае называется угловой точкой множества В.
Другими словами любой отрезок, содержащий угловую точку внутри себя, обязательно «высовывается» из множества В.
Замечание.
Условие 2) Из (7) можно заменить в предыдущих рассуждениях на условие: , - то есть можно считать, без ограничения общности, что точка является серединой отрезка , действительно, если существует отрезок, содержащий внутри себя, то существует в нем меньший отрезок, для которого точка является серединой.
Определение. Множество называется замкнутым, если оно содержит все свои граничные точки.
Значение угловых точек для описания выпуклого множества в дает следующая теорема, которую мы приводим без доказательства.
Теорема 3. Замкнутое выпуклое множество является выпуклой оболочкой своих угловых точек.