64
§8. Линейное программирование: графический
метод
Важное место в математике, а особенно в приложениях
математики к реальным практическим задачам, занимает
математическое программирование. Это математическая
дисциплина, посвящена теории и методам решения задач о
нахождении экстремумов функций на множествах
конечномерного векторного пространства, определяемых
линейными и нелинейными ограничениями (равенствами и
неравенствами).
Если в задаче математического программирования целевая
функция линейная и ограничения в форме равенств
и неравенств
заданы линейными функциями, то это задача линейного
программирования. Такие задачи имеют огромную область
применения, не в последнюю очередь потому, что “любой процесс
в первом приближении является линейным”. Теория таких задач
обстоятельно разработана [8, 9, 10]. Особенно большое значение
имеет этот раздел для изучения конечных игровых задач [2, с. 83-
87; 4, c. 28-32]. Далее будет представлены элементы теории
линейного программирования,
в той мере, как это потребуется
для изучения игровых задач.
Рассматривается задача максимизации на множестве
заданном ограничениями – неравенствами
max;...)(
2211
→+++=
mm
xcxcxcxf (8.1)
,,...1 ,...
211
nibxaaxa
imimii
=≤+++ (8.2)
.,...,1 ,0 mjx
j
=≥
(8.3)
Функция
)(xf
в (8.1) называется целевой функцией.
Ограничения – неравенства в (8.2) и (8.3) определяют область
допустимых значений
.
m
RX ⊂
Содержательно задача линейного
программирования состоит в поиске
Xx
*
, доставляющего
наибольшее значение функции ),(xf когда
. Xx
Существуют