Экономико-математические методы и модели

Вспомним неравенства. Если линейное уравнение с двумя переменными может быть представлено в виде прямой на плоскости, то неравенство вида:

a1x1+a2

x2£b (4.9)

изображается как полуплоскость, показанная на рис. 4.1. На этом рисунке часть плоскости, удовлетворяющая неравенству, заштрихована. Координаты всех точек, принадлежащих заштрихованному участку, имеют такие значения x1 и x2, которые удовлетворяют заданному неравенству. Значит, эти значения составляют область допустимых решений (ОДР). Саму прямую считаем принадлежащей каждой из двух указанных полуплоскостей. Предположим теперь, что задано не одно неравенство, а система:

ìа11x1+а12x2 £ b1

ïа21x1+а22x2 £ b2

(4.10) í . . . .

îаm1x1+аm2x2 £ bm,

где первое неравенство определяет некоторую полуплоскость П1, второе - полуплоскость П2 и т.д.

если какая-либо пара чисел (x1, x2) удовлетворяет всем неравенствам (4.10), то, соответствующая точка Р(x1, x2), принадлежит всем полуплоскостям П1, П2, . Пm одновременно. Другими словами, точка Р принадлежит пересечению (общей части) полуплоскостей П1, П2, . Пm, т.е. некоторой многоугольной области М (Рис. 4.3), которая является ОДР. Вдоль контура области изображены штрихи, идущие внутрь области. Они одновременно указывают, с какой стороны от данной прямой лежит соответствующая полуплоскость, то же самое указано и с помощью стрелок на каждой линии. Сразу же отметим, что ОДР не всегда бывает, ограничена: в результате пересечения нескольких полуплоскостей может возникнуть и неограниченная область (Рис. 4.4). Возможен и случай, когда область допустимых решений (ОДР) пуста. Это означает, что система (5.7) противоречива (Рис. 4.5). Многоугольник ОДР обладает весьма важным свойством: он является выпуклым.

þ фигура называется выпуклой, если вместе с любыми двумя своими точками А и В, она содержит и весь отрезок АВ.

В случае трех неизвестных, каждое уравнение представляет собой плоскость в пространстве. Каждая плоскость разбивает все пространство на два полупространства. Система неравенств определяет в пространстве выпуклый объемный многогранник, который представляет ОДР.

5. МЕТОДЫ РЕШЕНИЯ

ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

5.1. Общая и основная задачи линейного программирования

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

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

þ Oбщей задачей линейного программирования называется задача, которая coстоит в определении максимального (минимального) значения функции:

(5.1)

при условии:

(5.2)

(5.3)

Xj³ 0 (j=1, 1; 1 £n) (5.4)

где aij, bi, сj - заданные постоянные величины и k £ m.

þ Функция (5.1) называется целевой функцией (или линейной формой) задачи (5.1)-(5.4), а условия (5.2)-(5.4) - ограничениями данной задачи.

þ Стандартной (или симметричной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (5.1) при выполнении условий (5.2) и (5.4), где k=m и 1=n.

þ Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (5.1) при выполнении условий (5.3) и (5.4), где k=0 и 1=n.

þ Совокупность чисел Х* = (x1, x2, ., xn), удовлетворяющих ограничениям задачи (5.2)-(5.4), называется допустимым решением (или планом).

þ План Х* = (x1, x2, ., xn), при котором целевая функция задачи (5.1) принимает свое максимальное (минимальное) значение, называется оптимальным.

значение целевой функции (5.1) при плане X будем обозначать через F(X). Следовательно, Х* - оптимальный план задачи, если для любого X выполняется неравенство F(X) £ F(Х*) (соответственно F(X) ³ F(Х*)).

5.2. Геометрический метод решения

задач линейного программирования

Перепишем основную задачу линейного программирования в векторной форме: найти максимум функции

F=CX (5.5)

при условиях:

x1P1+x2P2+ . +xnPn = P0 (5.6)

Х ³0 (5.7)

где C = (с1, с2, ., сn), Х = (х1, х2, ., хn); СХ - скалярное произведение; Р1, Р2, ., Рn и Р0 - m-мерные вектор-столбцы, составленные из коэффициентов при неизвестных и свободных членах системы уравнений задачи.

þ План X = (х1, х2, ., хn) называется опорным планом основной задачи линейного программирования, если система векторов Pj, входящих в разложение (5.6) с положительными коэффициентами xj, линейно независима.

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

 Скачать реферат