Пример решения методом Гомори

Пример решения методом Гомори. Задание . Решить целочисленную задачу линейного программирования, используя метод Гомори: F(X) = x 1 + 2x 2 4x 1 + 3x 2 24 -x 1 + x 2 3. Решение находим с помощью сервиса Метод Гомори (случай целочисленного решения). Этап I . Решим прямую задачу линейного программирования симплекс-методом.

Определим максимальное значение целевой функции F(X) = x 1 + 2x 2 при следующих условиях-ограничений. 4x 1 + 3x 2 24 -x 1 + x 2 3. Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

4x 1 + 3x 2 + 1x 3 + 0x 4 = 24 -1x 1 + 1x 2 + 0x 3 + 1x 4 = 3 Введем новую переменную x 0 = x 1 + 2x 2 . Выразим базисные переменные 3, 4 через небазисные. x 0 = 0+x 1 +2x 2 x 3 = 24-4x 1 -3x 2 x 4 = 3+x 1 -x 2. Переходим к основному алгоритму симплекс-метода.

Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x 0 . x 0 = 0+x 1 +2x 2 x 3 = 24-4x 1 -3x 2 x 4 = 3+x 1 -x 2 В качестве новой переменной выбираем x 2.

Вычислим значения D 2 по всем уравнениям для этой переменной. и из них выберем наименьшее: min (24. 3. 3. 1 ) = 3 Вместо переменной x 4 в план войдет переменная x 2 . Выразим переменную x 2 через x 4 и подставим во все выражения.

После приведения всех подобных, получаем новую систему, эквивалентную прежней: x 0 = 6+3x 1 -2x 4 x 3 = 15-7x 1 +3x 4 x 2 = 3+x 1 -x 4. Полагая небазисные переменные x = (3, 2) равными нулю, получим новый допустимый вектор и значение целевой функции: x = (-3, 0, 0, 2), x 0 = 6 x 0 = 6+3x 1 -2x 4 x 3 = 15-7x 1 +3x 4 x 2 = 3+x 1 -x 4 В качестве новой переменной выбираем x 1 . Вычислим значения D 1 по всем уравнениям для этой переменной. и из них выберем наименьшее: min (15.

7. - ) = 2 1 / 7 Вместо переменной x 3 в план войдет переменная x 1 . Выразим переменную x 1 через x 3 и подставим во все выражения. Дополнительное ограничение имеет вид: 1 / 7 - 1 / 7 x 3 - 4 / 7 x 4 0 Преобразуем полученное неравенство в уравнение: 1 / 7 - 1 / 7 x 3 - 4 / 7 x 4 + x 5 = 0 коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу.

Категория: Ответы на вопросы.

Ответы юристов


Ответ юриста

live-torrent.ru

Вы не можете добавить ответ к этому вопросу. Авторизуйтесь или присоеденитесь к этому вопросу.



Похожие вопросы:


Юристы - участники

Займы

 

Социальные сети

© live-torrent.ru 2013-2018. При использовании материалов сайта, ссылка на сайт обязательна.