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

1.

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

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

3.

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

4.

Геометрический метод решения
Построение многоугольника ограничений:
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 2 x1 x2 0: x1 0 x2 0; x1 1 x2 2
4

5.

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

6.

Пример решения в 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 и А3 вводим начальные нулевые значения.
В ячейки С3, D3, E3,F3 вводим формулы
Получаем
6

7.

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

8.

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

9.

Пример решения в EXCEL
9

10.

Отчет в EXCEL
10

11.

Задание 2.
Математическая постановка задачи
11