- •2) Переход от общей (стандартной) формы злп к канонической.
- •Переход от канонической формы к стандартной.
- •1.1.3. Контрольные вопросы:
- •1.1.4. Варианты индивидуальных заданий:
- •1.2 Графический метод решения задач
- •1.2.2. Теоретическая часть:
- •1.2.3. Контрольные вопросы:
- •1.2.4. Варианты индивидуальных заданий:
- •1.3 Симплекс-метод решения задач линейного программиро-вания
- •1.3.2. Теоретическая часть
- •1.3.2.1. Симплекс-метод
- •1.3.2.2. Cимплекс-метод для неполного базиса (м-метод).
- •1.3.3. Контрольные вопросы:
- •1.3.4. Варианты индивидуальных занятий
- •1.4 Двойственность в линейном программировании
- •1.4.2. Теоретическая часть:
- •1.4.2.1. Общая модель задачи
- •1.4.2.2. Решение злп с помощью графического анализа двойственной задачи
- •1.4.3. Контрольные вопросы:
- •1.4.4. Варианты индивидуальных заданий.
- •1.5 Транспортная задача (т-задача)
- •1.5.2. Теоретическая часть:
- •1.5.2.1. Алгоритм решения т-задачи.
- •1.5.2. Примеры решения т-задачи.
- •1.5.3. Контрольные вопросы.
- •1.5.4. Варианты индивидуальных заданий:
- •1.6 Целочисленное программирование
- •1.6.2. Теоретическая часть: Описание метода отсечений (метода Гомори).
- •1.6.3. Контрольные вопросы:
- •1.6.4. Варианты индивидуальных заданий.
- •2.1.2.2. Метод Франка-Вулфа решения задач квадратичного программирова-
- •2.2 Контрольные вопросы.
- •2.3. Индивидуальные задания.
1.6.3. Контрольные вопросы:
-
Что называется правильным отсечением, как оно формируется?
-
Какой геометрический смысл имеет правильное отсечение?
-
В чем состоит идея метода Гомори решения задач целочисленного программи-рования?
-
Сформулируйте признак неразрешимости задачи целочисленного программи-рования.
1.6.4. Варианты индивидуальных заданий.
Найти решение целочисленных ЗЛП.
|
x1 |
4x2 max, |
|
2x1 3x2 max, |
|
x1 2x2 max, |
|||||||||||||
|
2x1 4x2 |
7, |
|
x1 4x2 |
14, |
|
5x1 7x2 |
21, |
|||||||||||
1. |
10x1 3x2 15, |
2. |
2x1 3x2 12, |
3. |
x1 3x2 |
8, |
|||||||||||||
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
||||||||||||||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
||||||||||||||
|
x1 x2 |
max, |
|
x1 2x2 |
max, |
|
8x1 6x2 |
max, |
|||||||||||
|
6x1 5x2 |
20, |
|
2x1 9x2 36, |
|
2x1 5x2 |
11, |
||||||||||||
4. |
2x1 3x2 |
10, |
5. |
x1 x2 7, |
6 . |
4x1 x2 10, |
|||||||||||||
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
||||||||||||||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
||||||||||||||
|
x1 3x2 |
max, |
|
x1 2x2 max, |
8x1 6x2 |
max, |
|||||||||||||
|
2x1 4x2 17, |
|
2x1 2x2 |
7, |
|
3x1 5x2 |
11, |
||||||||||||
7. |
10x1 3x2 |
10, |
8. |
4x1 5x2 |
9, |
9. |
4x1 x2 8, |
|
|||||||||||
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
||||||||||||||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
||||||||||||||
|
8x1 6x2 |
max, |
|
2x1 3x2 |
max, |
|
x1 2x2 |
max, |
|||||||||||
|
2x1 5x2 |
12, |
|
x1 4x2 14, |
|
3x1 2x2 5, |
|||||||||||||
10. |
4x1 x2 10, |
11. |
2x1 3x2 |
12, |
12 . |
x2 2, |
|
|
|||||||||||
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
||||||||||||||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
||||||||||||||
|
x1 x2 |
max, |
|
2x1 x2 |
max, |
|
2x1 x2 max, |
||||||||||||
|
20x1 10x2 75, |
|
2x1 3x2 11, |
|
x1 x2 |
7, |
|||||||||||||
13. |
12x1 7x2 55, |
14. |
4x1 x2 |
10, |
15. |
4x1 5x2 |
5, |
||||||||||||
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
||||||||||||||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 x2 max, |
|
x1 |
x2 |
max, |
|
2x1 |
x2 |
max, |
||||||||||||||||||
|
x1 |
2x2 |
16, |
|
x1 |
2x2 |
10, |
|
2x1 |
3x2 12, |
|||||||||||||||||
16. |
2x1 x2 |
16, |
17. |
2x1 x2 |
10, |
18. |
4x1 |
x2 |
10, |
||||||||||||||||||
|
x1 |
0, x2 0, |
|
x1 |
0, x2 0, |
|
x1 0, x2 0, |
||||||||||||||||||||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
||||||||||||||||||||||
|
x1 |
x2 max, |
|
5x1 |
10x2 |
max, |
|
x1 2x2 |
max, |
||||||||||||||||||
|
x1 |
7x2 |
30, |
|
3x1 |
x2 |
8, |
|
2x1 x2 |
16, |
|||||||||||||||||
19. |
2x1 2x2 5, |
20. |
x1 7x2 |
30, |
21. |
2x1 3x2 9, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|||
|
5x1 3x2 |
max, |
|
x1 x2 max, |
|
5x1 6x2 |
max, |
|
|
2x1 4x2 |
15, |
|
x1 2x2 |
10, |
|
2x1 x2 12, |
|
22. |
5x1 x2 10, |
23. |
3x1 x2 |
10, |
24. |
3x1 5x2 24, |
||
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|||
|
2x1 x2 max, |
|
5x1 6x2 |
max, |
|
5x1 6x2 |
max, |
|
|
x1 x2 5, |
|
2x1 x2 12, |
|
2x1 3x2 |
18, |
||
25. |
2x1 3x2 |
6, |
26. |
3x1 3x2 |
24, |
27. |
2x1 x2 12, |
|
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|||
|
12x1 15x2 max, |
|
x1 x2 |
max, |
|
x1 x2 |
max, |
|
|
4x1 3x2 |
12, |
|
10x1 6x2 50, |
|
10x1 6x2 50, |
||
28. |
2x1 5x2 |
10, |
29. |
10x1 15x2 150, |
30 . |
3x1 4x2 24, |
||
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|
x1 0, x2 0, |
|||
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
|
x1 , x2 - целые. |
-
НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.
2.1 КЛАССИЧЕСКАЯ ЗАДАЧА МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВА-НИЯ
2.1.1. Цель: закрепить теоретические знания и практические навыки анализа на-хождения экстремума функции одной или нескольких переменных, а также использо-вания метода множителей Лагранжа для нахождения глобального экстремума.
2.1.2. Теоретическая часть:
2.1.2.1. Общая формулировка задачи
Классическая задача математического программирования заключается в выборе
таких значений некоторых переменных x j . j 1, n , подчиненных системе ограничений в
форме равенств вида gi (x) 0, i 1, m; m n , при которых достигается максимум или минимум заданной функции f (x) . То есть она имеет следующий вид
-
(x) extr(max, min);
gi (x) bi ,i 1, m;m n.
Могут встретиться следующие варианты задач:
а) n=1, m=0;
б) n>1, m=0;
в) n>1, m0.
-
случае наличия ограничений находится условный экстремум целевой функции, если они отсутствуют, говорят о безусловном экстремуме, нахождение которого сво-
дится к определению и исследованию стационарных точек функции f (x) .
Чтобы классическим методом можно было найти экстремальные точки, функции f(x) и gi(x) должны быть непрерывными и дифференцируемыми, хотя бы по второй по-рядок включительно.
Стационарные точки функции f(x) в случаях а) и б) находятся как решения систе-мы уравнений
f
0, j 1,n.
x j
Система уравнений определяет положение стационарных точек внутри области, среди которых, кроме экстремальных, могут быть особые точки типа “седла”.
Чтобы определить тип стационарных точек для функции одной переменной, сле-дует проверить достаточные условия, сформулированные для экстремальной и седло-вой точек. Так, например, достаточные условия существования максимума функции одной переменной - это отрицательная величина производной четного порядка
-
2k
x2k
0, (k 1,n) .
Для функции двух переменных достаточным условием существования максимума является отрицательная определенность матрицы Гессе:
|
|
|
|
2 |
f |
|
2 |
f |
|
|
|
|
|||||||||||||
2 f |
0, |
|
|
x2 |
|
|
x x |
|
|
0; |
|
||||||||||||||
|
|
|
2 |
1 |
|
|
1 |
f |
2 |
|
|||||||||||||||
x2 |
|
|
|||||||||||||||||||||||
|
|
|
f |
|
2 |
|
|
|
|
||||||||||||||||
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
x |
2 |
x |
|
|
x2 |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
1 |
|
|
|
2 |
|
|
|
|
-
иных случаях задание достаточных условий значительно усложняется. Практическое значение получил метод сведения задачи на условный экстремум к
задаче на безусловный экстремум, основанный на использовании функции Лагранжа (так называемый метод множителей Лагранжа). Введем в рассмотрение вектор множи-телей Лагранжа ( 1 ,..., m ) и рассмотрим функцию L(x, ) , называемую функцией Лагранжа, состоящую из исходной функции и суммы ограничений, умноженных на со-ответствующие множители i:
m
L(x, ) f (x) ( i gi (x)).
-
1
Необходимые условия существования экстремума состоят в решении следующей системы уравнений для отыскания координат стационарных точек
L |
0, j |
|
, |
L |
0, i |
|
. |
|
||
1, n |
1,m |
|
||||||||
|
|
|
||||||||
x j |
i |
|
50
Анализ функции f(x) в найденной точке позволяет определить вид экстремума (максимум или минимум) данной функции.
Пример 1: Найти
f (x) (x1 1)2 x22 extr,
при условии g(x) x12 x2 1 0.
Выразив |
x |
2 |
x2 1 |
и подставив значение x2 |
в f(x), получим функцию одной пе- |
|
|||||||||||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
2, дифференцируя которую по х1 |
|
||||||||||||||||
ременной f (x ) (x 1)2 |
(x2 |
1) |
2 x4 |
3x2 |
2x |
|
|||||||||||||||||||
1 |
|
|
|
1 |
1 |
|
|
1 |
1 |
1 |
|
|
|
||||||||||||
, приходим к уравнению 2x3 3x |
1 |
0 . Это уравнение имеет единственный вещест- |
|
||||||||||||||||||||||
|
|
|
|
|
|
1 |
1 |
|
|
|
|
|
|
|
|||||||||||
венный корень |
|
х1=0,313. А так как |
вторая |
производная 2 f x2 |
6x 3 0 , то |
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
|
функция f(x1) в найденной точке имеет минимум. При этом х2 =1,098, а f(x)= 1,678. Пример 2. Для приведенного примера функция Лагранжа имеет вид
L(x, ) (x1 1)2 x22 (x12 x2 1).
Проверим необходимые условия экстремума
|
|
|
|
|
|
L |
|
x ( 1) 1 0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
x1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
L |
2x2 0, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
x2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
L |
x2 |
x |
|
1 0. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Решение этой системы уравнений дает х1=0,313, |
х2 =1,098, |
=2,196. |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Произведем анализ функции f(x1, х2) в стационарной точке х=(0,313; 1,098) с по- |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
мощью матрицы Гессе. Находим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 f |
|
2 f |
|
2 f |
|
|
2 f |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2; |
|
2; |
|
|
|
|
|
|
|
2. |
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
2 |
x x |
|
x |
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
2 |
x |
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Так |
|
|
|
|
x1 |
|
x2 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
как |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 |
0 |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
f |
|
|
0 |
|
и матрица Гессе положительно определена, т.е. |
|
|
|
|
0, |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
x2 |
|
|
|
0 |
2 |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
то функция f(x) выпукла и в исследуемой точке имеет минимум.