28. Целевая функция:
max(11x1 + 24x2 + 28x3 + 4x4 + 18x5 + 18x6 + 17x7):
Система ограничений:
8
> 4x1 + 19x2 + 27x3 + 12x4 + 24x5 + 21x6 + 13x7 = 124;
>
>
> 3x1 3x2 + 15x3 + 11x4 x5 2x6 + 29x7 = 60;
<
24x1 9x2 + 20x3 + 29x4 + 6x5 + 3x6 + 11x7 > 80;
>
> 3x1 + x2 3x3 + 19x4 9x5 4x6 + 8x7 > 3;
>
>
:18x1 + 15x2 + 23x3 + 16x4 + 12x5 + 21x6 9x7 6 100:
29.Целевая функция:
max(7x1 + 16x2 + 18x3 + 26x4 + 8x5 + 3x6 + 2x7):
Система ограничений:
8
> 21x1 8x2 + 28x3 6x4 7x5 3x6 x7 = 28;
>
>
> 26x1 + 5x2 3x3 + 19x4 + 18x5 + 16x6 + 20x7 = 106;
<
8x1 + 18x2 + 10x3 9x4 x5 + 13x6 + 3x7 > 19;
>
> 3x1 x2 + 28x3 6x4 + 29x5 8x6 4x7 > 37;
>
>
:18x1 + 25x2 10x3 x4 + 27x5 + 6x6 + 27x7 6 97:
30.Целевая функция:
max(8x1 + x2 + 24x3 + 3x4 + x5 + 18x6 + 25x7):
Система ограничений:
8
> 3x1 + 5x2 + 10x3 + 27x4 + 18x5 7x6 4x7 = 59;
>
>
> x1 + 20x2 + 17x3 + 27x4 + 18x5 7x6 6x7 = 75;
<
5x1 + 2x2 + 20x3 9x4 6x5 + 9x6 2x7 > 3;
>
> 17x1 + 11x2 + 25x3 + 15x4 + 27x5 + 23x6 + 13x7 > 124;
>
>
:30x1 + 22x2 + 22x3 + 22x4 + 4x5 + x6 2x7 6 103:
1.Выписать согласно своему номеру варианта исходные данные для выполнения практической работы.
2.Записать исходную задачу в матричной и в векторной формах.
3.Выполнить переход к эквивалентной задаче минимума, записав целевую функцию.
4.Преобразовать систему ограничений с неравенствами в систему уравнений. Записать ее. Записать преобразованную задачу в матричной и в векторной формах.
16
5.Проанализировать полученные результаты и сделать выводы.
6.Оформить отчет в печатном виде согласно рекомендациям преподавателя. В отчете должны быть подробно расписаны исходные данные задачи согласно номеру варианта, ход решения и полученные результаты по каждому пункту задания. В титульном листе отчета обязательно должны быть указаны номер варианта задания, номер группы и ФИО учащегося.
7.Защитить по отчету выполненную работу.
Примечание. Работа выполняется индивидуально.
1.Сформулируйте общий принцип оптимизации функциональной
задачи.
2.Что такое целевая функция (критерий эффективности)?
3.Для чего производится трансформация неравенств и преобразование задачи в различные формы?
Список использованных источников
1. Таха, Х. Введение в исследование операций /Х. Таха. — М. : Мир,
1986.
2.Номоконов, М. К. Лекции и практические занятия по курсу «Математическое программирование» / М. К. Номоконов. — СПб. : СПВВИУС, 1992. — 172 с.
3.Вентцель, Е. С. Исследование операций. Задачи и принципы методологии / Е. С. Вентцель. — М. : Наука, 1980.
17
Практическая работа 2
Научиться приводить системы ограничений к базисным формам и находить допустимое опорное решение. Научиться оперировать условиями ограничений в векторной и матричной формах.
2.2.1. Основные определения
n
1. W = F(x) = å cjxj — целевая функция.
j=1
2.Вектор X = (x1; x2; :::; xn) — допустимый план, удовлетворяющий ограничениям. Допустимый план, который максимизирует или минимизирует целевую функцию, называется оптимальным планом или решением задачи.
3.Число Wmax(Wmin) = Fmax(x)(Fmin(x)) — значение оптимального решения.
4.Вектор C = (c1; c2; :::; cn) — вектор коэффициентов целевой функции.
5.Вектор B = (b1; b2; :::; bm) и матрица A = (ai j) — вектор значений свободных членов и матрица коэффициентов переменных функций
ограничений.
2.2.2. Допустимые решения целевой функции
Ответом на вопрос о существовании допустимых максимальных или минимальных решений целевой функции W (x1; x2; :::; xn) = F(x), при xj > 0; j = (1;n), может быть один из вариантов:
1.Система ограничений несовместна, следовательно, решений не имеет, значит, допустимых планов нет. Задача не имеет решения.
2.Система совместная и определенная. При этом m = n = r. Матрица A = (ai j) квадратная и DA = D(ai j) 6= 0, так как r — порядок не равного нулю DA. Следовательно, система имеет только одно решение X = (x1; x2; :::; xn). Если все найденные X = (x1; x2; :::; xn) неотрицательны, то решение допустимое и оптимальное. Если хотя бы одно найденное xn из X = (x1; x2; :::; xn) отрицательно, то решение недопустимое и задача не имеет решения. Сам случай простой и решается обычными матметодами.
3.Если система совместная и неопределенная, то она имеет бесчисленное множество решений, из которых необходимо найти допустимые. В этом
18
случае r 6 m < n и останется только r уравнений, соответствующих базисному минору. В левой части уравнений сохраняем (x1; x2; :::; xr) и называем их
базисными переменными, а весь набор X = (x1; x2; :::; xr) — базисом неизвестных. В правую часть переносим оставшиеся (n r) и называем их свободными неизвестными. Решаем систему относительно базисных неизвестных, что возможно единственным образом.
Воспользуемся матричной формой AX = B. Предположим, что r = m < n — ранг матрицы равен m. Это значит, что m векторов системы линейно независимы. Полагаем, что это первые m векторов A1; A2; :::; Am. Обозначим базисные переменные как
0 1
x1
¯ Bx2 C X = B C @:::A
xm
и свободные переменные как
X˜ = |
0xm+21 |
: |
||
|
B |
xm+1 |
C |
|
|
:x:: |
|
||
|
B |
n |
C |
|
|
@ |
|
A |
|
В матрице A = (ai j) выделим матрицу D, состоящую из коэффициентов при базисных переменных (x1; x2; :::; xm), и матрицу S, состоящую из коэффициентов при свободных неизвестных (xm+1; xm+2; :::; xn). Тогда AX =
(DS) |
¯ |
|
= DX¯ +SX˜ |
= B, и если ранг D равен m, то DD 6= 0 и D — невырож- |
X˜ |
||||
|
X |
|
|
|
денная матрица, обратная к D матрица D 1. Умножаем обе части последне-
го равенства на 1, получаем 1 ¯ 1 ˜ 1 или ¯ 1 ˜
D D DX + D SX = D B EX + D SX =
1 ¯ ¯ ¯ 1 1 ˜
D B, но EX = X, а значит X = D B D SX.
Обозначим D 1B = b — вектор-столбец с элементами bi (i = 1;m) и D 1S = a — матрица размером (m (n r)) с элементами ai j, получаем си-
стему ¯ ˜ равносильную исходной .
X = b aX AX = B
Далее разворачиваем систему из матричного вида в классический
8
> x1 = b1 (a1;m+1xm+1 + a1;m+2xm+2 + ::: + a1;nxn);
>
< x2 = b2 (a2;m+1xm+1 + a2;m+2xm+2 + ::: + a2;nxn);
:::
>
>
: xm = bm (am;m+1xm+1 + am;m+2xm+2 + ::: + am;nxn);
19
переносим все неизвестные влево и получаем систему с единичным базисом:
8
> 1x1 + 0x2 + ::: + 0xm + a1;m+1xm+1 + a1;m+2xm+2 + ::: + a1;nxn = b1;
>
< 0x1 + 1x2 + ::: + 0xm + a2;m+1xm+1 + a2;m+2xm+2 + ::: + a2;nxn = b2;
:::
>
>
: 0x1 + 0x2 + ::: + 1xm + am;m+1xm+1 + am;m+2xm+2 + ::: + am;nxn = bm:
Запишем систему в матричной форме ˙ , где
AX = b
A˙ = |
0 0 |
1 |
::: 0 |
a2;m+1 |
::: a2;n 1; |
X = |
0x2 1 |
: |
||||||
|
|
1 |
0 |
::: |
0 |
a1;m+1 |
::: |
a1;n |
|
|
x1 |
|
||
|
B |
:0:: |
0 |
::: |
1 |
a |
m;m+1 |
::: |
a |
m;n |
C |
|
B:x::C |
|
|
B |
|
|
|
|
|
|
|
C |
|
B n C |
|
||
|
@ |
|
|
|
|
|
|
|
|
|
A |
|
@ A |
|
Если в такой системе с единичным базисом принять все небазисные переменные равными нулю, то получится базисное решение системы:
X = (b1; b2; :::; bm; |
0; :::; 0): |
||||||||
| |
|
{z |
|
} |
| |
|
{z |
|
} |
mn m
2.2.3.Определения
1.Если базисное решение X = (b1; b2; :::; bm; 0; :::; 0) удовлетворяет условию неотрицательности (bi > 0), то оно называется допустимым опорным решением или допустимым опорным планом.
2.Если среди bi; (i = 1; m) нет равных нулю, то опорный план называется невырожденным. Если нули есть, то опорный план называется вырожденным.
На опорном плане целевая функция всегда принимает значение равное ее свободному члену.
n
Заменим в целевой функции W = å cjxj базисные переменные на
j=1
8
> x1 = b1 (a1;m+1xm+1 + a1;m+2xm+2 + ::: + a1;nxn);
>
< x2 = b2 (a2;m+1xm+1 + a2;m+2xm+2 + ::: + a2;nxn);
:::;
>
>
: xm = bm (am;m+1xm+1 + am;m+2xm+2 + ::: + am;nxn):
Тогда она будет выражена через небазисные (свободные) переменные
n
W = c˙0 å c˙jxj;
j=m+1
где c˙0 и c˙j — новые коэффициенты целевой функции.
Если свободные переменные (xm+1; xm+2; :::; xn) примут нулевые значения, то целевая функция W = c˙0.
20