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

f = –х 1 + 5х 2 ¾> min ;

4х 1+ 3х 2 £ 24,

х 1– 10х 2 £ 0,

8х 1– 3х 2 ³ 0,

5х 1+ 3х 2 ³ 15,

х 1³0, х 2³ 0. (1)

Совокупность переменных хj , удовлетворяющих условию (1), называется областью допустимых решений. Допустимое решение, обращающее целевую функцию в min или max , называется оптимальным. Для его определения необходимо построить область допустимых решений (область определения). Так как в условии задачи заданы две переменные, то область допустимых решений находится на плоскости х 10х 2. Каждое неравенство (1) определяет полуплоскость, а равенство – прямую. Для построения полуплоскости необходимо найти ее границу и установить, с какой стороны от нее лежит искомая полуплоскость. Перепишем условия (1) в виде равенств (2) и пронумеруем их.

4х 1+ 3х 2	=	24 (I ),
х 1– 10х 2	=	0 (II ),
8х 1– 3х 2	=	0 (III ),
5х 1+ 3х 2	=	15 (IV ).	(2)

Введем систему координат х 10х 2 и построим последовательно эти прямые – границы полуплоскостей. Для построения прямой на плоскости необходимо определить любые две точки, лежащие на этой прямой. Если прямая пересекает оси 0х 1и 0х 2, то можно найти координаты точек ее пересечения с осями координат. Определим координаты пересечения прямой (I ) с осью 0х 1: х 1=0; Þ 3х 2= 24; Þ х 2= 8. Соответственно определим координаты второй точки пересечения первой прямой с осью 0х 2: х 2=0; Þ 4х 1= 24; Þ х 1= 6. Следовательно, точки пересечения прямой (I ) с осями координат равны (0,8) и (6,0). Построим эту прямую (рис. 1).

Определим полуплоскость. Для этого подставим в первое неравенство (1) координаты любой точки, не лежащей на данной прямой, например (0,0). Тогда из первого условия следует: 4×0+3×0 £24, значит, неравенство справедливо, откуда следует, что полуплоскость лежит с той стороны прямой, где находится точка с координатами (0,0).

Аналогичным образом строятся и другие полуплоскости. Необходимо учесть, что прямые (II) и (III) проходят через начало координат, т.е. точку (0,0). Координаты второй точки желательно брать пропорционально коэффициентам в уравнении искомой прямой. Например, для второй прямой – точки (0,0) и (10,1), а для третьей – (0,0) и (3,8). После построения всех полуплоскостей область допустимых решений примет следующий вид (рис. 3):

Целевая функция f определяет на плоскости прямую, которая должна проходить через точку или сторону многоугольника и иметь наименьшее значение. Построим направляющий вектор для этой прямой. Данный вектор перпендикулярен искомой прямой, и его направление всегда определяет максимум целевой функции. Противоположное направление вектора определяет минимум. Обозначим этот вектор через . Он проходит через точку (0,0) и (–1,5). Координаты второй точки берут из коэффициентов целевой функции и с их помощью определяют направление вектора. Перпендикулярно ему построим прямую –х 1+ 5х 2=0. Как было сказано выше, вектор всегда показывает направление возрастания значения целевой функции (max ) , противоположный ему вектор –– направление убывания значения целевой функции (min ). Перемещаем прямую –х 1+5х 2=0 по области определения параллельно самой себе в направлении min . Целевая функция f достигнет своего минимального значения в точке С (рис. 4).

Оптимальному решению задачи (1) соответствует точка С , которая лежит на пересечении прямых (I ) и (II ):

4х 1+ 3х 2= 24;

х 1– 10х 2= 0.

Для решения данной системы уравнений умножить второе уравнение на 4 и сложить соответственно по элементам с 1-м уравнением:

4х 1+ 3х 2 = 24;

4х 1– 40х 2 = 0.

Вычтем из первого уравнения второе, получим: 43х2= 24 Þ х 2= 0,56.

Подставив найденное значение х 2во второе уравнение, получим:

х 1= 10х 2Þ х 1=5,6. Подставив координаты точки С в целевую функцию, получим следующий результат:

f min = – 5,6 + 5×0,56 = – 2,8.

Окончательный результат задачи запишем в следующем виде:

х 1= 5,6, х 2= 0,56;f min = – 2,8.

Решение данного примера на ПЭВМ осуществляется программным комплексом «Блок-3». С его помощью производятся ввод, решение и вывод результативной информации на внешний носитель. Простота и доступность комплекса позволит без труда освоить его и применять на практике.

Задача № 1.1.2.

f = 2х 1+ 3х 2 ¾> max;

2х 1+ 3х 2 £ 12,

2х 1– 5х 2 £ 0,

7х 1– 2х2³ 0,

х 1, х 2³ 0. (3)

Определения и построение области допустимых решений аналогичны заданию 1.1.1. Окончательный вид области допустимых решений представлен на рис. 5 многоугольником АВС (точка А совпадает с точкой 0).

Очевидно, что прямая, определяющая целевую функцию, совпадает с прямой, образующей сторону многоугольника ВС . Отсюда следует, что решением данной ЭММ являются точки, лежащие на стороне ВС много-

угольника АВС . Для записи решения ЭММ необходимо найти координату x 1B – точки В и x 1C – точки С . Определив их, мы сможем найти отрезок, лежащий на оси 0x 1(рис. 6).

Координаты точки В – x1B определяются в результате пересечения прямых 2х 1+ 3х 2 = 12 и 7х 1– 2х 2 = 0. Для этого необходимо решить систему уравнений:

2х 1+ 3х 2= 12 ´ 2 Þ 4х 1+ 6х 2= 24;

7х 1– 2х 2= 0 ´ 3 Þ 21х 1– 6х2= 0.

Сложив два последних уравнения, получим: 25х 1=24, х 1=0,96. Из этого следует, что x 1B =0,96. Координата точки С – x 1C определяется в результате пересечения прямых 2х 1+ 3х 2=12 и 2х 1–5х 2=0. Решим систему уравнений:

2х 1+ 3х 2= 12 ´ 5 Þ 10х 1+ 15х 2= 60;

2х 1– 5х 2= 0 ´ 3 Þ 6х 1 – 15х 2= 0.

Сложив два последних уравнения, получим: 16х 1= 60, х 1= 3,75, откуда следует, что x 1C = 3,75.

Значение целевой функции для данной ЭММ равно 12 (так как уравнение прямой, на которой определен отрезок ВС – 2х 1+3х 2= 12).

Таким образом, ответ данной задачи:

x 1Î[x 1B ; x 1C ] Þ x 1Î;

2х 1+ 3х 2=12 Þ 3х 2= 12 – 2х 1Þ х 2= (12 – 2х 1)/3.

Полный ответ данного примера запишется в следующем виде:

x 1Î; x 2= (12 – 2х 1)/3; f max = 12.

Задача № 1.1.3.

f = 2х 1+ 3х 2 ¾> max;

2х 1+ 3х 2 ³ 12,

2х 1– 5х 2 £ 0,

7х 1– 2х 2³ 0,

х 1, х 2 ³0. (4)

Используя схему построения области допустимых решений задач 1.1.1–1.1.2, получим следующий график (рис. 7):

f = 2х 1+ 3х 2 ¾> max ;

х 1+ х2 £ 2,

2х 1+ 3х 2³ 12,

2х 1– 5х 2£ 0,

7х 1– 2х 2³ 0,

х 1, х 2³ 0. (5)

Используя график задачи 1.1.3 и достроив первую полуплоскость х 1+х2£ 2, получим область определения, показанную на рис. 8.

Из графика (рис. 8) видно, что для данной ЭММ области допустимых решений нет. Ответ: нет области допустимых решений.

Задача № 1.1.5.

f = – х 1+ 5х 2 ¾> min;

10х 1+ 3х 2£ 30,

10х 1+ 5х 2³ 50,

2х 1– 6х 2£ 0,

х 1, х 2³ 0. (6)

Область определения ЭММ (6) представлена на рис. 9. Из анализа графика следует, что областью допустимых решений будет являться точка А с координатами (0,10) (10х 1+ 5х 2= 50, х 1= 0, 5х 2= 50, х 2=10). В случае, когда решением ЭММ является единственная точка, целевую функцию можно не строить.

Ответ: x 1= 0; x 2=10; fmin = 0+5×10 = 50.

Таким образом, при решении задач ЭММ ЛП возможны следующие ситуации:

– задача имеет одно оптимальное решение;

– задача имеет бесконечное число оптимальных решений;

– задача не имеет оптимального решения;

– задача не имеет области допустимых решений.

На практике ЭММ ЛП не имеет решений только в том случае, если некорректна постановка задачи.

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

Задача № 1.1.6.

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

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

1) Решить графическим способом;

2) Решить на базе комплекса «Блок-3»;

3) Симплекс-методом.

Рассмотрим сначала простейший случай, когда в ЗЛП включены ровно две переменные:

Каждое из неравенств (a)-(b) системы ограничений задачи (3.8) геометрически определяет полуплоскость соответственно с граничными прямыми , Х 1 =0 и Х 2 =0. Каждая из граничных прямых делит плоскость х 1 Ох 2 на две полуплоскости. Все решения исходного неравенства лежат в одной из образованных полуплоскостей (все точки полуплоскости) и, следовательно, при подстановке координат любой ее точки в соответствующее неравенство обращает его в верное тождество. С учетом этого и определяется та полуплоскость, в которой лежат решения неравенства, т.е. путем выбора любой точки из какой-либо полуплоскости и подстановки ее координат в соответствующее неравенство. Если неравенство выполняется для данной точки, то оно выполняется и для любой другой точки из этой же полуплоскости. В противном случае решения неравенства лежат в другой полуплоскости.

В том случае, если система неравенств (a)-(b) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то область допустимых решений задачи (3.8) является выпуклое множество, которое называется многоугольником решений (введённый ранее термин “многогранник решений” обычно употребляется, если n 3). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

Таким образом, исходная ЗЛП состоит в нахождении такой точки многоугольника решений, в которой целевая функция F принимает максимальное (минимальное) значение.

Эта точка существует тогда, когда многоугольник решений не пуст и на нём целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины строят линию уровня L: c 1 x 1 +c 2 x 2 =h (где h – некоторая постоянная), перпендикулярную вектору-градиенту и проходящую через многоугольник решений, и передвигают её параллельно вдоль вектора-градиента до тех пор, пока она не пройдёт через последнюю её общую точку пересечения с многоугольником решений (при построении вектора-градиента откладывают точку (с 1 ; с 2) в плоскости х 1 Ох 2 и проводят к ней из начала координат направленный отрезок). Координаты указанной точки и определяют оптимальный план данной задачи.

Суммируя все выше изложенное, приведем алгоритм графического метода решения ЗЛП.

Алгоритм графического метода решения ЗЛП

1. Построить многоугольник решений, задаваемый системой ограничений исходной ЗЛП.

2. Если построенный многоугольник решений – пустое множество, то исходная ЗЛП решений не имеет. В противном случае построить вектор-градиент и провести произвольную линию уровня L, перемещая которую при решении задачи на максимум в направлении вектора (или в обратном направлении для задачи на минимум) определить крайнюю точку многоугольника решений, где и достигается максимум (минимум) целевой функции задачи.

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

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

При графическом построении множества допустимых решений ЗЛП (многоугольника решений) возможны следующие ситуации.

Графический метод решения ЗЛП основан на утверждениях, приведенных в пункте 2.1. Согласно теореме 2, оптимальное решение находится в вершине области допустимых решений и поэтому решить ЗЛП – найти вершину области допустимых решений, координаты которой дают оптимальное значение целевой функции.

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

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

Реализацию графического метода решения ЗЛП рассмотрим на примерах.

Пример 2.2.1. Решить ЗЛП графическим методом:

(2.2.1)

max z =x 1 + 4x 2 (2.2.2)

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

l 1: x 1 + 5x 2 = 5; l 2: x 1 + x 2 = 6; l 3: 7x 1 + x 2 = 7.

l 1 к виду (2.2.3.) разделим обе его части на 5:
. Таким образом, прямаяl 1 отсекает на оси Ох 1 5 единиц, на оси Ох 2 1 единицу. Аналогично имеем для l 2:
иl 3:
.

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

Таким образом, первая и вторая искомые полуплоскости расположены в противоположную сторону от начала координат (0 – 5·0– 5; 7·0 + 07), а вторая – в сторону начала координат (0 + 06). Область допустимых решений на рисунке 2.2.1 заштрихована.

Рисунок 2.2.1 – Область допустимых решений

Для нахождения оптимального плана, который будет находиться в вершине многоугольника решений, нужно построить вектор направлений
=(с 1 ,с 2), который указывает направление наибольшего возрастания целевой функцииz =с 1 х 1 +с 2 х 2 .

В данной задаче вектор направлений
= (1, 4): он начинается в точкеО (0,0) и заканчивается в точкеN (1, 4).

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

Таким образом, точкой максимума целевой функции z является точкаА пересечения прямыхl 2 иl 3 .

Для вычисления оптимального значения целевой функции z найдем координаты точки А. Поскольку точка А – это точка пересечения прямых l 2 и l 3 , то ее координаты удовлетворяют системе уравнений, составленной из уравнений соответствующих граничных прямых:

Таким образом, точка А имеет координаты x 1 =1/6, x 2 = 35/6.

Для вычисления оптимального значения целевой функции нужно подставить в нее координаты точки А.

Подставив координаты точки А в целевую функцию (2.4), получим

max z = 1/6 + 4·(35/6) = 47/2.

Пример 2.2.2. Построить на плоскости область допустимых решений системы линейных неравенств (2.2.4) и найти наибольшее и наименьшее значения целевой функции (2.2.5):

(2.2.4)

z = –2x 1 –x 2 (2.2.5)

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

l 1: 4x 1 – x 2 = 0; l 2: x 1 + 3x 2 = 6; l 3: x 1 – 3x 2 = 6; l 4: x 2 = 1.

Прямая l 1 проходит через точку с координатами (0;0). Для ее построения выразим x 2 через x 1: x 2 = 4x 1 . Найдем еще одну точку, через которую проходит прямая l 1 , например (1;4). Через точку с координатами (0;0) и точку с координатами (1;4) проведем прямую l 1 .

Для приведения уравнения прямой l 2 к виду в отрезках на осях (2.2.3) разделим обе его части на 6:
. Таким образом, прямаяl 2 отсекает на оси Ох 1 6 единиц, на оси Ох 2 - 2 единицы. Аналогично имеем для l 3:
и Прямаяl 4 параллельна оси Ох 1 и проходит через точку с координатами (0;1) .

Для определения полуплоскостей, которые отвечают ограничениям системы (2.2.4) в ограничения нужно подставить координаты какой-либо точки, не лежащей на граничной прямой. В силу ограничений х 1 0, х 2 0, область допустимых решений ЗЛП лежит в первой четверти координатной плоскости.

О
бласть допустимых решений на рисунке 2.2.2 заштрихована.

Рисунок 2.2.2 – Область допустимых решений

Построим вектор направлений
= (–2,–1). Далее строим линию уровня, перпендикулярно к вектору.

Для нахождения наибольшего значения целевой функции передвигаем линию уровня в направлении вектора до последнего пересечения с областью допустимых решений. Таким образом, точкой максимума целевой функцииz является точкаА (пересечение прямыхl 1 иl 2).

Для вычисления оптимального значения целевой функции z найдем координаты точкиА . Поскольку точкаА – это точка пересечения прямыхl 1 иl 2 , то ее координаты удовлетворяют системе уравнений, составленной из уравнений соответствующих граничных прямых:

Таким образом, точка А имеет координаты x 1 =6/13, x 2 = 24/13.

Подставив координаты точки А в целевую функцию (2.2.5), получим оптимальное значение целевой функции

max z = – 2·(6/13) – (24/13) = – 36/13.

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

В результате решения ЗЛП возможны следующие случаи:

Целевая функция достигает оптимального значения в единственной вершине многоугольника решений;

Целевая функция достигает оптимальное значение в любой точке ребра многоугольника решений (ЗЛП имеет альтернативные опорные планы с одинаковыми значениями z);

ЗЛП не имеет оптимальных планов;

ЗЛП имеет оптимальный план в случае неограниченной области допустимых решений.

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу .

Решение происходит в три этапа:

1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b (F(X) → extr) сводится к виду ax = b , F(X) → max ;
2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
3. Решение симплексным методом;

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 1 2 3 4 5 6 7 8 9 10

Переход от задачи минимизации целевой функции к задаче максимизации

Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:

F(x) → min

F(x) → max

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

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

Переменные x 1 , …, x m , входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми - в остальные, называются базисными или зависимыми . В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса-Жордана . Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x m +1 ,…, x n) называются небазисными или независимыми переменными .

Базисное решение называется допустимым базисным решением , если значения входящих в него базисных переменных x j ≥0, что эквивалентно условию неотрицательности b j ≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом .
Если среди неотрицательных чисел b j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной .

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x 1 + 2x 2 - 2x 3 → min при ограничениях:
4x 1 + 3x 2 - x 3 ≤10
- 2x 2 + 5x 3 ≥3
x 1 + 2x 3 =9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x 4 ; во втором неравенстве смысла (≥) вводим базисную переменную x 5 со знаком минус.
4x 1 + 3x 2 -1x 3 + 1x 4 + 0x 5 = 10
0x 1 -2x 2 + 5x 3 + 0x 4 -1x 5 = 3
1x 1 + 0x 2 + 2x 3 + 0x 4 + 0x 5 = 9
F(X) = - x 1 - 2x 2 + 2x 3
Переход к СЗЛП .
Расширенная матрица системы ограничений-равенств данной задачи:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 4 .
2. В качестве базовой переменной выбираем x 2 .
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x 2 , получена в результате деления всех элементов строки x 2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(0 3):-2	3-(-2 3):-2	-1-(5 3):-2	1-(0 3):-2	0-(-1 3):-2	10-(3 3):-2
0: -2	-2: -2	5: -2	0: -2	-1: -2	3: -2
1-(0 0):-2	0-(-2 0):-2	2-(5 0):-2	0-(0 0):-2	0-(-1 0):-2	9-(3 0):-2

Получаем новую матрицу:

4	0	6 1 / 2	1	-1 1 / 2	14 1 / 2
0	1	-2 1 / 2	0	1 / 2	-1 1 / 2
1	0	2	0	0	9

3. В качестве базовой переменной выбираем x 3 .
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x 3 , получена в результате деления всех элементов строки x 3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x 3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

4-(1 6 1 / 2):2	0-(0 6 1 / 2):2	6 1 / 2 -(2 6 1 / 2):2	1-(0 6 1 / 2):2	-1 1 / 2 -(0 6 1 / 2):2	14 1 / 2 -(9 6 1 / 2):2
0-(1 -2 1 / 2):2	1-(0 -2 1 / 2):2	-2 1 / 2 -(2 -2 1 / 2):2	0-(0 -2 1 / 2):2	1 / 2 -(0 -2 1 / 2):2	-1 1 / 2 -(9 -2 1 / 2):2
1: 2	0: 2	2: 2	0: 2	0: 2	9: 2

Получаем новую матрицу:

3 / 4	0	0	1	-1 1 / 2	-14 3 / 4
1 1 / 4	1	0	0	1 / 2	9 3 / 4
1 / 2	0	1	0	0	4 1 / 2

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или

Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max

Пример №2 . Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x 1 + x 2 - x 3 + x 5 +15 → max (min) при ограничениях:
-3x 1 + x 2 + x 3 =3
4x 1 + 2x 2 - x 4 =12
2x 1 - x 2 + x 5 =2
x 1 ≥ 0, x 2 ≥ 0, x 3 ≥ 0, x 4 ≥ 0, x 5 ≥ 0

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи линейного программирования (1.2) определяет на координатной плоскости некоторую полуплоскость (рис.2.1), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.

Все вышесказанное относится и к случаю, когда система ограничений (1.2) включает равенства, поскольку любое равенство

можно представить в виде системы двух неравенств (см. рис.2.1)

ЦФ при фиксированном значении определяет на плоскости прямую линию. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня .

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

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора.

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

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.

Рисунок 2.1 Геометрическая интерпретация ограничений и ЦФ задачи.

Методика решения задач ЛП графическим методом.

I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.

II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если неравенство истинное,

то надо заштриховать полуплоскость, содержащую данную точку;

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

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

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

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

IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

V. Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны .

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

VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.