Лидеры рейтинга

ID: 226425

Konstantin Shvetski

Мастер-Эксперт

959

Россия, Северодвинск


ID: 259041

Алексеев Владимир Николаевич

Мастер-Эксперт

514

Россия, пос. Теплоозёрск, ЕАО


ID: 401284

Михаил Александров

Академик

354

Россия, Санкт-Петербург


ID: 137394

Megaloman

Мастер-Эксперт

312

Беларусь, Гомель


ID: 400669

epimkin

Профессионал

191


ID: 400484

solowey

Профессор

71


ID: 401888

puporev

Профессор

53

Россия, Пермский край


8.1.6

02.01.2021

JS: 2.2.2
CSS: 4.2.0
jQuery: 3.5.1


 

Консультации и решение задач по исследованию операций, линейному, динамическому программированию, теории игр и сетевому планированию.

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


Коцюрбенко Алексей Владимирович
Статус: Старший модератор
Рейтинг: 2103
Зенченко Константин Николаевич
Статус: Старший модератор
Рейтинг: 269
Gluck
Статус: 6-й класс
Рейтинг: 240
 

Перейти к консультации №:
 

Консультация онлайн # 187491
Раздел: • Исследование операций
Автор вопроса: Aleksandrkib (Посетитель)
Дата: 28.06.2013, 20:47
Поступило ответов: 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.

Состояние: Консультация закрыта

Здравствуйте, 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 → 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 → max. (10)


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

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

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

С уважением.


Консультировал: Гордиенко Андрей Владимирович (Специалист)
Дата отправки: 29.06.2013, 10:25

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

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

Гордиенко Андрей Владимирович

Специалист

ID: 17387

1

= общий = |  29.06.2013, 00:14 |  цитировать |  профиль |  личное сообщение
Aleksandrkib:

Здравствуйте!

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

В самом деле, формально, ограничения заданы неравенствами. Преобразуем их в равенства путём введения новых неотрицательных переменных х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 мы не можем, поскольку свободные переменные должны быть неотрицательны. Значит, найденное решение - оптимальное.

Последнее редактирование 29.06.2013, 01:06 Гордиенко Андрей Владимирович (Специалист)

=====
Facta loquuntur.

Aleksandrkib

Посетитель

ID: 317729

2

= общий = |  29.06.2013, 02:33 |  цитировать |  профиль |  личное сообщение
Гордиенко Андрей Владимирович:

Здравствуйте! Разместил задачу по просьбе другого человека. Видимо, он что-то напутал. Получается, необходимо найти не минимальное, а максимальное значение функции.
Если возможно, решите, пожалуйста, задачу при данном условии.

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