Какую размерность будет иметь матрица задачи, если привести условия транспортной задачи к канонической форме задачи линейного программирования [c.347]
Пример 7.1. Приведение к канонической форме задачи линейного программирования [c.190]
После приведения к канонической форме задача линейного программирования выглядит следующим образом [c.211]
Каноническая форма задачи линейного программирования [c.191]
Каноническая форма задачи линейного программирования 191 Каноническое разложение 300 Квадратическая форма 70 [c.328]
Нетрудно заметить, что платой за переход от общей формы задачи линейного программирования к канонической является рост ее размерности, что, при прочих равных условиях, является фактором, усложняющим процесс решения. [c.20]
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот. [c.190]
В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть неотрицательными. Допустим, что [c.191]
Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме [c.191]
Xs+t 0. Полагая, что n=S + m и g+,- = 0 (z = l, 2,. .. т), получаем возможность рассматривать задачу линейного программирования (за счет увеличения числа переменных) в следующей канонической форме [c.31]
Полагая, что п = S + т и s+i = 0 (i = 1, 2,. .., т), получаем возможность рассматривать задачу линейного программирования (благодаря увеличению числа переменных) в следующей канонической форме найти [c.36]
Эта задача отличается от рассматривавшейся задачи линейного программирования в канонической форме тем, что в ней требуется отыскать максимум, а не минимум. Понятно, что план ж такой задачи оптимален тогда и только тогда, когда k план опорный, так как векторы а, и 2 линейно независимы — образуют базис. [c.41]
Переход к канонической форме. Подавляющее большинство известных методов решения задач линейного программирования предназначены для канонических задач. Поэтому начальный этап решения всякой общей задачи линейного программирования обычно связан с приведением ее к некоторой эквивалентной канонической задаче. [c.19]
Поскольку задача (3.15)-(3.17) является частным случаем задачи линейного программирования, ее можно привести к канонической форме. При этом достаточно просто устанавливается, что ранг матрицы задачи равен т-1, где т — количество вершин в сети. Введем дополнительно еще некоторые понятия, используемые при описании свойств сетевых задач. [c.125]
Задача линейного программирования (ЗЛП) в общей постановке имеет три формы произвольную, симметричную и каноническую. [c.45]
Задача линейного программирования имеет каноническую форму, если в ее систему ограничений входят только линейные уравнения и условия неотрицательности для всех неизвестных, т. е. в задаче (9.1)—(9.4) / = Л4 = = 1, 2,. .., т , a J=N = 1, 2,. .., п . [c.191]
Задача линейного программирования в канонической форме имеет следующий вид [c.191]
Задачу линейного программирования (9.7)—(9.9) в канонической форме можно записать в виде [c.191]
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. В самом деле, рассмотрим задачу (9.1)—(9.4), [c.191]
Если все оценки некоторого базиса опорного решения не положительны, то оно является оптимальным решением задачи линейного программирования в канонической форме. (Признак оптимальности.) [c.195]
Для оптимального опорного решения задачи линейного программирования в канонической форме всегда существует базис, все оценки которого не положительны. [c.195]
Предположим, что симплекс-таблица для задачи линейного программирования в канонической форме при- [c.195]
Если известно некоторое опорное решение задачи линейного программирования в канонической форме, то ее можно решать симплекс-методом. Симплекс-метод—это направленный перебор опорных решений, при котором значение целевой функции на каждом последующем опорном решении меньше, чем на предыдущем (для задачи минимизации). [c.197]
Для решения симплекс-методом задачи линейного программирования в канонической форме необходимо выполнить ряд последовательных шагов. На каждом шаге либо возникает базис нового опорного решения, причем на новом опорном решении значение целевой функции обязательно меньше, чем на предыдущем (для задачи минимизации), либо меняется базис исходного опорного решения. [c.197]
Конечность симплекс-метода. Если задача линейного программирования в канонической форме не имеет вырожденных опорных решений, то через конечное число шагов симплекс-метода она будет решена. [c.198]
Семейство задач линейного программирования в канонической форме [c.214]
Пусть по-прежнему (А, Ъ, с) — набор параметров условий задачи линейного стохастического программирования, приведенной к канонической форме. (А, Ъ, с) — соответствующие математические ожидания, /о — набор индексов векторов оптимального базиса задачи. [c.298]
Если привести условия трансдортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (т+п)хтп. Матрицы систем уравнений в ограничениях (3.2) и (3.3) имеют ранги, равные соответственно тип. Однако, если, с одной стороны, просуммировать уравнения (3.2) по т, а с другой — уравнения (3.3) по я, то в силу (3.5) получим одно и то же значение. Из этого следует, что одно из уравнений в системе (3.2)-(3.3) является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен т + п-, и ее невырожденный базисный план должен содержать т + п- ненулевых компонент. [c.110]
СИМПЛЕКСНАЯ ТАБЛИЦА (СИМПЛЕКС-ТАБЛИЦА) [simplex table] — матрица, служащая средством перебора допустимых базисных решений (невырожденной) задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования, приведенной к "канонической форме"75 последовательное ее преобразование по т.н. симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый результат — план, обеспечивающий экстремальное значение целевой функции. [c.322]
Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные я. наложены условия неотрицательности, то она называется задачей линейного программирования в канонической форме, или канонической задачей линейного программирования (КЗЛП). В матричной форме КЗЛП можно записать в следующем виде [c.18]
Векторная форма записи КЗЛП и ее применение. Рассмотрим каноническую задачу линейного программирования [c.29]
Опорные решения играют важнз /Ю Роль ПРИ решении задачи линейного программирования. т канонической форме, так как если эта задача имеет оптм мальное решение, то одно из ее оптимальных решений обязательно будет ее опорным решением. Таким образом, оптимальное решение задачи линейного программирования в канонической форме можно искать только среди ее опорных решений (а их лишь конечное число). [c.194]
Признак оптимальности ога оршого решения задачи линейного программирования в канонической форме. "Условие неограниченности целевой (функции [c.194]
По задаче линейного программирования в канонической форме (9.7)—(9.9) всегда можкшо составить таблицу (табл. 9.1). [c.194]