Презентация2(1)

1.

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

2.

2.1. Алгоритмы графического метода
Рассмотрим задачу линейного программирования, система
ограничений которой задана в форме неравенств.
Найти
экстремум
целевой
функции:
L( X ) c1x1 c2 x2 ... cn xn max (min) .
При
xj 0
ограничениях:
a11 x1 a12 x2 ... a1n xn b1 ,
a x a x ... a x b ,
21 1 22 2
2n n
2
. . . . . . . . . . . . . . . . . . . . . . . . . . ...
am1 x1 am 2 x2 ... amn xn bm ,
( j 1, 2, ..., n) .
Допустимым решением (или допустимым планом) задачи линейного
программирования называется любое решение X ( x1, x2 ,..., xn ) ,
удовлетворяющее системе ограничений и условиям неотрицательности.
Множество допустимых решений (планов) задачи образует область
допустимых решений – ОДР
Если система имеет хотя бы одно решение, она называется
совместной, в противном случае – несовместной.

3.

Рассмотрим частный случай совместной системы при n 2 :
a11 x1 a12 x2 b1 ,
a x a x b ,
21 1 22 2
2
x1 0 , x 2 0
. . . . . . . . . . . . . . . . . .
am1 x1 am 2 x2 bm ,
Каждое неравенство данной системы на плоскости Ox1x2 геометрически
определяет полуплоскость с граничной прямой
ai 1 x1 ai 2 x2 bi , (i 1, 2, ..., m) .
x2
a i 1 x1 a i 2 x 2 b i
ОДР
x1 0
0
x2 0
x1
Рис. 2.1. Выпуклый многоугольник решений

4.

Графический метод решения задач линейного
программирования с двумя переменными
Теорема. Если задача линейного программирования имеет
,
оптимальное решение, то оно достигается
в одной из угловых точек
,
многогранника решений. Если же оптимальное
решение достигается сразу
.
в нескольких угловых точках, то оно также достигается в точках любой их
выпуклой линейной комбинации.
Следствие. Согласно этой теореме для нахождения оптимального
решения, доставляющего экстремум целевой функции L(X ) , необходимо
исследовать лишь конечное число угловых точек многогранника решений,
не исследуя бесконечное множество других допустимых решений.
Графическое решение задач линейного программирования получают,
используя два разных метода:
1. Метод угловой точки.
2. Метод Iso-cost.

5.

Для решения задачи с использованием метода Iso-cost необходимо
выполнить следующие шаги:
Шаг 1: Создать математическую модель из данной задачи.
Шаг 2: Построить график с использованием заданных ограничений и
определить допустимую область.
Шаг 3: Найти координаты допустимой области, полученной на шаге 2.
Шаг 4: Найти значение Z (целевая функция) и построить ее график.
Шаг 5: Построить прямую, отвечающую значению целевой функции
Z =0 и вектор-градиент, составленный из коэффициентов целевой функции.
Начало вектора – точка (0; 0), конец – точка с координатами,
соответствующими коэффициентам целевой функции. Вектор нормали
целевой функции указывает направление возрастания целевой функции.
Будем двигать эту прямую параллельным образом. Поскольку нас
интересует минимальное решение, двигаем прямую целевой функции до
первого касания обозначенной области, если максимальное решение, двигаем
прямую до последнего касания обозначенной области.
Шаг 6: Определяем координаты экстремальных точек и вычисляем в них
значения целевой функции.

6.

Задача 2. Решите данные задачи линейного программирования
графически. Максимизировать: