Консультации Портала - Консультация #198160

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 198160

06.04.2020, 21:49

0.00 руб.

1 1 1

Образование

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:

необходимо решить задачи линейного программирования симплекс- методом.

Прикрепленные файлы:

3b7f40c61659804de6af54c7e0ebe858a41491c8.jpg

скачать (18.00 кБ)

Обсуждение

давно

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

Старший Модератор
312929
1973

13.04.2020, 02:59

общий

это ответ

Здравствуйте, vjzgjxnf-2019!

2. Полагая переменные x[sub]1[/sub], x[sub]5[/sub], x[sub]6[/sub] свободными и равными 0, получим начальный опорный план X = (0, 3, 6, 5, 0, 0). Составим симплекс-таблицу:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₄[/col][col]5[/col][col]1[/col][col]0[/col][col]2[/col][col]1[/col][col]-4[/col][col]0[/col][/row]
[row][col]x₂[/col][col]3[/col][col]0[/col][col]1[/col][col]0[/col][col]-2[/col][col]2[/col][col]2[/col][/row]
[row][col]x₃[/col][col]6[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col]-4[/col][col]-1[/col][/row]
[row][col]z[/col][col]0[/col][col]-3[/col][col]0[/col][col]-2[/col][col]3[/col][col]0[/col][col]0[/col][/row]
[/table]
Этот опорный план допустим, так как все свободные члены (5, 3, 6) положительны, но неоптимален, так как в индексной строке z есть отрицательные коэффициенты.
Наибольший по модулю отрицательный коэффициент в индексной строке равен -3. Соответствующая ему переменная x[sub]1[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (5/1, 3/0, 6/0) = (5, [$8734$], [$8734$]). Наименьшее среди них положительное значение равно 5. Соответствующая ему переменная x[sub]4[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col][/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col silver]x₄[/col][col silver]5[/col][col gray]1[/col][col silver]0[/col][col silver]2[/col][col silver]1[/col][col silver]-4[/col][col silver]0[/col][/row]
[row][col]x₂[/col][col]3[/col][col silver]0[/col][col]1[/col][col]0[/col][col]-2[/col][col]2[/col][col]2[/col][/row]
[row][col]x₃[/col][col]6[/col][col silver]0[/col][col]0[/col][col]1[/col][col]0[/col][col]-4[/col][col]-1[/col][/row]
[row][col]z[/col][col]0[/col][col silver]-3[/col][col]0[/col][col]-2[/col][col]3[/col][col]0[/col][col]0[/col][/row]
[/table]
Разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки, равен 1. Заменяем строку x[sub]4[/sub] на строку x[sub]1[/sub], для чего делим все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col][/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col silver]x₁[/col][col silver]5[/col][col gray]1[/col][col silver]0[/col][col silver]2[/col][col silver]1[/col][col silver]-4[/col][col silver]0[/col][/row]
[row][col]x₂[/col][col]3[/col][col silver]0[/col][col]1[/col][col]0[/col][col]-2[/col][col]2[/col][col]2[/col][/row]
[row][col]x₃[/col][col]6[/col][col silver]0[/col][col]0[/col][col]1[/col][col]0[/col][col]-4[/col][col]-1[/col][/row]
[row][col]z[/col][col]0[/col][col silver]-3[/col][col]0[/col][col]-2[/col][col]3[/col][col]0[/col][col]0[/col][/row]
[/table]
Исключаем новую базисную переменную x[sub]1[/sub] из остальных строк, для чего вычитаем из них строку x[sub]1[/sub], умноженную на соответствующий элемент столбца x[sub]1[/sub] (0 для x[sub]2[/sub], x[sub]3[/sub] и -3 для z):
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₁[/col][col]5[/col][col]1[/col][col]0[/col][col]2[/col][col]1[/col][col]-4[/col][col]0[/col][/row]
[row][col]x₂[/col][col]3[/col][col]0[/col][col]1[/col][col]0[/col][col]-2[/col][col]2[/col][col]2[/col][/row]
[row][col]x₃[/col][col]6[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col]-4[/col][col]-1[/col][/row]
[row][col]z[/col][col]15[/col][col]0[/col][col]0[/col][col]4[/col][col]6[/col][col]-12[/col][col]0[/col][/row]
[/table]
Получаем новый опорный план X = (5, 3, 6, 0, 0, 0). Он допустим, так как все свободные члены (5, 3, 6) положительны, но неоптимален, так как в индексной строке z есть отрицательный коэффициент -12 в столбце x[sub]5[/sub]. Других отрицательных коэффициентов нет, поэтому переменная x[sub]5[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (-5/4, 3/2, -3/2). Наименьшее среди них положительное значение равно 3/2. Соответствующая ему переменная x[sub]2[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col silver]x₅[/col][col]x₆[/col][/row]
[row][col]x₁[/col][col]5[/col][col]1[/col][col]0[/col][col]2[/col][col]1[/col][col silver]-4[/col][col]0[/col][/row]
[row][col silver]x₂[/col][col silver]3[/col][col silver]0[/col][col silver]1[/col][col silver]0[/col][col silver]-2[/col][col gray]2[/col][col silver]2[/col][/row]
[row][col]x₃[/col][col]6[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col silver]-4[/col][col]-1[/col][/row]
[row][col]z[/col][col]15[/col][col]0[/col][col]0[/col][col]4[/col][col]6[/col][col silver]-12[/col][col]0[/col][/row]
[/table]
Разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки, равен 2. Заменяем строку x[sub]2[/sub] на строку x[sub]5[/sub], для чего делим все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col silver]x₅[/col][col]x₆[/col][/row]
[row][col]x₁[/col][col]5[/col][col]1[/col][col]0[/col][col]2[/col][col]1[/col][col silver]-4[/col][col]0[/col][/row]
[row][col silver]x₅[/col][col silver]3/2[/col][col silver]0[/col][col silver]1/2[/col][col silver]0[/col][col silver]-1[/col][col gray]1[/col][col silver]1[/col][/row]
[row][col]x₃[/col][col]6[/col][col]0[/col][col]0[/col][col]1[/col][col]0[/col][col silver]-4[/col][col]-1[/col][/row]
[row][col]z[/col][col]15[/col][col]0[/col][col]0[/col][col]4[/col][col]6[/col][col silver]-12[/col][col]0[/col][/row]
[/table]
Исключаем новую базисную переменную x[sub]5[/sub] из остальных строк, для чего вычитаем из них строку x[sub]5[/sub], умноженную на соответствующий элемент столбца x[sub]5[/sub] (-4 для x[sub]1[/sub], x[sub]3[/sub] и -12 для z):
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col]x₆[/col][/row]
[row][col]x₁[/col][col]11[/col][col]1[/col][col]2[/col][col]2[/col][col]-3[/col][col]0[/col][col]4[/col][/row]
[row][col]x₅[/col][col]3/2[/col][col]0[/col][col]1/2[/col][col]0[/col][col]-1[/col][col]1[/col][col]1[/col][/row]
[row][col]x₃[/col][col]12[/col][col]0[/col][col]2[/col][col]1[/col][col]-4[/col][col]0[/col][col]3[/col][/row]
[row][col]z[/col][col]33[/col][col]0[/col][col]6[/col][col]4[/col][col]-6[/col][col]0[/col][col]12[/col][/row]
[/table]
Получаем новый опорный план X = (11, 0, 12, 0, 3/2, 0). Он допустим, так как все свободные члены (11, 12, 3/2) положительны, но неоптимален, так как в индексной строке z есть отрицательный коэффициент -6 в столбце x[sub]4[/sub]. Других отрицательных коэффициентов нет, поэтому переменная x[sub]4[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (-11/3, -3/2, -3). Среди них нет положительных значений, следовательно, дальнейшая оптимизация невозможна и решением задачи будет x[sub]1[/sub] = 11, x[sub]3[/sub] = 12, x[sub]5[/sub] = 3/2, x[sub]2[/sub] = x[sub]4[/sub] = x[sub]6[/sub] = 0, z[sub]max[/sub] = 3[$183$]11 + 2[$183$]12 - 3[$183$]0 = 57.

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.