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

Примеры перехода от

ограничений – неравенств к ограничениям уравнениям:
Пример 1
2X1 + 5X2 ≤ 20,
8X1 + 5X2 ≥ 40,
5X1 + 6X2 ≤ 30,

2X1 + 5X2 + X3 = 20,
8X1 + 5X2 - X4 = 40,
5X1 + 6X2 + X5 = 30,

может быть меньше нуля. Введем в систему ограничений (1)

дополнительное уравнение X4 = X3 - X2 , система (1) примет вид:
2X1 + 5X2 ≤ 20,
8X1 + 5X2 ≥ 40,
5X1 + 6X2 ≤ 30,
X3 - X4 = X2

2X1 + 5X2 + X5 = 20,
8X1 + 5X2 - X6 = 40,
5X1 + 6X2 + X7 = 30,
X3 - X4 = X2
или
2X1 + 5(X3 - X4) + X5 = 20,
8X1 + 5 (X3 - X4) - X6 = 40,
5X1 + 6 (X3 - X4) + X7 = 30,

m линейных уравнений с n переменными
называется несовместной, если у

нее нет ни одного
решения, и совместной, если она имеет хотя бы одно
решение.
Совместная система уравнений, имеющая только одно решение, называется определенной, а более одного – неопределенной.
Пример 1. Система уравнений
x1 + 4 x2 – x3 = 1,
x1 + 4 x2 - x3 = 5
несовместна, т.к. любое решение первого уравнения не является решением второго и наоборот

+ x2 – x3 = 2,

x1 - x2 + x3 = 6
является совместной, т.к. например, тройка чисел (2,1,5) – ее решение, и неопределенной, поскольку кроме указанного она имеет, например, еще одно решение (2,-4, 0).
Уравнения систем могут быть независимыми и зависимыми. Независимость означает, что ни одно из уравнений входящих в состав системы, не является следствием других (одного или нескольких).
Если уравнения зависимы, то “лишние” уравнения должны быть исключены.

система уравнений содержит столько переменных, сколько в ней уравнений,

т. е. m = n , то она имеет только одно решение.
Если число m уравнений системы больше числа n переменных в ней, то такая система эквивалентна или системе из n уравнений с n переменными, или системе из m’ уравнений, в которой m’ < n.
Если число m уравнений системы меньше числа n переменных в ней, то любые m переменных системы m линейных уравнений с n переменными называются основными (базисными), если определитель из коэффициентов при них отличен от нуля. Остальные (n – m) переменных называются неосновными (свободными).
Базисным решением системы m линейных уравнений с n переменными (m < n) называется всякое ее решение, в котором свободные переменные имеют нулевые значения.

и свободные соответствует одно базисное решение.
В базисном решении

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

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

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

меньше m, и равно m – t , где

m – общее число ограничений, а t – число ограничений в виде уравнений.
Вывод. Как бы не были первоначально заданы ограничения задачи линейного программирования, их всегда можно свести к системе линейных уравнений в канонической форме представления.
Уравнение называется линейным, если оно содержит переменные только в первой степени и не содержит произведений переменных.
Пример. Уравнение 3x1 – 4x2 - 5x3 – x4 = 2 является линейным,
а уравнения 2x1x2 – 4x3 – x4 + x5 = 6
x12 + 3x22 + x3 – x4 = 8 не являются линейными.

переменными запишется как:
a11 x1 + a12

x2 + …+ a1n xn = b1,
a21 x1 + a22 x2 + …+ a2n xn = b2,
…………………………………..
am1 x1 + am2 x2 + …+ amn xn = bm,

(1)

ЛП к канонической форме (основной задаче линейного программирования).
2. Определить

свободные переменные.
3. Выразить базисные переменные через свободные.
4. Построить оси координат, соответствующие свободным переменным, выделить для них разрешенные области.
5. Построить прямые, соответствующие каждой базисной переменной равной нулю, выделить для каждой из них разрешенную полуплоскость.
6. Найти область допустимых решений (ОДР) задачи линейного программирования (ЗЛП).
7. Выразить целевую функцию через свободные переменные.
8. Отбросив постоянную составляющую в полученной целевой функции, построить опорную прямую целевой функции равной нулю через начало координат.

целевая функция минимизируется (максимизируется) в соответствии с условием задачи.
10.

Путем параллельного переноса в сторону области допустимых решений совместить опорную прямую с последней точкой ОДР, если направление переноса совпало с направлением оптимизации целевой функции.
11. Путем параллельного переноса в сторону области допустимых решений совместить опорную прямую с первой точкой ОДР, если направление переноса не совпало с направлением оптимизации целевой функции.
12. Определить координаты свободных переменных, соответствую­щие последней (первой) точке, принадлежащей области допустимых решений (ОДР), в которой целевая функция максимальна (минимальна).
13. Вычислить значение целевой функции в этой точке.
14. Вычислить значения базисных переменных через найденные значения свободных переменных.
15. Записать ответ решения задачи в формализованном виде.

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

При этом задача может иметь либо единственное, либо бесчисленное множество оптимальных решений.
2. Единственное оптимальное решение достигается в точке, где не менее чем две переменные обращаются в ноль. Эта точка является одной из вершин многоугольника ОДР.
3. Задача имеет бесчисленное множество решений, если при перемещении опорная прямая совпадает на границе ОДР с ребром выпуклого многоугольника.
4. Оптимальное решение не существует, если ОДР в направлении оптимизации целевой функции не замкнута.
5. Задача не имеет допустимого решения, если условия ограничения противоречивы (нет единой ОДР на плоскости).

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


и обращающие в

минимум целевую функцию:

Решение
1. Приведем условия задачи, заданные в стандартной
форме, к форме канонической:


2.Так как число переменных n = 4, а число уравнений
ограничений m = 2, то n - m = 2, следовательно решение
задачи можно выполнить геометрическим методом.

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


3. Проведем координатные оси

и и
построим прямые х3 = 0 и х4 = 0. Отметим
штриховкой те полуплоскости, где свободные и
базисные переменные принимают положительные
значения (рис.1).

х4 = 0 положительной полуосью Ох1 является

областью допустимых решений, поскольку любая точка внутри треугольника или на его границе удовлетворяет требованию не отрицательности переменных
5. Целевая функция выражена через свободные переменные х1 и х2. Построим опорную прямую целевой функции L(X) = 0, проходящую черев начало координат и точку c координатами (2;1). Направление минимизации целевой функции будет справа налево и снизу вверх.

0 в направлении минимизации L(X), находим вершину выпуклого многоугольника

ОДР, наиболее удаленную от начала координат – точка А, которая и будет точкой ОДР, где целевая функция L(X) имеет свой минимум.
7. Определив координаты точки A, где целевая функция L(X) минимальна и подставив их в исходные уравнения-ограничения и уравнение целевой функции L(X), получим оптимальное решение задачи, в нашем случае:

L(Х) = -7 при = (3;5;0;0).

имеет бесчисленное множество оптимальных решений

L(x) ? опт
ABCD есть ОДР
L(x)

|| AB

X1

X2

Рис.2

имеет не имеет оптимальных решений

Рис.3

незамкнутой ОДР

L(x) имеет оптимальное значение при
X1 = X2

= 0

L(x) ? опт

Рис.4