Cтраница 1
Любое базисное решение имеет по крайней мере I T положительных переменных. Для выполнения / условий ( 13) необходимо, чтобы хотя бы одна переменная в этих ограничениях была отличной от нуля. [1]
Любое базисное решение такой задачи является целочисленным, следовательно, состоит из нулей и единиц и представляет собой переставляющую матрицу. [2]
Любое базисное решение вырождено, но система неизбыточна. [3]
Так как элементы любого базисного решения не образуют замкнутых цепей между собой, то с помощью эквивалентных преобразований матрицы С ( сц) можно все х-выбранные элементы сц обратить в нуль. [4]
В силу теоремы 1.5 любое базисное решение невырождено, а в силу условий дополнительной нежесткости любое оптимальное решение двойственной задачи должно удовлетворять соответствующей невырожденной системе из N двойственных равенств; следовательно, решение двойственной задачи единственно. [5]
В силу характера задачи допустимое решение содержит ровно п переменных, равных единице, тогда как любое базисное решение включает п п - 1 переменных. Это обстоятельство приводит к выводу, что применение симплексного алгоритма не обеспечивает в полной мере учета особой структуры модели назначений. В данном разделе будут изложены три отличных от симплексного метода решения задачи о назначениях. [6]
В силу треугольной структуры можно последовательно найти значения соответствующих двойственных переменных ( выбрав некоторую переменную и приписав ей произвольное значение) при условии, что известно любое базисное решение. [7]
Из рассмотренного выше случая 1 следует, что любое базисное-решение вырождено. Таким образом, избыточность влечет за собой вырожденность любого базисного решения. [8]
Очевидно, все переменные должны быть неотрицательными и для выполнения условий ( 12) - ( 13) должно соблюдаться условие ue Q. Нетрудно понять, что это условие выполняется автоматически для любого базисного решения. [9]
Прежде чем перейти к анализу оптимальности планов и способам их улучшения, выясним, каким требованиям должны удовлетворять составляемые планы. Условие закрытости модели транспортной задачи означает, что среди m n уравнений системы ограничений независимых только m n - 1, поэтому в любом базисном решении этой системы должно быть m n - 1 базисных переменных. Поскольку свободные переменные в таком решении равны нулю, то в транспортной таблице им будут соответствовать пустые клети. [10]
Пусть дана некоторая основная задача линейного программирования. Предположим, что эта задача имеет оптимальное решение. Тогда существует по крайней мере одно оптимальное базисное решение, которое может быть получено симплекс-процессом из любого базисного решения. [11]
Это можно строго показать, умножив каждое из ограничений ( 3) на - 1, а затем сложив любые т п - 1 ограничений и используя условие ( 5) для упрощения констант в правой части. Следовательно, любое из уравнений спроса и поставок ( 2) или ( 3) можно без ущерба опустить. В итоге имеем модель, содержащую т - - п - 1 независимых ограничений, вследствие чего в любое базисное решение входит именно такое число переменных. [12]