Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 187491
28.06.2013, 20:47
130.00 руб.
0 3 1
Образование
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:

Решить задачу симплекс-методом:

f=9*x1+10*x2+16*x3 (min - найти минимальное значение функции)

Ограничения:

x1, x2, x3>=0;

18*x1+15*x2+12*x3<=360;

6*x1+4*x2+8*x3<=192;

5*x1+3*x2+3*x3<=180.

Обсуждение

давно
Гордиенко Андрей Владимирович
Мастер-Эксперт
17387
18345
29.06.2013, 00:14
общий
29.06.2013, 01:06
Адресаты:
Здравствуйте!

Странная задача. Ведь очевидно, что при неотрицательных переменных х1, х2, х3 минимум целевой функции, в которую эти переменные входят с положительными коэффициентами, достигается при нулевых значениях этих переменных. Если Вы правильно привели условие задачи, то какие могут быть проблемы с её решением? И симплекс-метод явно не нужен.

В самом деле, формально, ограничения заданы неравенствами. Преобразуем их в равенства путём введения новых неотрицательных переменных х4, х5, х6:
18х1+15х2+12х3+х4=360,

6х1+4х2+8х3+х5=192,

5х1+3х2+3х3+х6=180.

В результате имеем задачу линейного программирования с n = 6 переменными и m = 3 независимыми уравнениями.

Оптимальное решение, если оно существует, достигается в одной из опорных точек, где по крайней мере k = n - m = 6 - 3 = 3 переменных равны нулю. Выберем первые k = 3 переменные (х1, х2, х3) в качестве свободных и выразим через них остальные m = 3 (х4, х5, х6) переменные:
х4 = -18х1 - 15х2 - 12х3 + 360,

х5 = -6х1 - 4х2 - 8х3 + 192,

х6 = -5х1 -3х2 - 3х3 + 180.


Если все свободные переменные равны нулю (х1 = х2 = х3 = 0), то
х4 = 360,

х5 = 192,

х6 = 180.

Получили допустимое решение, потому что числа 360, 192, 180 неотрицательны. Это решение является и опорным. Функция f выражена через свободные переменные, и при х1 = х2 = х3 = 0 f = 0. Все коэффициенты при свободных переменных положительны, поэтому уменьшить f мы не можем, поскольку свободные переменные должны быть неотрицательны. Значит, найденное решение - оптимальное.
Об авторе:
Facta loquuntur.
давно
Aleksandrkib
Посетитель
317729
109
29.06.2013, 02:33
общий
Адресаты:
Здравствуйте! Разместил задачу по просьбе другого человека. Видимо, он что-то напутал. Получается, необходимо найти не минимальное, а максимальное значение функции.
Если возможно, решите, пожалуйста, задачу при данном условии.
давно
Гордиенко Андрей Владимирович
Мастер-Эксперт
17387
18345
29.06.2013, 10:25
общий
это ответ
Здравствуйте, Aleksandrkib!

При неотрицательных переменных х1, х2, х3 минимум целевой функции, в которую эти переменные входят с положительными коэффициентами, достигается при нулевых значениях этих переменных. Поэтому будем считать, что требуется найти максимум функции f.

Ограничения заданы неравенствами. Преобразуем их в равенства путём введения новых неотрицательных переменных х4, х5, х6:
18х1 + 15х2 + 12х3 + х4 = 360,

6х1 + 4х2 + 8х3 + х5 = 192,

5х1 + 3х2 + 3х3 + х6 = 180.

В результате имеем задачу линейного программирования с n = 6 переменными и m = 3 независимыми уравнениями.

Оптимальное решение, если оно существует, достигается в одной из опорных точек, где по крайней мере k = n - m = 6 - 3 = 3 переменных равны нулю. Выберем первые k = 3 переменные (х1, х2, х3) в качестве свободных и выразим через них остальные m = 3 (х4, х5, х6) переменные (базисные):
х4 = -18х1 - 15х2 - 12х3 + 360, (1)

х5 = -6х1 - 4х2 - 8х3 + 192, (2)

х6 = -5х1 - 3х2 - 3х3 + 180. (3)


Если все свободные переменные равны нулю (х1 = х2 = х3 = 0), то х4 = 360, х5 = 192, х6 = 180.
Получили допустимое решение, потому что числа 360, 192, 180 неотрицательны. Это решение является и опорным. Функция f выражена через свободные переменные, и при х1 = х2 = х3 = 0 f1 = 0. Получили первое допустимое решение (0, 0, 0, 360, 192, 180).

Чтобы увеличить f, увеличим х3 до 24, следуя уравнению (2). Тогда при х1 = 0, х2 = 0 значения базисных переменных х4 = -288 + 360 = 72, х5 = 0, х6 = -72 + 180 = 108. Новое допустимое решение (0, 0, 24, 72, 0, 108), а f2 = 16 * 24 = 384 > f1.

Выразим теперь х3, х4, х6 и f через х1, х2, х5:
х3 = -(3/4)x1 - (1/2)x2 - x5 + 24, (4)

x4 = -18x1 - 15x2 - 12x3 + 360 = -18x1 - 15x2 - 12(-(3/4)x1 - (1/2)x2 - x5 + 24) + 360 = -9x1 - 9x2 + 12x5 + 72, (5)

x6 = -5x1 - 3x2 - 3x3 + 180 = -5x1 - 3x2 - 3(-(3/4)x1 - (1/2)x2 - x5 + 24) + 180 = -(11/4)x1 - (3/2)x2 + 3x5 + 108, (6)

f = 9x1 + 10x2 + 16x3 = 9x1 + 10x2 + 16(-(3/4)x1 - (1/2)x2 - x5 + 24) = -3x1 + 2x2 - 16x5 + 384 [$8594$] max.


Чтобы увелічіть f, увеличим x2 до 8, следуя уравнению (5). Тогда при х1 = 0, х5 = 0 значения базисных переменных х3 = -4 + 24 = 20, х4 = 0, х6 = 96. Новое допустимое решение (0, 8, 20, 0, 0, 96), а f3 = 400 > f2.

Выразим теперь х2, х3, х6 через х1, х4, х5:
х2 = -х1 - (1/9)x4 + (4/3)x5 + 8, (7)

x3 = -(3/4)x1 - (1/2)x2 - x5 + 24 = -(3/4)x1 - (1/2)(-х1 - (1/9)x4 + (4/3)x5 + 8) - x5 + 8) - x5 + 24 = -(1/4)x1 + (1/18)x4 - (5/3)x5 + 20, (8)

x6 = -5x1 - 3x2 - 3x3 + 180 = -5x1 - 3(-х1 - (1/9)x4 + (4/3)x5 + 8) - 3(-(1/4)x1 + (1/18)x4 - (5/3)x5 + 20) + 180 =

= -(5/4)x1 + (1/6)x4 + x5 + 96, (9)

f = -3x1 + 2x2 - 16x5 + 384 = -3x1 + 2(-х1 - (1/9)x4 + (4/3)x5 + 8) - 16x5 + 384 = -x1 - (2/9)x4 - (40/3)x5 + 400 [$8594$] max. (10)


Из выражения (10) для целевой функции видно, что увеличение базисных переменных приводит лишь к уменьшению её значения. Следовательно, оптимальное решение достигнуто. Оно равно (0, 8, 20, 0, 0, 96). При этом fmax = 400.

Ответ: х1 = 0, х2 = 8, х3 = 20, fmax = 400.

Решение задачи при помощи надстройки "Поиск решения" в табличном процессоре MS Excel дало тот же результат.

С уважением.
Об авторе:
Facta loquuntur.
Форма ответа