Консультация онлайн # 202211

Раздел: Исследование операций
Автор вопроса: kabanov.anton2010 (Посетитель)
Дата: 22.02.2022, 10:46 Консультация неактивна
Поступило ответов: 1
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
Задана каноническая модель задачи линейного программирования.
Z = CX, AX = A0, X ≥ 0, A = (aij) 3х5.
Требуется найти max Z М-методом.


Последнее редактирование 01.03.2022, 06:41 Коцюрбенко Алексей Владимирович (Старший модератор)
Вопрос перенесен из раздела Математика
Поскольку задача уже имеет каноническую форму, определяем базисные переменные системы (содержащиеся каждая только в одном уравнении системы с коэффициентом 1). Таковой, очевидно, является только x4. Первое и третье уравнение не содержат базисных переменных, поэтому введём в них неотрицательные искусственные переменные x6 = 2 + 2x1 + x2 - 2x3 и x7 = 5 - 3x1 - x2 + x3 - 6x5. Матрица A примет вид:

а в целевую функцию новые переменные войдут с большим по модулю отрицательным коэффициентом -M:

или

Составим симплекс-таблицу
БПx1x2x3x4x5x6x7РешениеОтношение
x6-2-1200102
x4114130088/3
x731-1060155/6
z-M-13-M1-1-6M00-7M
Здесь на пересечении i-ой строки и j-го столбца стоит коэффициент aij системы, предпоследний столбец содержит свободные члены ai0, являющиеся одновременно текущим решением. Последняя строка содержит соответствующие коффициенты целевой функции (для оптимального решения они должны быть неотрицательны), а в столбце свободных членов - значение целевой функции, соответствующее текущему решению.
Первоначальное решение x4 = 8, x6 = 2, x7 = 5 неоптимально, так как строка z содержит отрицательные коэффициенты. Выбираем в ней максимальный по модулю отрицательный элемент -1-6M, содержащий его столбец x5 является ведущим. Для всех неотрицательных элементов ведущего столбца находим отношения соответствующего свободного члена и элемента ведущего столбца (они занесены в последнюю колонку таблицы). Выбираем минимальное значение отношения (5/6), содержащая его строка x7 является ведущей. Элемент на пересечении ведущих строки и столбца является разрешающим (в данном случае он равен 6).
Переменная, соответствующая ведущей строке (x7) исключается из базиса, переменная соответствующая ведущему столбцу (x5) включается в базис. Для этого все элементы ведущей строки (включая свободный член), делим на разрешающий элемент (после чего он становится равным 1), затем вычитаем получившуюся ведущую строку из всех остальных (включая строку z), умножая на соответствующий коэффициент в ведущем столбце. Получаем новую симплекс-таблицу:
БПx1x2x3x4x5x6x7РешениеОтношение
x6-2-12001021
x4-1/21/29/2100-1/211/211/9
x51/21/6-1/60101/65/6-
z1/2+2M-5/6+M17/6-2M1001/6+M5/6-2M
Полученное решение x4 = 11/2, x5 = 5/6, x6 = 2 неоптимально, так как строка z содержит отрицательный коэффициент 17/8-2M в столбце x3. Выбираем его в качестве ведущего. Находим отношения свободных членов к неотрицательным элемента ведущего столбца. Минимальное из них (1) соответствует строке x6, которая становится ведущей. Следовательно, переменная x6 исключается из базиса, а переменная x3 включается в базис. Строим новую симплекс-таблицу:
БПx1x2x3x4x5x6x7РешениеОтношение
x3-1-1/21001/201
x4411/4010-9/4-1/21
x51/31/120011/121/61
z10/37/12010-17/12+M1/6+M-2
Теперь строка z не содержит отрицательных коэффициентов, следовательно, найдено оптимальное решение x1 = x2 = 0, x3 = x4 = x5 = 1, которому соотвествует максимальное значение целевой функции z = -2.

Последнее редактирование 02.03.2022, 05:06 Коцюрбенко Алексей Владимирович (Старший модератор)


Коцюрбенко Алексей Владимирович

Старший модератор
01.03.2022, 08:34
5

Мини-форум консультации # 202211

Коцюрбенко Алексей Владимирович

Старший модератор

ID: 312929

324576

= общий =    25.02.2022, 03:12
Экспертам раздела
Обратите внимание на консультацию, перенесённую из другого раздела
Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.