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

2.

Задание 1.
Задание 1: Найти точку максимума функции z=Sx1+ Gx2
при ограничениях
x1 x2 1
G S 4 0
Sx1 2Gx 2 GS 0
2 Sx Gx 2 GS 0
x 0
1
x2 0
G- номер группы, S- номер студента в списке
2

Геометрический метод решения
Построить прямые, уравнения которых получаются в результате замены в
ограничениях знаков неравенств на знаки равенств.
Найти полуплоскости, определяемые каждым из ограничений. Соответствующая полуплоскость
может быть найдена подстановкой в неравенство координат какой-нибудь «простой» точки,
например, - (0,0). Главное - чтобы эта точка не принадлежала границе полуплоскости. Если после
подстановки неравенство окажется справедливым, то выбирается та полуплоскость, где
содержится эта точка. Если неравенство не справедливо, то выбирается альтернативная
полуплоскость.
Определить многоугольник решений как пересечение найденных
полуплоскостей.
Построить градиент целевой функции, т.е. вектор grad(z)=(c1,c2), координатами
которого служат коэффициенты целевой функции z. Этот вектор определяет
направление наискорейшего возрастания целевой функции.
Построить ряд линий уровня целевой функции z, т.е. прямых, перпендикулярных градиенту L. При
этом построение линий уровня следует вести в направлении градиента, если решается задача на
максимум, и в противоположном направлении (в направлении «антиградиента»), если решается
задача на минимум. В результате отмечается точка (точки), в которой линии уровня в последний раз
касаются допустимого множества.
3

4.

Пример
Требуется определить x1 , x2 , при котором величина z максимальна:
z 3x1 2 x2
при ограничениях
x1 x2 6
x 2 x 10
2
1
2 x1 x2 10
x 0
1
x2 0
4

5.

Геометрический метод решения
Построение многоугольника ограничений:
1. Прямая x1 x2 6 :
x1 0 x2 6 ;
x2 0 x1 6
2. Прямая x1 2 x2 10 :
x1 0 x2 5;
x2 0 x1 10
3. Прямая 2 x1 x2 10 :
x1 0 x2 10 ;
x2 0 x1 5
4. Прямая z 3x1 2 x2 0:
x1 0 x2 0 ; x1 2 x2 3
5

6.

Геометрический метод решения
11
10
Расстояние d от точки (x1 , x2)
до прямой z= ax1+b x2+c =0
определяется по формуле:
X2
d
9
8
ax1 bx2 c
a 2 b2
2X1+X2=10
7
6
5
X1=4, X2=2 решение
4
3
2
1
1
2
3
a 2 b2
z
Поскольку в рассматриваемой
задаче z 0, то z
пропорциональна d и максимум
значения z достигается в точке,
максимально удаленной от
прямой z=0.
max d
0
-1 -1 0
X1+2X2=10
Область W
1
X1
4
5
6
7
8
9
10
11
-2
-3
Z=3X1+2X2=0
x1 x 2 6
2 x1 x 2 10
X1+X2=6
x1 4 , x2 2
z 3 * 4 2 * 2 16
6

7.

Пример решения в EXCEL (S=3, G=12)
Функция цели:
Z Sx1 Gx2
Ограничения:
a x1 / G x2 / S 0,25 0
b Sx 2Gx GS 0
1
2
c 2 Sx1 Gx2 GS 0
x 0
1
x2 0
В первую строку вводим обозначения: x1, x2, z, a, b, c.
В ячейки A2 и B2 вводим начальные нулевые значения.
В ячейки С3, D3, E3,F3 вводим формулы
Получаем
7

8.

Команда «Поиск решения»
В Excel 2010 и более поздних версиях, если эта надстройка не
использовалась, ее необходимо установить.
Выбираем: Файл/Параметры Excel/Надстройки/ Поиск решения/
Кнопка «Перейти»/ Поиск решения/ OK
Команда «Поиск решения»
появится на вкладке «Данные»
8

9.

Во вкладке Данные запускаем команду Поиск решения
Целевая ячейка - это
там, которую мы хотим
максимизировать, это
результат. У нас это C2.
Ставим выбор
"максимум".
Изменяя ячейки ставим диапазон ячеек,
от которых зависит
итог.
Вводим каждое
ограничение отдельно,
используя кнопку
Добавить.
Окно для добавления
ограничений
9

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

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.