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