- •1 3(1) . Линейное программирование. Симплекс-метод. Привести числовой пример решения задачи линейного программирования симплекс-методом с использованием симплекс-таблиц.
- •2 3(3) . Свойства бинарных отношений. Рефлексивность, симметричность, транзитивность, иррефлексивность, антисимметричность, интранзитивность.
- •3 3(5) .Последовательная и связанная память. Представление линейных списков в последовательной и связанной памяти. Достоинства и недостатки того и другого представления
- •Логическое высказывание и его свойства. Логические операции (связки). Формализация логических суждений.
- •Машина Тьюринга, ее структура и свойства. Проблема остановки мт.
- •3 8(5) .Понятие обхода дерева. Виды обходов двоичного дерева. Определение структуры двоичного дерева по двум заданным обходам. Рекурсивные алгоритмы обходов двоичных деревьев.
- •1 16(1) . Цикломатика графов. Цикломатическое число. Цикломатический базис. Связь циклов графа с цикломатическим базисом.
- •2. Процессы в операционных системах. Общие понятия. Ресурсы процесса. Создание и уничтожение процесса.
- •3. Xml базы данных. Dtd и xml Schema
- •1 19(1) . Условная вероятность события. Формула полной вероятности и формула Байеса. Независимость событий (попарная и в совокупности). Примеры. Условная вероятность
- •Независимость событий
- •Формула полной вероятности
- •Теорема гипотез (формула Байеса)
- •2 19(4) . Логическое высказывание и его свойства. Логические операции (связки). Формализация логических суждений.
- •3 19(6) . Операционная система. Функции, назначение. Многопользовательские системы. Мультипрограммные системы.
- •1. Условная вероятность события. Формула полной вероятности и формула Байеса. Независимость событий (попарная и в совокупности).
- •1Нф (Первая Нормальная Форма)
- •2Нф (Вторая Нормальная Форма)
- •3Нф (Третья Нормальная Форма)
- •Алгоритм нормализации (приведение к 3нф)
- •К 43(6) лассы бинарных отношений. Отношение порядка и его свойства.
- •3 43(7) .Структура языка sql. Оператор select. Типы соединений таблиц.
1 3(1) . Линейное программирование. Симплекс-метод. Привести числовой пример решения задачи линейного программирования симплекс-методом с использованием симплекс-таблиц.
Пусть дана задача ЛП в канонической форме: <c,x>® max, A1+A2+...+An=A0, x³0. Пусть известно некоторое опор. решение x*=( x*1 , x*2 ,..., x*n ) и базис этого решения:B=(Ai1,Ai2,…,Aim).
Будем считать, что базисная матрица является единичной матрицей (B=E), т.е. система ограничений задачи имеет форму приведенной системы, а вектор A0 не имеет отрицательных координат: ai ³ 0, (i=1,2,...,m). Очевидно, что ранг базисной матрицы B равен m - количеству ограничений-уравнений (m единичных векторов Ai1,Ai2,…,Aim составляют линейно-независимую систему). Работу по симплекс-методу рассмотрим по шагам.
шаг 1. Разложить векторы A0 ,A1 ,A2 ,...An по базису, то есть, найти все числа xkj (j=0,1,2,...,n; k=1,2,...,m ) такие, что: Aj=x1j + x2j +...+ xmj . Учитывая тот факт, что B=(Ai1,Ai2,…,Aim) =E=B-1, коэффициенты разложения определяются непосредственно параметрами задачи: xkj=akj , xk0=ak (j=1,2,...,n; k=1,2,...,m ). При этом, координаты опорного решения x*=( x*1 , x*2 ,..., x*n ) опредедяются следующим образом: =ak=xk0 ,(k=1,2,...,m ); =0, (j=1,2,...,n; jÏ{i1,i2,...,im}) .
шаг 2. Найти оценки всех свободных векторов Aj, jÏ{i1,i2,...,im} и вычислить значение ЦФ:
Dj = .
Z0= .
Результаты вычислений занести в симплекс-таблицу.
Баз. |
Сбаз |
A0 |
c1 |
c2 |
|
cs |
|
cj |
|
cn |
|
|
|
A1 |
A2 |
|
As |
|
Aj |
|
An |
Ai1 |
Ci1 |
x10 |
x11 |
x12 |
|
x1s |
|
x1j |
|
x1n |
Ai2 |
Ci2 |
x20 |
x21 |
x22 |
|
x2s |
|
x2j |
|
x2n |
|
|
|
|
|
|
|
|
|
|
|
Ai3 |
Ci3 |
xr0 |
xr1 |
xr2 |
|
xrs |
|
xrj |
|
xrn |
|
|
|
|
|
|
|
|
|
|
|
Aik |
Cik |
xk0 |
xk1 |
xk2 |
|
xks |
|
xkj |
|
xkn |
|
|
|
|
|
|
|
|
|
|
|
Aim |
Cim |
xm0 |
xm1 |
xm2 |
|
xms |
|
xmj |
|
xmn |
|
|
Z0 |
D1 |
D2 |
|
Ds |
|
Dj |
|
Dn |
шаг 3. Если все оценки Dj ³ 0 (j=1,2,...,n), процесс закончен. Очередное опорное решение - оптимальное решение задачи. Координаты этого решения x*=(x*1 , x*2 ,..., x*n) однозначно определяются коэффициентами разложения вектора A0 : =ak=xk0 ,(k=1,2,...,m); = 0, (j=1,2,...,n; jÏ{i1,i2,...,im}).
шаг 4. Последовательно просматриваются все свободные векторы, имеющие отрицательные оценки. Если обнаруживается такой вектор Aj (Dj < 0), для которого все xkj £ 0, (j=1,2,...,n), вычисления прекращаются: задача не имеет решения, так как ее целевая функция не ограничена сверху на допустимом множестве. В против. случае выполняется следующий шаг.
шаг 5. Выбирается любой вектор, имеющий отрицательную оценку (обычно предпочтение отдается вектору с максимальной по абсолютной величине отрицательной оценкой - это, как правило, сокращает общее количество вычислительных операций). Пусть, для определенности, выбран вектор As (Ds < 0). Этот вектор будет вводиться в базис.
ш
3(2)
. Тогда из базиса будет выводиться вектор . Выполняется следующий шаг.
шаг 7. Для нового базиса Внов=( ),
с использованием основных формул пересчитываются координаты разложения всех векторов Aj (j=0,1,2,...,n):
Далее, вычисляется значение целевой функции на новом опорном решении:
Zнов= Zст - Ds.
В этом выражении Zнов и Zст - соответственно, новое и старое значения целевой функции. Наконец, вычисляются оценки свободных векторов в новом базисе. Здесь используется выражение:
.
При ручном счете для вычислений по приведенным выше формулам используется правило “крест-накрест”. Результаты вычислений заносятся в новую симплекс-таблицу и выполняется шаг 3.
П
5
4
-4
-9
Баз
Cбаз
A0
A1
A
2
A
3
A
4
A
3
-4
8/3
2/3
1/3
1
0
A4
-9
10/3 5
1/3 1/2
2/3 1
0 0
1 3/2
Tабл.1
-122/
3
-32/
3
-34/
3
0
0
5
4
-4
-9
Баз
Cбаз
A0
A1
A
2
A
3
A
4
A
3
-4
1 2
1/
2 1
0 0
1 2
-1/
2 -1
A2
4
5
1/
2
1
0
3/
2
Табл.2
16
-5
0
0
17
5
4
-4
-9
Баз
Cбаз
A0
A1
A
2
A
3
A
4
A
1
5
2
1
0
2
-1
A2
4
4
0
1
-1
2
Табл.3
26
0
0
10
12
x*=(2,4,0,0);
Zопт.=
26.