Chernov_-_Vvedenie_v_LP

13.Человеку для нормальной жизнедеятельности необходимо ежемесячно потреблять 3,5 кг белка, 1,7 кг жиров, 15 кг углеводов, 250 г минеральных солей.

В таблице 4 указано количество граммов этих полезных веществ, содержащихся в килограмме потребляемых продуктов, а также цена за 1 кг каждого продукта.

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

41

2. Геометрический смысл задачи линейного

программирования и графический способ ее решения

2.1. Задачи линейного программирования с двумя

переменными

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

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

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

max(c1 x1 c2 x 2 )

Планы такой задачи - это пары чисел (x1, x2). Им соответствуют точки координатной плоскости (рис.1).

42

x2

Градиент

bi / ai2 X*min

X*max

Рис. 1. Ограниченная область допустимых планов

2.2.Допустимые планы задачи

2.2.1.Геометрический смысл ограничений - неравенств

Рассмотрим систему ограничений. Возьмем одно из неравенств системы,

ai1x1 ai 2 x 2 bi .

Множество решений неравенства, то есть множество пар (x1, x2), компоненты которых удовлетворяют неравенству, геометрически представляет собой множество точек некоторой части координатной плоскости. Такая часть представляет собой полуплоскость. Для того чтобы определить граничную прямую этой полуплоскости, следует заменить знак неравенства знаком равенства:

ai1x1 ai 2 x 2 bi .

43

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

Для того, чтобы построить прямую, достаточно знать две ее точки. Можно подставить в уравнение любые два значения x1 (или x2) и найти из уравнения соответствующее значение другой неизвестной. Обычно бывает удобно положить x1 = 0 и найти соответствующее значение x2 = bi / ai2, а затем положить x2 = 0 и найти значение x1 = bi / ai1. В этом случае две точки будут лежать на координатных осях (рис.1). Полученные две точки следует соединить прямой линией.

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

Если неравенство окажется выполненным, то вся полуплоскость, в которой лежит эта точка, является множеством решений неравенства. Если неравенство не выполнено, то множеством решений является противоположная полуплоскость. На рис. 1 выбранная полуплоскость отмечена короткими стрелками около граничной прямой.

Отметим, что и в том, и в другом случае граничная прямая относится к множеству решений неравенства, так как неравенство нестрогое и включает в себя равенство.

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

44

2.2.2.Область допустимых планов задачи

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

В типичной, наиболее часто встречающейся ситуации, множество допустимых планов представляет собой ограниченную выпуклую многоугольную область — выпуклый многоугольник, расположенный в первой координатной четверти (рис. 1).

x2

Градиент

Но возможны и другие варианты. Область может быть выпуклой неограниченной (рис.2) или пустой (рис.3).

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

45

Пустота области соответствует отсутствию планов, удовлетворяющих всем ограничениям вместе. Это означает противоречивость системы ограничений.

Противоречивой, например, является система, содержащая неравенства

ai1x1 + ai2x2 10,

ai1x1 + ai2x2 15.

x2

Рис.3. Пустая область допустимых планов

2.2.3.Свойства области допустимых планов

Область допустимых планов обладает важным свойством - свойством выпуклости.

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

46

Для анализа решения задачи важно знать и другое определение выпуклости. Именно, если взять любые две точки выпуклой области и соединить их отрезком прямой, то все точки этого отрезка также окажутся принадлежащими области.

Точки отрезка в алгебраической форме представляют собой взвешенную сумму его концов или, как иногда говорят, смесь его концов. Взвешенная сумма двух векторов X1, X2 - это вектор X определяемый формулой

X h1X1 h 2 X2 ,

где h1, h2 - неотрицательные числа, сумма которых равна 1.

h1 h2 1, h1 0, h2 0.

Если h1 = h2 = 1/2, то точка Х представляет собой середину отрезка с концами X1 и X2 (точка X0 на рис.4). Если увеличить h1 (и, следовательно, уменьшить h2, так как их сумма равна 1), то точка Х сместится по отрезку от его середины в сторону конца X1. В частности, если h1 = 1 (и h2 = 0), то X = X1. Если же, напротив, увеличить h2, то точка Х сдвинется в сторону конца X2, и при h2 = 1 (и h2 = 0) получим X = X2.

47

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

то есть отношение длин двух частей отрезка равно обратному отношению соответствующих весовых коэффициентов.

Выпуклое множество вместе с любыми двумя своими точками содержит целиком и весь отрезок, соединяющий эти точки. В невыпуклом множестве, напротив, найдутся две такие его точки, что соединяющий их отрезок не содержится целиком в этом множестве. На рис.5 точки X1 и X2 принадлежат многоугольному множеству ОАВС, а точка X соединяющего их отрезка находится за пределами этого множества. Следовательно, многоугольник ОАВС - невыпуклый.

Рис.5 Невыпуклое множество

49