Задачу линейного программирования (ЛП) можно решать аналитическими и графическими методами. Аналитические методы являются основой для решения задачи на ЭВМ. Их единственный недостаток состоит в том, что в отличие от графических методов, они недостаточно наглядны. Графические методы очень наглядны, но они пригодны лишь для решения задач на плоскости, т.е. когда размерность пространства К=2. Однако, учитывая большую наглядность графических методов, с их помощью рассмотрим идею решения задачи ЛП на примере задачи распределения ресурсов.

Однако прежде чем заняться решением, сделаем некоторые замечания. Пусть мы имеем систему m уравнения с n неизвестными (I).

Возможны следующие варианты:

Число неизвестных меньше, чем число уравнений n  m.

например: ì2x1=4, в этом случае n=1;

îx1=5, тогда m=2 (число линейно независимых уравнений). (

3.4)

Очевидно, что система (3.4) решения не имеет, и она несовместна;

Число неизвестных равно числу уравнений n=m.

В этом случае система имеет единственное решение или не имеет ни одного. Заметим, что m равно числу линейно независимых уравнений.

Для системы: ì2x=10, n=1, m=1;

î6x=30.

Если число неизвестных больше числа уравнений, то система имеет бесчисленное множество решений. Пусть n  m. Например:

2

x

1

+

x

2

=2

(3.5)

Очевидно, что это уравнение прямой, и все значения x1 и x2, лежащие на этой прямой, являются решением уравнения (4.2). Значит уравнение (4.5) имеет бесчисленное множество решений.

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

a

1

x

1

+

a

2

x

2

=

b

(

3.6)

Преобразуем его к виду:

(

3.7)

Запись (3.7) называют уравнением прямой в отрезках, что изображено на Рис.

3.1

. Рассмотрим еще одну форму представления уравнения (3.6). Запишем это уравнение в виде:

a2x2=b-a1x1

или

или

x

2

=

F

-

kx

1

(

3.8)

Уравнение (3.8) изображено на рис.

3.2

.

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

a

1

x

1

+

a

2

x

2

£

b

(

3.9)

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