Детерминированные линейные модели с непрерывными переменными

1. Моделирование систем

Лекция 3:
Детерминированные линейные модели с
непрерывными переменными

2. Часть 1

Общая постановка задач
и алгоритм их решения

3. Формальная постановка задачи

с x
i i
min(max);
i
j : ai , j xi b j ;
i
i : xi 0.

4. Линейное программирование

Дж. Данциг.
Целевая функция
Симплекс

5. Основные постулаты линейного программирования

1.
2.
Оптимальное решение всегда
принадлежит одной из вершин
симплекса.
Локально оптимальное решение
задачи линейного
программирования одновременно
является и глобально оптимальным.

6. Пример 1

Определить оптимальное решение задачи:
5x 1 - 4x 2 13x 3 - 2x 4 x 5 20;
x - x 5x - x x 8;
1 2
3
4
5
x 1 6x 2 - 7x 3 x 4 5x 5 min;
x i 0; i 1,2,3,4,5.
где: хi – непрерывная неотрицательная переменная;
Решение – симплекс методом.

7. Выделение базисных переменных.

Пусть в качестве базисных (не равных нулю) переменных выбраны х1 и х5:
x1 = 8 + x2 – 5x3 + x4 – x5. Отсюда: 5х1 = 40 + 5х2 – 25х3 + 5х4 – 5х5
(2)
Подставляя (2) в первое равенство системы (1), получим:
40 + 5х2 – 25х3 + 5х4 – 5х5 – 4х2 + 13х3 – 2х4 + х5 = 20.
Отсюда следует:
х2 – 12х3 + 3х4 – 4х5 + 20 = 0.
Окончательное равенство, включающее х5, имеет вид:
1
3
x 2 3x 3 - x 4 x 5 5
4
4
(3)
Подставляя (3) в выражение для х1, получим:
х1
3
1
х 2 2х 3 х 4 3
4
4
(4)
После подстановки х1 и х5 в целевую функцию, получим:
28 8х 2 24х 3 5х 4 min
(5)

8. Эквивалентная каноническая форма задачи (1)

- 0,25х 2 3х 3 - 0,75х 4 х 5 5;
х - 0,75х 2х - 0,25х
3;
1
2
3
4
min;
28 8х 2 - 24х 3 5х 4
i, x i 0.
х1 и х5 – базисные переменные.
Базисное решение: х1=3; x5=5; x2=x3=x4=0.
Значение целевой функции = 28.

9. Переход к новому базису

Т.к. коэффициент при х3 в целевой функции отрицателен, то
увеличение х3 вызовет уменьшение функционала цели.
Т.о. введению в базис подлежит х3. Теперь следует выбрать
переменную, выводимую из базиса:
х1 = 3 – 2х3
из равенства (4)
х5 = 5- 3х3
5 из равенства (5)
х
3
Если :
3 то х5 станет <0, что недопустимо.
х3
х3
3
2
3
то х1 станет <0, что недопустимо.
2
5 3
х 3 min , .
3 2
из базиса выводится х1.
Новый базис имеет вид:
х3 = 1,5; x5 = 0,5; x1=x2=x4=0; f(x) = -8
Значение целевой функции уменьшилось с 28 до –8.
Новая система имеет вид:
- 0,375х 4 х 5 0,5;
- 1,5х 1 0,875х 2
1,5;
0,5х 1 0,375х 2 х 3 - 0,125х 4
12х
- х2
2х 4 - 8 min
1
где х3 и х5 – базисные переменные.

10. Переход к новому базису

Т.к. коэффициент при х2 в целевой функции
отрицателен, в базис вводится х2. Для того, чтобы
определить, какая переменная выводится из базиса,
проанализируем выражения, получаемые из 1-го и 2го равенств:
х 5 0,5 - 0,875х 2 х 2 0,5/0,875
х 3 1,5 0,375х 2 - не ограничивает величину х2
4
Т.о. х 2 0,5/0,875
7
3 4 12
Отсюда х 3 1,5 * , а х 5 0
8 7
7
4
12
Новый базис x2 ; x3 ; x1 x4 x5 0
7
7

11. Канонический вид системы с учетом нового базиса

3
8
4
12
x 4 x5 ;
7 x1 x 2
7
7
7
1
2
3
12
x3 x 4 x5 ;
x1
7
7
7
7
72
11
8
60
x 4 x5
min
x1
7
7
7
7
Поскольку все коэффициенты небазисных
переменных положительны, полученное
решение является глобально оптимальным:
4 12
x опт 0, , ,0,0 ;
7 7
f x опт
60
7

12. Настройка пакета Simplexwin 3.1 –ввод числа переменных и ограничений

Настройка пакета Simplexwin 3.1 –
ввод числа переменных и ограничений

13. Ввод исходных данных в пакет Simplexwin 3.1

14. Вывод результатов пакетом Simplexwin 3.1

15. Достоинства и недостатки симплекс-метода

1. Достоинства:
Гарантия глобально оптимального
решения.
Высокое быстродействие независимо от
размерности.
Наличие большого числа программных
реализаций.
2. Недостатки:
Решаются только линейные задачи с
непрерывными неотрицательными
переменными.

16. Самостоятельно

Решить задачу симплекс-методом,
добавив переменные:
S=5x₁+8x₂+3x₃
max;
2x₁+3x₂+4x₃ ≤ 12;
x₁≥0; x₂ ≥0; x₃ ≥0.

17. Часть 2

Важный частный случай:
задача с одним
ограничением

18. Задача с одним видом ресурса

Требуется определить вектор переменных Х, который бы
максимизировал финансовые поступления на предприятие:
xi ci max;
i
xi ai b;
i
i : xi 0,
(1)
где: хi – объем выпускаемой продукции i-го вида (непрерывная
неотрицательная переменная); сi – стоимость единицы выпускаемой
продукции i-го вида; b – величина имеющегося ресурса (например,
человекочасы); аi, – затраты единственного вида ресурса,
приходящиеся на единицу i-го вида продукции.

19. Алгоритм поиска решения задачи (1)

Ганс Христиан Андерсен
Начало,
1 S=0.
3
Ввод n, b, ci, ai,
2 i=1,2,…n
Все наряд-заказы
ранжируются таким
образом, что:
1 j n 1 :
9 Конец
алгоритма
8
Печать S и xi j
4
7 S S x с .
i i
j
j
сi j
ai j
ci j 1
ai j 1
.
j=1
6 x b .
i
j
ai j
Блок-схема алгоритма

20. Достоинства и недостатки алгоритма

1. Достоинства:
Гарантия глобально оптимального
решения.
Простота реализации.
Высокое быстродействие.
Низкие требования к ресурсам
компьютера.
2. Недостаток:
Узкий диапазон применения.

21. Пример 2

Решить самостоятельно, пользуясь
приведенным выше алгоритмом и
симплекс методом:
S=5x₁+9x₂+3x₃
max;
2x₁+3x₂+4x₃ ≤ 12;
x₁≥0; x₂ ≥0; x₃ ≥0.
Ответ: x₁=0; x₂ =4; x₃ =0, S =36.
max

22. Задача с одним видом ресурса и ограничениями на выпуск каждого вида продукции

Требуется определить вектор переменных Х, который бы максимизировал финансовые
поступления на предприятие:
xi ci max;
i
xi ai b;
i
i : d i xi 0,
где: х – объем выпускаемой
продукции i-го вида (непрерывная
неотрицательная переменная); с – стоимость единицы выпускаемой
продукции i-го вида; b – величина имеющегося ресурса (например,
человекочасы); а – затраты единственного вида ресурса, приходящиеся на
единицу i-го вида продукции, di - верхняя граница выпуска i-го вида
продукции.
i
i
i,

23. Алгоритм поиска решения задачи (2)

Начало,
S=0.
1
Ввод n, b, ci, ai,
2 i=1,2,…n
3
Все наряд-заказы
ранжируются таким
образом, что:
1 j n 1 :
сi j
ai j
ci j 1
ai j 1
4 j=1
9
Нет
Конец
алгоритма
8 b=0
Да
b
xi j min d i ; .
5
ai j
7 сi j 0.
6 b b xi j ai j .
.

24. Пример 3

Решить самостоятельно, пользуясь
приведенным выше алгоритмом и
симплекс методом:
S=5x₁+9x₂+3x₃
max;
2x₁+3x₂+4x₃ ≤ 12;
4≥x₁≥0; 2≥x₂ ≥0; 3≥x₃ ≥0.
Ответ: x₁=3; x₂ =2; x₃=0; S=33.

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

Область допустимых решений ограничена.
Аналитическая
форма
10 x1 x 2 max;
x1 x 2 1;
x1 x 2 2;
x 2 x 1;
2
1
xi 0; i 1,2.
Графическая
интерпретация
-x1+x2=1
x1+x2=2
x1-2x2=1

26. Достоинства и недостатки алгоритма

1. Достоинства:
Гарантия глобально оптимального
решения.
Простота реализации.
Высокое быстродействие.
Низкие требования к ресурсам
компьютера.
2. Недостаток:
Узкий диапазон применения.

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

Формальная
постановка
с1 x1 min;
x 2 x 2;
2
1
x x 4;
1
2
xi 0; i 1,2.
Графическая
интерпретация

28. Задачи ЛП на графах

Задача о максимальном потоке: На
графе G(X,U), множество вершин
которого X, а множество дуг U,
определить максимальный поток
из вершины – источника в вершину
– сток, если поток f (i,j) по дуге не
может превысить пропускной
способности дуги r(i,j).

29. Графическое представление задачи о максимальном потоке.

f 1, i max; целевая функция;
i 1
j 1, n : f i, j f i, уравнение непрерывности
i
i,j U , f i, j r i, j ограничения сверху и
i, j U , f i, j 0 снизу на величину потока по дуге

30. Задача о максимальной циркуляции на взвешенном орграфе

Содержательная постановка задачи: на
взвешенном орграфе с бикомпонентами
требуется распределить замкнутые
потоки (циркуляции) в контурах таким
образом, чтобы:
Их сумма в одной и той же дуге не
превышала пропускной способности
этой дуги.
Суммарный вес всех циркуляций должен
быть максимальным.

31. Формальная постановка задачи о максимальной циркуляции

s(ai ) max;
i
( p, q ) U : s (ai ) r ( p, q );
ai A ( p , q )
i : s (a ) 0.
i
Здесь s(аi ) - циркуляция в i-о контуре; r(p,q) –
пропускная способность дуги (p,q) множества U;
A(p,q) – подмножество контуров, которым
принадлежит дуга (p,q).

32. Графовая иллюстрация

Аналитическое
представление
Граф
1
2
7
2
4
3
3
9
4
a1= 1-3-1; a2= 1-2-4-3-1;
a3= 2-4-2.
5
s (a1 ) s (a2 ) s (a3 ) max;
s (a1 ) 2;
s (a1 ) s (a2 ) 4;
s (a2 ) s (a3 ) 3;
s (a ) 5;
3
s (a3 ) 3;
i : s (ai ) 0.

33. Решение задачи программой поиска максимальных циркуляций на планарных графах

34. Прямые и двойственные задачи

Прямая задача
L x c, x max;
AX B;
X 0
3x5 x6 max;
x1 3x 2 2 x3
2 x 2 x x x 2 x x 1;
1
2
3
4
5
6
4 x1 3x 2 x3 2 x 4 x5 2 x6 1;
j, x j 0

35. Двойственная задача

L y B, Y min;
T
A Y C;
Y 0
y1 y 2 min;
2 y 4 y 1;
2
1
2 y1 3 y 2 3;
y1 y 2 2;
y1 2 y 2 0;
2 y1 y 2 3;
y1 2 y 2 1;
y 0; y 0.
2
1

36. Графическое решение двойственной задачи

37. Решить самостоятельно графически

Задача № 1
x1 5 x2 min;
a
x1 x2 4;
Задача № 2
2 x1 x2 x3 7 x4 2 x5 min;
x1 x2 x3 x4 0 x5 1;
2 x1 x2 x3 0 x4 x5 7;
Перейти к двойственной задаче