Шпаргалка Матпрограммирование.

2. Различные формы записи задачи ЗЛП и спосо-бы их преобразования
1. Общей задачей ЗЛП называют задачу МП, в кот. целевая функция линейна и система ограничений, состоит из линейных уравнений и неравенств.
2. Задача ЛП представлена в канонической форме, если она имеет вид F =  ci*xj (max)
i = 1, n; j =1, m;  ai*xj = bi; xj > =0.
В этой записи система ограничений представлена в виде неравенств (уравнений) все переменные не от-рицательны каноническая (основная).
3. Задачи ЛП в симметричной форме записи, наз. задача вида
F =  ci*xj (max)
i = 1, n; j =1, m;  ai*xj < = bi; xj > =0.
Это запись с системой ограничений в виде неравенств.
4. Матричная форма канонической ЗЛП
F = C * X (max)
A * X = B; X > = 0;
C = (C1++Cn); X = (X1столбикомXn);
A = (A11матрицаAnn);
B = (B1столбикомBm);
0 = (0столбиком0)
Приведение общей задачи ЛП к каноническому виду
1. Если задача содержит переменную, на которую не наложено условие отрицательности, то ее можно представить в виде разности двух переменных Xt = Xt` - Xt``, которые будут не отрицательны Xt`, Xt`` > = 0.
2. Задачу минимизации замещают задачей максими-зации, учитывая, что целевая функция f достигает наименьшего значения, что и функция f1 = - f достигает наибольшего значения.
3. Всякое неравенство вида
а1*X1 ++ аn*Xn < = bi
преобразуется в уравнение
а1*X1 ++ аn*Xn + Xn+1 = bi
где Xn+1 - неотрицательная переменная и наз. балан-совой переменной.
Аналогично неравенство
а1*X1 ++ аn*Xn > = bi
преобразуется в уравнение
а1*X1 ++ аn*Xn - Xn+1 = bi
Приведение канонической ЗЛП к симметричному виду
Пусть дана каноническая ЗЛП
F =  ci*xj (max)
i = 1, n; j =1, m;  ai*xj = bi; xj > =0.
Пусть ранг матрицы А системы ограничений задачи равен «r». Поэтому будем считать, что первые «r» столбиков матрицы А линейно независимы. Тогда методом Гаусса система уравнений м.б. приведена к виду
Xi +  bj*xj = bi`; j =1, r; (*)
где Xi (i = 1, r) базисные переменные
Xj (j = 1, n) свободные
Выражая базисные переменные через свободные и подставляя их в целевую функцию F получим:
F =  c`j*xj + c` (max) j = 1, n
Удаляя из неравенства (*) базисные переменные получим:
 bj*xj < = bi` i = 1, r
все неотрицательны

1. Общая формулировка задачи матпрограммирования
2. Различные формы записи задачи ЗЛП и спосо-бы их преобразования
3. Геометрическая интерпретация ЗЛП. Графиче-ский метод решения
4. Опорные планы и вершины. Теорема о соответ-ствии между ними
5. Основная теорема ЛП
6. Признак оптимальности опорного плана
8. Признак неограниченности целевой функции канонической ЗЛП
9. Признак бесконечности множества оптимальных планов канонической ЗЛП
10. Теория двойственности.
12. Основное неравенство теории двойственности
13. Достаточный признак оптимальности
14. Первая теорема двойственности
15. Вторая теорема двойственности
16. Транспортная задача по критерию стоимости
17. Теорема о ранге матрицы транспортной задачи
18. Построение начального опорного плана (2 ме-тода)
19. Перераспределение поставок

Различная литература