Материал: Материалы по курсу (часть 2)

n=5 (кол-во переменных)

m=3 (кол-во уравнений)

n-m=2=k

Пусть и свободные переменные

Осуществили обратный переход

и свободные

Штриховка так, чтобы

Получили открытую ОДР, следовательно, решение на [AB]

(если бы по условию , то решения не было бы)

Решение в опорной точке (.)А:

6. Симплекс-метод решения задачи лп

Алгоритм выполнения симплекс-метода решения задачи ЛП:

• Запишем исходные данные в виде системы уравнения, где ,,, –свободные переменные

стремится к минимуму

• Введем базовые переменные

n = 7 (указано в дано к задаче), m = 3 (кол-во уравнений), k = n – m = 4 (базовых переменных)

Базисными обозначим:

Приравняем все свободные переменные (т.е. все оставшиеся) к нулю.

Мы получили первую опорную точку , однако же обратим внимание на то, что при стоит минус. Это значит, что, сделав переменную положительной, мы получим меньшее значение . В таких случаях говорят, что функция убывает быстрее при положительных значениях . Базисные переменные априори ≥ 0, следовательно сделаем базисной.

Очень просто: у тебя стоит -, значит если , например, 4 → , что меньше, чем, например, если бы стал →

Если бы мы получили такую функцию L, где все значения были бы с , то такое значение называлось бы оптимальным (то, к чему мы стремимся по ходу решения).

• Процедура замены свободной переменной на базисную

В контексте нашей задачи в первом и во втором неравенстве есть отрицательный . Необходимо выбрать какую базисную переменную будем заменять или . Смотрим на коэф-ты при иксе, в первом случае функция убывает быстрее, т.к. меньше, чем , следовательно выбираем .

Выразили через и подставили получившееся выражение во второе неравенство вместо (в третьем нечего было заменять).

Очень доходчиво: первым делом мы поделили все в первом неравенстве на коэф-т, стоящий при (2) и перенесли в правую часть новые свободные переменные, а в левой остался как базисный.

Обратите внимание тоже меняется

Таким образом получаем промежуточную систему уравнений:

Пусть , тогда , хороший результат, но все же мы видим, что перед стоит минус, значит можно сделать L ещё меньше, необходима вторая замена по тому же алгоритму. Выбираем , т.к. других вариантов просто нет.

Сделаем последние преобразования

7. Табличный алгоритм замены переменных.

Рассмотрим применение данного алгоритма на конкретном примере.

Рассмотрим систему пяти уравнений-ограничений:

с четырьмя свободными переменными: x₁, x₂, x₃, x₄. Пусть нам требуется вывести из числа свободных какую-нибудь переменную, например x₂ и перевести ее в базисные, а взамен ее ввести в число свободных какую-то базисную переменную, скажем y3 короче, мы хотим обменять местами переменные x₂ и y₃. Эту замену мы будем символически обозначать

Посмотрим, какие действия надо для этого осуществить.

Вообще, можно было бы для каждой новой системы уравнений проводить переразрешение заново, т.е. для замены .

Мы взяли бы в третьем уравнении (6.1) член а₃₂х₂, содержащий х₂ (назовем его «разрешающим членом»; разумеется, предполагаем а₃₂≠0 ) , перенесли бы его в левую часть, а у₂ – в правую; решили бы уравнение относительно х₂ и подставили бы выражение для х₂ во все остальные уравнения. Процедура достаточно громоздкая, требующая напряженного внимания; при ее выполнении легко ошибиться (особенно при большом числе уравнений). Но так как здесь каждый раз нужно проделывать одни и те же операции, то их достаточно выполнить один раз в общем виде и вывести правила преобразования, которые затем можно применять автоматически.

Целесообразно предварительно несколько преобразить систему уравнений (6.1), представив их правые части как разности между свободными членами и суммой остальных:

(6.1)

Обозначая

получим:

(6.2)

Форму записи уравнений (6.2) мы будем называть стандартной.

Очевидно, вместо того чтобы полностью записывать уравнения (6.2), можно ограничиться заполнением стандартной таблицы, где указаны только свободные члены и коэффициенты при переменных. Первый столбец таблицы мы отведем под свободные члены, второй, третий, четвертый и пятый – под коэффициенты при переменных х₁, х₂, х₃, х₄ в стандартной форме (6.2). Стандартная таблица для системы (6.2) имеет следующий вид (Табл.6.1).

Таблица 6.1.

Мы хотим произвести замену Т.е. перевести переменную х₂ в число базисных, а переменную у₃ - в число свободных. Выделим в стандартной таблице разрешающий элемент α₃₂ (обведем его кружком); выделим так же жирными линиями строку и столбец, в которых стоит разрешающий элемент. Эту строку и этот столбец мы будем называть разрешающей строкой и разрешающим столбцом (см.табл. 6.2).

Пусть , тогда

Отметим, что в выражении L все знаки при коэф-тах положительны, больше преобразовывать ничего не нужно, мы получили минимальное значение

Ответ: