1.2.1. Постановка задачи
Дана целевая функция — цель задачи:
n
max(min)W = max(min)F(x) = å cjxj = c1x1 + c2x2 + ::: + cnxn
j=1
при ограничениях
a11x1 + a12x2 + ::: + a1nxn 6 b1 a21x1 + a22x2 + ::: + a2nxn 6 b2
:::
am1x1 + am2x2 + ::: + amnxn 6 bm
и при условии xj > 0; где ( j = 1;n).
Любое множество чисел x1; x2; :::; xj; :::; xn, удовлетворяющее ограничениям, называется допустимым решением (допустимым планом).
Запишем коротко ограничения разных типов:
уравнения |
n |
|
|
|
å ajxj = bi; |
где(i = 1;m); |
|
неравенства |
j=1 |
|
|
|
> |
|
|
|
n |
где(i = 1;m); |
|
|
j=1 |
||
|
å ajxj |
6 bi; |
|
уравнения и неравенства
n |
263 |
|
å ajxj |
= |
bi; где(i = 1;m); |
j=1 |
4>5 |
|
условия неотрицательности
xj > 0; j = 1;n:
Матричная форма
max(min)CX AX 6 B X > 0;
6
где A = |
0a21 |
a22 |
::: a2n |
1, B = |
0b2 |
1, |
|||
|
a11 |
a12 |
::: |
a1n |
|
b1 |
|
||
|
Ba::: |
a |
m2 |
::: |
a |
|
C |
Bb:::C |
|
|
B m1 |
|
|
|
mnC |
B mC |
|||
|
@ |
|
|
|
|
|
A |
@ |
A |
CX и AX — произведения матриц.
0 1
x1
Bx2 C
X = B:::C, C = (c1; c2; :::; cn).
@ A xn
Векторная форма
max(min)CX
x1A1 + x2A2 + ::: + xnAn 6 B ; X > 0
0 1
a1 j
Ba2 j C
где Aj = B C при j = 1; n вектор-столбец коэффициентов xj из элементов
@ ::: A
am j
j столбца матрицы A;
0 1 b1
Bb2 C
B = B C — вектор-столбец B свободных членов или значений уравнений
@:::A
bm
(неравенств) системы ограничений;
X = (x1; x2; :::; xn) и C = (c1; c2; :::; cn) — вектор-строки переменных в задаче и коэффициентов целевой функции соответственно,
CX — скалярное произведение векторов.
Символика теории множеств
max(min)[CX : AX 6 B; X > 0]:
1.2.2. Переходы в задачах
Задача max — min
Задача
n
max å ajxj > bi (i = 1; m)
j=1
эквивалентна задаче
n
min( å ajxj) 6 ( bi) (i = 1; m):
j=1
7
Приведение неравенства к равенству
К исходному неравенству
n
å ajxj 6 bi (i = 1; m)
j=1
прибавляем
xn+1 > 0
и получаем
n
å ajxj + xn+1 = bi (i = 1; m):
j=1
Пример.
Задана целевая функция
max(x1 + 2x2 + 5x3)
с системой ограничений
8
> 2x1 x2 + x3 = 2;
>
< x1 + 2x2 + 3x3 = 5; > x1 + x2 x3 6 4;
>
: x1 + 2x2 + x3 > 1:
Вводим две переменные x4 и x5:
x4 = 4 x1 x2 + x3; x5 = 1 x1 + 2x2 + x3;
при x4; x5 > 0.
Получаем систему уравнений
8
> 2x1 x2 + x3 = 2;
>
< x1 + 2x2 + 3x3 = 5; > x1 + x2 x3 + x4 = 4;
>
: x1 2x2 x3 + x5 = 1:
Приведение равенства к неравенству
n
å ai jxj = bi (i = 1; m)
j=1
8
эквивалентно
8n
> å ai jxj 6 bi (i = 1; m);
>
>
< j=1
|
|
|
|
> |
j=1 |
|
! |
> |
|
|
|
|
|
|
|
|
|
|
> |
n |
|
|
|
( bi) (i = 1; m): |
|||||
|
|
|
|
å ai jxj |
|
|||||||||
Если |
j |
|
j |
> |
j |
j |
|
|
j j |
|
|
j |
|
|
x |
|
6 |
|
>: |
|
|
|
v |
и u |
> |
0, v |
|
> |
0. |
|
x |
|
0, то x = u |
|
|
|
|
|
||||||
Вариант выбирается по номеру студента в журнале группы.
Врамках задания каждый учащийся получает целевую функцию задачи
исистему ограничений, состоящую из двух равенств и трех неравенств.
1. Целевая функция:
max(21x1 + 17x2 + 15x3 + 4x4 + 6x5 + 3x6 + 17x7):
Система ограничений:
8
> 11x1 7x2 + 12x3 8x4 5x5 3x6 + 2x7 = 4;
>
>
> 3x1 + 14x2 + 5x3 x4 + 16x5 + 14x6 + 28x7 = 87;
<
10x1 + 29x2 4x3 + 9x4 + 18x5 + 2x6 + 26x7 > 65;
>
> 9x1 3x2 + 27x3 10x4 + 25x5 7x6 8x7 > 28;
>
>
:9x1 + 9x2 + 2x3 + 23x4 2x5 + 21x6 + 21x7 6 85:
2.Целевая функция:
max(3x1 + 17x2 + 20x3 + 13x4 + 11x5 + 15x6 + 29x7):
Система ограничений: |
|
|
|
|
|
|
|
|
|
|
|
|
|||||
8 |
27x1 + 5x2 + 10x3 + 19x4 + 8x5 |
3x6 + 14x7 = 84; |
|||||||||||||||
14x1 + 14x2 + 19x3 + 19x4 |
2x5 + 30x6 + 8x7 = 108; |
||||||||||||||||
> |
3x1 + 5x2 + 29x3 10x4 |
4x5 + 3x6 |
|
10x7 > 5; |
|||||||||||||
> |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
> |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
> |
5x |
+ 22x |
2 |
|
3x |
+ 25x |
+ 8x |
+ 27x |
+ 27x |
7 |
> |
107; |
|||||
< |
1 |
|
|
3 |
|
4 |
|
5 |
|
6 |
|
|
|
|
|||
> |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>
>
>
:7x1 + 23x2 + 29x3 + 25x4 + x5 + 7x6 + 2x7 6 86:
3.Целевая функция:
max(14x1 + 29x2 + x3 + 12x4 + 4x5 + 26x6 + 3x7):
Система ограничений:
8
> 10x1 10x2 + 13x3 + 23x4 + 23x5 4x6 + 26x7 = 88;
>
>
> 13x1 + 20x2 + 10x3 + 16x4 + 13x5 + 11x6 + 4x7 = 95;
<
3x1 + 2x2 + 13x3 + 5x4 + 3x5 x6 2x7 > 17;
>
> 29x1 + 9x2 + 6x3 + 21x4 6x5 9x6 + 13x7 > 56;
>
>
: 8x1 + 7x2 + 2x3 x4 + 25x5 + 12x6 + 11x7 6 53:
9
4. Целевая функция:
max(30x1 + 18x2 + 2x3 + 5x4 + 25x5 + 13x6 + 3x7):
Система ограничений:
8
> 5x1 10x2 + 5x3 + 10x4 + 5x5 8x6 + 5x7 = 18;
>
>
> 6x1 + 6x2 + 17x3 + 14x4 + 26x5 + 16x6 + 20x7 = 101;
<
2x1 8x2 x3 + 8x4 + 6x5 + 28x6 10x7 > 18;
>
> 26x1 + 28x2 + 18x3 + 30x4 + 14x5 + 25x6 + 29x7 > 164;
>
>
:9x1 + 9x2 + x3 + 28x4 4x5 + 26x6 9x7 6 47:
5.Целевая функция:
max(30x1 + 21x2 + 19x3 + 8x4 + 2x5 + 19x6 + 10x7):
Система ограничений:
8
> 5x1 + 8x2 + 25x3 + 10x4 + 19x5 3x6 + 17x7 = 89;
>
>
> 12x1 + 4x2 + 19x3 x4 4x5 + 8x6 + 24x7 = 66;
<
18x1 10x2 + 20x3 2x4 + 13x5 + 14x6 + 4x7 > 53;
>
> 7x1 + 2x2 7x3 5x4 + 24x5 + 4x6 + 21x7 > 23;
>
>
:x1 + 26x2 6x3 + 14x4 5x5 + 19x6 + 5x7 6 61:
6.Целевая функция:
max(20x1 + 8x2 + 4x3 + 23x4 + 27x5 + x6 + 26x7):
Система ограничений:
8
> 3x1 3x2 + 22x3 + 20x4 + 10x5 + x6 + 10x7 = 62;
>
>
> 6x1 + 6x2 + 19x3 + 5x4 + 28x5 + 2x6 + 18x7 = 77;
<
15x1 + 17x2 + 28x3 + 8x4 + 25x5 2x6 + 21x7 > 108;
>
> 2x1 3x2 + 22x3 + 17x4 + 4x5 + 24x6 6x7 > 49;
>
>
:16x1 + 14x2 8x3 + 18x4 + 21x5 7x6 + 13x7 6 75:
7.Целевая функция:
max(3x1 + 26x2 + 7x3 + 12x4 + x5 + 4x6 + 2x7):
Система ограничений:
8
> 6x1 10x2 + 8x3 + 26x4 + 7x5 x6 + 12x7 = 52;
>
>
> 2x1 9x2 5x3 + 25x4 + 27x5 + 14x6 + 11x7 = 67;
<
6x1 + x2 + 30x3 + 27x4 + 7x5 + 16x6 + 5x7 > 87;
>
> 23x1 + 2x2 + 23x3 + 2x4 + 2x5 8x6 + 2x7 > 38;
>
>
: 8x1 2x2 + 11x3 x4 + 19x5 x6 4x7 6 35:
10