Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Пример решения ЗЛП модифицированным симплекс-методом

Пример решения ЗЛП модифицированным симплекс-методом. Приведем решение рассмотренной ранее задачи (1.34)-(1.35), основанное на использовании процедуры модифицированного симплекс-метода. По аналогии с п. 1.4.3 оно начинается с выбора очевидного исходного базиса, образуемого столбцами {5,2,3}. Для него уже были вычислены Δ-1(q)) и b(q)), поэтому заполнение начальных таблиц T1 и Т2(1) не представляет труда.

На первой итерации мы переписываем нулевую строку


из Т2(1) в T1 и, умножив ее на матрицу A, получаем строку оценок

Так как a0(1)) содержит отрицательные элементы, то делаем вывод о неоптимальности плана, соответствующего базису β(1), и, выбрав наименьшую отрицательную оценку (-88), получаем номер столбца, вводимого в базис, l = 4.

Переписываем столбец

из таблицы T1 в Т2(1) и пересчитываем его координаты относительно текущего базиса, т. е. умножаем матрицу Δ-1(q)), расположенную в таблице Т2(1) слева, на а4.

После заполнения таблицы Т2(1) данными по вводимому в новый базис столбцу можно перейти к определению номера выводимого столбца. Эта процедура осуществляется в полной аналогии с обычным симплекс-методом. Рассмотрев отношения элементов bi(1)) и ai,l(1)) для {i 1:m| ai,l(1))>0} и определив минимальное из них, находим, что r = 2. Следовательно, столбец с номером N2(q)) = 2 должен быть выведен из базиса. Таким образом, получаем очередной допустимый базис задачи с N(2)) = {5, 4, 3}. Элемент a2,3(1)) является ведущим (обведен кружком). Применив формулы (1.43)-(1.46), переходим к симплекс-таблице, соответствующей второй итерации Т2(2), и полагаем индекс текущей итерации q = 2.

Повторяя те же самые действия (их легко проследить по приводимым здесь таблицам Т2(2) и Т2(3), на третьей итерации мы получим оптимальный план задачи и оптимальное значение целевой функции, которые извлекаются из второго столбца таблицы Т2(3). Легко заметить, что в процессе решения мы «прошли» по той же самой последовательности допустимых базисных планов, которая встречалась в п. 1.4.3.