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

Объясните, пожалуйста, мне, школьнику, симплекс метод. Как его решать (в какой последовательности и по какому алгоритму), как строить этот график по x1 x2 и т.д.

Спасибо.

задан 28 Окт '13 21:42

изменен 28 Окт '13 22:00

Deleted's gravatar image


126

воу воу воу ПАЛЕГЧЕ :]

(28 Окт '13 21:58) algogol

@algogol, я хочу в хороший Вуз поступить.

(31 Окт '13 15:14) ВладиславМСК

а без "симплекс метода" в "хороший ВУЗ" не берут?

(31 Окт '13 16:49) algogol

@algogol, берут, но мне нужно для других целей.

(1 Ноя '13 15:10) ВладиславМСК

@falcao, мне основы симплекс метода не нужны. Нужен только 1 из них понять. Геометрический смысл мне ясен, не понимаю алгебраический(т.е. Формулы). К вашему ответу лимит комметариев исперпался, пожтому пишу здесь.

(6 Ноя '13 16:36) ВладиславМСК

Алгебраический способ решения можно прочитать в книге Солодовникова. Смысл там примерно вот какой: экстремум достигается в вершине многогранника, и если мы сначала выбрали вершину произвольно, решив некую систему уравнений, то далее ищем ребро, по которому надо продвигаться, чтобы увеличить целевую функцию. По ребру мы приходим в другую вершину, и так пока не дойдём до "экстремальной", для которой увеличение невозможно. Этому соответствует процедура преобразования симплекс-таблиц.

(6 Ноя '13 19:20) falcao

@ВладиславМСК: мне эта формула тоже ни о чём не говорит. Она имеет смысл только в контексте. Грубо говоря, если я встречаю число $%\pi$%, то это общепринятая константа, а число $%x_0$% или $%r_2$% само по себе не означает ничего -- это какие-то "текущие" обозначения.

(7 Ноя '13 12:54) falcao

В принципе, можно, но я не хотел бы оставлять свой адрес где-либо в "открытом" виде. Мне можно оставить комментарий через LiveJournal -- ссылка есть в моём "профиле".

(7 Ноя '13 14:23) falcao

Я Вам написал со своего адреса, так что можно удалить этот комментарий, а также Ваш предыдущий.

(10 Ноя '13 22:46) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
0

Этот метод всё-таки не такой простой, чтобы можно было его объяснить в двух словах. Лучше об этом где-нибудь прочитать. Есть популярно изложенные статьи в журнале "Квант" -- например, эта. Страницы там можно перелистывать.

Если задача ставится для двух переменных, то основная идея следующая: рисуется на плоскости многоугольник, задающий решение системы неравенств (ограничений). Далее, если требуется максимизировать или минимизировать значение некоторой функции $%ax+by$%, то строится семейство прямых вида $%ax+by=c$%, где $%c$% -- константа. Все такие прямые друг другу параллельны, поэтому достаточно построить одну из них. Далее надо найти крайнее верхнее или крайнее нижнее положение параллельной прямой, чтобы она проходила через точку многоугольника. Соответствующее этому значение $%c$% и будет оптимальным.

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

ссылка

отвечен 28 Окт '13 21:59

Симплекс метод и регулярный симплекс одно и тоже? Просто мне нужно понять метод, для нахождения минимума используются треугольники .

(31 Окт '13 15:18) ВладиславМСК

@ВладиславМСК: Вы можете привести конкретный пример задачи, которая перед Вами стоит? Или общий вид постановки такой задачи. Тогда можно было бы точнее сказать, какого рода методы Вам нужны. Подозреваю, что в Вашем случае имеет место какой-то частный случай общего метода.

(31 Окт '13 15:44) falcao

@ВладиславМСК: я спрашивал немного не про это. Имелось в виду, какого рода класс задач Вы хотите научиться решать при помощи симплекс-метода. Здесь важна степень общности того, что подлежит изучению. Бывает знакомство с основами симплекс-метода на плоскости, на уровне школьного факультатива. У Вас в вопросе говорилось о двух координатах. Это намного проще, чем симплекс-метод для $%n$%-мерного пространства на уровне вузовского курса.

(1 Ноя '13 3:16) falcao

@falcao, для начала можно разобрать для 2-х мерного пространства. У вас есь скайп?

(1 Ноя '13 22:53) ВладиславМСК

@ВладиславМСК: для двумерного пространства достаточно популярных статей из "Кванта". Более сложный материал, мне кажется, предназначен скорее для специалистов. Скайп у меня есть, но я крайне редко им пользуюсь.

(1 Ноя '13 23:19) falcao

@falcao, в той ссылке, которую я дал, совсем другое насколько я понял.

(2 Ноя '13 14:51) ВладиславМСК

@ВладиславМСК: у меня сложилось такое впечатление, что материал по Вашей ссылке носит узкоспециальный характер. По крайней мере, изучение основ симплекс-метода не следует начинать с такого текста.

(2 Ноя '13 15:04) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
1

для школьников можно посмотреть книгу из серии "Популярные лекции по математике" вып. 48. А.С.Солодовников Системы линейных неравенств ссылка Там и про симплекс-метод рассказано немного...

ссылка

отвечен 28 Окт '13 22:11

изменен 28 Окт '13 22:11

Хорошая книжка -- как и многие другие из той же серии!

(28 Окт '13 22:16) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

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

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,521

задан
28 Окт '13 21:42

показан
1644 раза

обновлен
10 Ноя '13 22:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru