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

@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 берется какое-то число?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

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

	симплексное отношение 07.07.2014, 00:14. Показов 10033. Ответов 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