Методы нахождения опорного решения задачи линейного программирования

из "Математические методы моделирования экономических систем Изд2 "

Системы (7.42) и (7.43) будут эквивалентны в том случае, если все yf, для / = 1,г будут равны 0. Кроме того, мы считаем, что все bt 0 для / = 1,г. В противном случае соответствующие ограничения из системы (7.42) умножим на - 1. Для того чтобы yt были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные переменные yf перешли в свободные неизвестные. [c.221]
Рекомендуется вводить минимум искусственных переменных. [c.222]
Пример 7.13. Решение задачи линейного программирования симплекс-методом. Для нахождения опорного плана использовать метод искусственных переменных. [c.222]
В базис можно выделить переменную х3. Введем две искусственные переменные - yl и у2. [c.222]
Наименьший положительный элемент в строке линейной формы min = Минимальное симплекс-отношение соответствует строке переменной уг. [c.223]
После приведения системы ограничений к единичному базису целевая функция, как и базисные переменные, будет выражена через свободные переменные. Аналогичным приемом мы пользовались, когда решали задачи графическим методом с числом переменных более двух. [c.225]
Пояснение. В п.1 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование необязательно. В случае когда в столбце свободных членов встречаются отрицательные числа, будем пользоваться теоремой. [c.225]
Теорема. Если разрешающий элемент выбирать по наименьшему положительному симплекс-отношению, то после шага Жор-дана—Гаусса свободный член в разрешающей строке становится положительным, а остальные члены сохраняют свой знак, Выбор разрешающего элемента производят иначе, а именно. [c.226]
Запишем данную задачу в виде выражения 7.48 и получим табл. 7.14. [c.226]
Выберем произвольно столбец с положительным элементом. Затем по минимальному положительному отношению находим разрешающий элемент. В нашем примере он равен 1 и находится на пересечении столбца переменной х4 и первой строки (элемент отмечен квадратом). Выполняя преобразования Жордана—Гаусса, получим табл. 7.15. [c.226]
На данном этапе расчетов в табл. 7.17 мы получили три нулевых столбца, что соответствует количеству ограничений в примере. Здесь необходимо закончить преобразования Жордана-Гаусса. [c.228]

Вернуться к основной статье