Общая задача линейного программирования. Основные теоремы. Многоугольник решений.
Теорема 1. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
Ограничениями любой задачи линейного программирования являются либо система линейных уравнений, либо система линейных неравенств. Совокупность решений таких систем при условии их совместности, образует выпуклые множества с конечным числом угловых точек. В частном случае, когда в систему ограничений - неравенств входят только две переменные x1 и x2 это множество можно изобразить на плоскости (см.3).
Теорема 2. Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений. Справедливость этого утверждения иллюстрируется в примере 3.
Теорема 3. Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений системы ограничений, и наоборот.
Общей
задачей линейного программирования
(ОЗЛП)
называется задача, которая состоит в
определении максимального (мин.) значения
функции
при условиях
где
-
заданные постоянные величины и
.
Функция (7) называется целевой функцией задачи (7)-(10), а условия (8)-(10)- ограничениями данной задачи.
Выпуклое множество точек на плоскости. Угловые точки. Выпуклый многоугольник. Геометрическая интерпретация линейных неравенств и их систем.
Определение 4.1. Множество точек называется выпуклым, если вместе с двумя его точками М1 и М2 ему принадлежат и все внутренние точки отрезка М1М2.
Теорема 4.1. Пусть дана полуплоскость
Ф1: A×x + B×y + C < 0
и точки М1(х1,у1) и М2(х2,у2), принадлежащие Ф1, то есть
А×х1 + В×у1 + С < 0 и А×х2 + В×у2 + С < 0.
Пусть точка М0(х0,у0) принадлежит отрезку L = М1М2.
Если А×х0 + В×у0 + С < 0, то тогда полуплоскость будет выпуклой.
Д о к а з а т е л ь с т в о :
Координаты точки М1 можно выразить через координаты точек М1 и М2:
, 
,
где l > 0.
Подставим эти выражения в неравенство полуплоскости
.
Так как
l > 0, 
и
по условию
А×х1 + В×у1 + С < 0 и А×х2 + В×у2 + С < 0.
следовательно,
А×х0 + В×у0 + С < 0,
а по определению 8.4 такое множество называется выпуклым.
З а м е ч а н и е. Определение выпуклого множества сформулировано в предположении, что в этом множестве имеются по крайней мере две точки. Если множество пустое (в этом случае его обозначают как Æ) или состоит из одной точки, то его тоже считают выпуклым.
Для выпуклых множеств имеет место следующая теорема:
Теорема 4.2. Пересечение любого числа выпуклых множеств - выпуклое множество.
Д о к а з а т е л ь с т в о :
Пусть j1, j2,
..., jn - выпуклые множества и их
пересечение 
,
тогда оно выпукло. Из того, что точка
М0(х0,у0) принадлежит множеству ji (i
= 1,...,n) следует, что М0(х0,у0) принадлежит 
.
Пусть
имеем две произвольные точки М1(х1,у1) и
М2(х2,у2), принадлежащие пересечению
множеств ji, тогда, так как все
множества jiвыпуклы, то им принадлежит
и отрезок М1М2, а следовательно, 
,
но тогда и пересечение
есть
множество выпуклое.
Следствие. Область решений системы линейных неравенств (), если она не представляет собой Æ, является выпуклой многоугольной областью или выпуклым многоугольником.
Ломаная
называется замкнутой,
если ее концы соединены отрезком.
Если
все звенья простой замкнутой ломаной
не лежат на одной прямой, то это многоугольник.
Тогда точки ломанной называютсявершинами
многоугольника,
а звенья – сторонами
многоугольника.
Многоугольник
с n вершинами, называется n-угольником.
Многоугольник
называется выпуклым,
если он лежит в одной полуплоскости
относительно любой прямой, содержащей
его сторону.A1A2A3A4A5A6A7 – выпуклый
многоугольник.
B1B2B3B4B5
– невыпуклый многоугольник.