Файл: В. А.МАТВЕЕВ.pdf

Кратко решение записывается в форме выпуклой оболочки co({x1 , x2 , x3 , x4 }) = co({(4,0),(4013, 2413),(167 ,157),(85 , 95)}).

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

3x1 + 4x2 ≥12,

3x1 +8x2 ≥ 24,

2x1 + x2 ≥ 8,

−x1 + 2x2 ≤ 2,

x2 ≤ 5,

xi ≥ 0,i =1,2.

На плоскости каждому неравенству соответствует полуплоскость, её граница – прямая линия. Границы полуплоскостей представлены в форме (7.8). Полуплоскости для решения системы данной системы неравенств – на рисунке 7.3 и выделены штриховкой. Решение есть выпуклое множество – пересечение полуплоскостей. Из рисунка видно, что пересечение пяти полуплоскостей является неограниченное множество с границей - ломанной KGBEFL. Найдём координаты угловых точек. Они определяются, как пересечения прямых

61

или из рисунка 7.3. Это точки с координатими K (12,0),G(8,0),

B(4013, 2413), L(12,5).

Неограниченное множество решений выделено штриховкой на рис. 7.3. У этого множества четыре угловые точки: G, B, E, F.

(p)

Рис. 7.3.

Но всё множество решений уже не представляется выпуклой комбинацией угловых точек. На рисунке 7.3 указана бесконечная неограниченная последовательность точек из множества решений системы неравенств. Это множество

62

x6 = (8,5); x7 = (8,0).

неограниченная последовательность решений yn = (n+3, 2), n = 1,2, 3, ….

Задачидлясамостоятельногорешения

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

x1 + x2 ≤ 4,

2x1 +7x2 ≤14, x1 + 2x2 ≤ 6, 4x1 +5x2 ≤ 20, xi ≥ 0,i =1,2.

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

2x1 −5x2 ≤ −10, x1 −8x2 ≤ 8,

− x1 + x2 ≤1, 2x1 −7x2 ≤14, xi ≥ 0,i =1,2.

63

§8. Линейное программирование: графический метод

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

Если в задаче математического программирования целевая функция линейная и ограничения в форме равенств и неравенств заданы линейными функциями, то это задача линейного программирования. Такие задачи имеют огромную область применения, не в последнюю очередь потому, что “любой процесс в первом приближении является линейным”. Теория таких задач обстоятельно разработана [8, 9, 10]. Особенно большое значение имеет этот раздел для изучения конечных игровых задач [2, с. 8387; 4, c. 28-32]. Далее будет представлены элементы теории линейного программирования, в той мере, как это потребуется для изучения игровых задач.

Рассматривается задача максимизации на множестве заданном ограничениями – неравенствами

Функция f (x) в (8.1) называется целевой функцией. Ограничения – неравенства в (8.2) и (8.3) определяют область допустимых значений X Rm . Содержательно задача линейного программирования состоит в поиске x* X , доставляющего наибольшее значение функции f (x ), когда x X . Существуют

64

различные формы представления задачи линейного программирования в зависимости от вида ограничений для области допустимыхзначений. Говорят, чтов (8.1) – (8.3) задана стандартная задача линейного программирования.

Если в задаче линейного программирования разыскивается x* X , доставляющий наименьшее значение функции f (x ),

когда x X , то получается задача минимизации на множестве заданном ограничениями – неравенствами.

Существование решения в задаче линейного программирования следует из

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

значений X Rm является компактом, а целевая функция f (x) непрерывна на X. Тогда

x* X , f (x*) ≥ f (x), x X

( x* X , f (x* ) ≤ f (x), x X ).

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

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

(8.1) – (8.3) область допустимых решений X Rm непуста и ограничена. Тогда

x* X , f (x*) ≥ f (x), x X

( x* X , f (x* ) ≤ f (x), x X ).

Рассмотрим графический метод решения задачи линейного

программирования. Этот метод применим, когда X R2 или задача сводится к задаче с двумя переменными.

Графический метод разбивается на два этапа.

Первый этап. Используя условия (8.2) – (8.3) на плоскости строится область допустимых решений X R2.

Второй этап. На плоскости строятся прямые - линии уровня

65

c1 x1 +c2 x2 = ρ, ρ R. В точках касания линий уровня с областью

X достигаются наибольшие и наименьшие значения функции f. Отметим, что линия уровня касается области X, если

1)область и прямая имеют общие точки;

2)область расположена по одну сторону от прямой – линии уровня/

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

f (x ) = x1 + x2 →extr ; x1 +3x2 ≤30, 2x1 +x 2 ≤ 20, x1 ≥ 0; x2 ≥0.

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

расположена в первой четверти ( x1 ≥ 0, x2 ≥ 0) и ограничена

прямыми m и n. Для удобства построения запишем уравнения этих прямых в отрезках.

чертёж представлен на рис.8.1. Здесь m представлена прямой АВ, а n представлена прямой ДВ.

Каждая прямая, как решение соответствующего неравенства, определяет полуплоскость (7.6). В случае прямых АВ и ДВ это будут полуплоскости, содержащие начало отсчёта O. Тогда область допустимых значений в задаче линейного программирования представляется четырёхугольником OДBC.

Построим прямые уровня, которые касаются области X. Таких прямых две

66

x 2

точке В(6, 8). Отметим, что координаты точки В являются решением системыуравнений

x1 +3x2 = 30,

2x1 + x2 = 20.

Точки касания О(0, 0) и В(6, 8) определяют решение задачи линейного программирования. Именно,

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

67