симплексное отношение

@konsul777 · Регистрация: 13.11.2012

Студворк — интернет-сервис помощи студентам

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

@Ev_Hyper · 07.07.2014, 08:12

konsul777, покажите на примере, что вы имеете ввиду.
Если я правильно понял вопрос, то берем положительную сигму, а не неотрицательную. Поэтому деления на 0 и нет
Если вы о выборе элемента а, то он тоже выбираеться из a>0, тут тоже деления на 0 нет.
Если вы о обращении в 0 одной из базисных переменных, то почитайте в литературе о проблеме вырожденности в симплекс-методе.

@konsul777 · 07.07.2014, 11:41 **[ТС]**

Ev_Hyper, к примеру имеется вот такая таблица
задача решается на минимум

берем допустим строку х1 ведущей, симплексное отношение определяется по формуле
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\theta ={b}_{i}/-{r}_{i}$
для строки х8 получаем отношение 0/1=0, либо минимальное отношение берется в строке х6?

@Ev_Hyper · 07.07.2014, 12:17

konsul777, хм...а откуда вы взяли такую формулу? Какая у вас целевая функция и ограничения?
Обычно, рассматривают только положительные значения. Предположу, что в вашем случае, наверное, все с точностью наоборот. Значит считать $https://www.cyberforum.ru/cgi-bin/latex.cgi?\theta$ для элементов >=0 не нужно.

По-моему, вы правильно выбрали ключевой элемент. Почему вас смутил 0 в b?

@konsul777 · 07.07.2014, 16:04 **[ТС]**

Ev_Hyper,

Сообщение от Ev_Hyper

хм...а откуда вы взяли такую формулу?

в методических рекомендация, выданных в универе, там как-то по-другому немного решается симплекс-метод, в отличие от учебников, которые успел просмотреть. Там дается такая форма определения максимального шага (симплексного отношения)
если $https://www.cyberforum.ru/cgi-bin/latex.cgi?{r}_{i}\geq 0$ симплексное отношение равно бесконечности
если $https://www.cyberforum.ru/cgi-bin/latex.cgi?{r}_{i}\prec 0$ симплексное отношение равно $https://www.cyberforum.ru/cgi-bin/latex.cgi?{b}_{i}/-{r}_{i}$
эта путаница в формулах напрягает, в литературе формула $https://www.cyberforum.ru/cgi-bin/latex.cgi?{b}_{i}/{r}_{i}$
Вообще, если я правильно понимаю, когда считается симплекное отношение, если элемент в ведущей строке меньше нуля, в этом случае симплексное отношение для этой строки не считается и если свободный элемент меньше нуля, то не считается симплексное отношение для этой строки, а если свободный элемент равен нулю?
считается ли для этой строки в этом случае симплексное отношение?

@S_el · 07.07.2014, 16:09

konsul777, а у вас есть эти рекомендации в электронном виде?

@Ev_Hyper · 07.07.2014, 16:19

Сообщение от konsul777

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

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

Сообщение от konsul777

Вообще, если я правильно понимаю, когда считается симплекное отношение, если элемент в ведущей строке меньше нуля, в этом случае симплексное отношение для этой строки не считается и если свободный элемент меньше нуля, то не считается симплексное отношение для этой строки, а если свободный элемент равен нулю?
считается ли для этой строки в этом случае симплексное отношение?

Не совсем понял вопрос, но я уверен, что вы легко его найдете в литературе. Краткое описание алгоритма на скриншотах:

Из литературы советую:
Банди Б. - Основы линейного программирования

@konsul777 · 07.07.2014, 17:44 **[ТС]**

Сообщение от Ev_Hyper

Не совсем понял вопрос

Допустим выбрали ведущий столбец (по максимальному модулю отрицательного коэффициента в строке целевой функции), дальше ищем ведущую (разрешающую) строку, для ее определения, мы делим каждый элемент столбца свободных членов на соответствующий ему элемент в ведущем столбце, наименьшее значение деления и укажет, какая переменная покинет базис, т.е. какая строка станет разрешающей. Так вот мне не ясно, если один из свободных членов (в столбце В) равен нулю, для строки, в которой он встретился, нужно считать отношение 0/r или для этой строки это отношение не считается, а разрешающей выбирается другая строка с наименьшим значением от деления свободного члена на элемент в ведущем столбце, где результат этого деления больше нуля?

Добавлено через 56 минут
вроде как разобрался, если в ходе решения одна из базисных переменных становится равной нулю (коэффициент B=0), в этом случае речь идет о вырожденности базиса

@Ev_Hyper · 07.07.2014, 17:52

konsul777, все, наконец-то я понял в чем вопрос. У вас один из элементов правой части B равен 0. Вы уверены, что правильно записали условие задачи? т.к в стандартной постановке на b наложено ограничение: b > 0

Добавлено через 6 минут
konsul777, в той книге, о которой я говорил, проблеме вырожденности посвещен пункт 5 второй главы.

@konsul777 · 07.07.2014, 18:01 **[ТС]**

Ev_Hyper, да вроде правильно, все ограничения и условия учел, вот текст задачи

Фабрика производит три основных типа товара. Для производства изделия типа I требуется 3 единицы сырья А и 1 единица сырья В, для производства изделия типа II - 4 единицы сырья А и 3 единицы сырья В, для производства изделия типа III - 1 единица сырья А и 2 единицы сырья В. Поставщики могут обеспечить не более 20 тыс. единиц сырья А и 10 тыс. единиц сырья В. Цена единицы сырья А и В - соответственно 5 и 8 тыс. долл. Цены на изделия I, II и III - 26,54 и 23 тыс. долл. соответственно.
Изделий типа I необходимо выпустить не менее чем в 1,5 раза больше, чем изделий типа II. Кроме того, требуется выпустить не менее тысячи изделий типа III.
Найти оптимальный план производства.

за х1, х2, х3 обозначаем типы товара
изделий 1 типа нужно выпустить не меньше чем в 1,5 раза больше изделий 2 типа, записывается ограничение
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x1\geq 1.5x2$
которое преобразуется в неравенство
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x1-1.5x2\geq 0$
товара х3 нужно выпустить не меньше 1000
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x3\geq 1000$
дальше ограничения по использованию ресурсов А и В:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?3x1+4x2+x3\preceq 20000$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x1+3x2+2x3\preceq 10000$
дальше считаю суммарную прибыль:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?L=3000x1+10000x2+2000x3\rightarrow max$
ну и все переменные неотрицательные

@Ev_Hyper · 07.07.2014, 19:05

konsul777, так а почему вы не избавитесь от 0, все равно вы добавляете дополнительную переменную в этом ограничении:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{1} - 1.5*{x}_{2}-{x}_{6}=E (E=const, E!=0)$

@konsul777 · 07.07.2014, 23:03 **[ТС]**

Ev_Hyper, не совсем понятна эта запись, как можно избавиться от нуля, поясните пожалуйста,
вместо 0 берется какое-то число?

Новые блоги и статьи Все статьи Все блоги /
Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .	Запрет удаления строк ТЧ документа при определенном условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .
My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .

@konsul777 4 / 4 / 2 Регистрация: 13.11.2012 Сообщений: 253

	симплексное отношение 07.07.2014, 00:14. Показов 10094. Ответов 11 Метки нет (Все метки) для определения разрешающей строки при пересчете симплексной таблицы вычисляется симплексное отношение, то есть для каждого числа ведущего столбца вычисляется отношение соответствующего ему свободному члену к значению числа в ведущей строке, и разрешающей принимается та строка, в которой получившееся число наименьшее. Не совсем ясен один момент, берем из ведущего столбца число, ему соотвествует в столбце свободных членов 0, в этом случае чему будет равно симплексное отношение в этой строке - бесконечноси или нулю? симплесное отношение может быть равно нулю? 0

@Ev_Hyper Заблокирован
	07.07.2014, 08:12
	konsul777, покажите на примере, что вы имеете ввиду. Если я правильно понял вопрос, то берем положительную сигму, а не неотрицательную. Поэтому деления на 0 и нет Если вы о выборе элемента а, то он тоже выбираеться из a>0, тут тоже деления на 0 нет. Если вы о обращении в 0 одной из базисных переменных, то почитайте в литературе о проблеме вырожденности в симплекс-методе. 0

@konsul777 4 / 4 / 2 Регистрация: 13.11.2012 Сообщений: 253
	07.07.2014, 11:41 [ТС]
	Ev_Hyper, к примеру имеется вот такая таблица задача решается на минимум берем допустим строку х1 ведущей, симплексное отношение определяется по формуле $https://www.cyberforum.ru/cgi-bin/latex.cgi?\theta ={b}_{i}/-{r}_{i}$ для строки х8 получаем отношение 0/1=0, либо минимальное отношение берется в строке х6? 0

@Ev_Hyper Заблокирован
	07.07.2014, 12:17
	konsul777, хм...а откуда вы взяли такую формулу? Какая у вас целевая функция и ограничения? Обычно, рассматривают только положительные значения. Предположу, что в вашем случае, наверное, все с точностью наоборот. Значит считать $https://www.cyberforum.ru/cgi-bin/latex.cgi?\theta$ для элементов >=0 не нужно. По-моему, вы правильно выбрали ключевой элемент. Почему вас смутил 0 в b? 0

@S_el 2444 / 1842 / 406 Регистрация: 15.12.2013 Сообщений: 8,243
	07.07.2014, 16:09
	konsul777, а у вас есть эти рекомендации в электронном виде? 0

@Ev_Hyper Заблокирован
	07.07.2014, 17:52
	konsul777, все, наконец-то я понял в чем вопрос. У вас один из элементов правой части B равен 0. Вы уверены, что правильно записали условие задачи? т.к в стандартной постановке на b наложено ограничение: b > 0 Добавлено через 6 минут konsul777, в той книге, о которой я говорил, проблеме вырожденности посвещен пункт 5 второй главы. 0

@Ev_Hyper Заблокирован
	07.07.2014, 19:05
	konsul777, так а почему вы не избавитесь от 0, все равно вы добавляете дополнительную переменную в этом ограничении: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{1} - 1.5*{x}_{2}-{x}_{6}=E (E=const, E!=0)$ 0

@konsul777 4 / 4 / 2 Регистрация: 13.11.2012 Сообщений: 253
	07.07.2014, 23:03 [ТС]
	Ev_Hyper, не совсем понятна эта запись, как можно избавиться от нуля, поясните пожалуйста, вместо 0 берется какое-то число? 0