Обсуждение:Симплекс-метод

--31.163.223.249 11:59, 19 февраля 2014 (UTC)Нужно запилить хотя бы описание симплекс метода из винрарной книги "Алгоритмы. Построение и Анализ." А то ну вообще статья никакая. Особенно двухфазный симплекс метод совсем неэнциклопедично написан. 79.164.234.234 20:49, 7 января 2011 (UTC)cyberbot

На странице Линейное_программирование указано что автором симплекс метода является не Конторович а Дациг.

хотелось бы увидеть статью о симплекс-методе для решения задач минимизации нелинейной функции 195.19.252.55 21:31, 7 января 2008 (UTC)GANJA_

Я не слишком большой специалист - однако имхо симплекс метод "по определению" относится к задачам линейного программирования - т.е. поиску экстремумов линейных функций. То что вам нужно явно не имеет отношения к симплекс-методу Bibikoff 14:50, 6 мая 2008 (UTC)

Симплекс-метод ошибочен.Свой способ решения подобных задач предложить я не могу,так как здесь требуется коллективный труд,но разработчикам нового способа я бы высказал свои мнения. 78.36.178.161 19:11, 6 мая 2008 (UTC)Вадим Ш. И еще,подскажите,как я могу сообщить об этом математикам Швеции? 78.36.176.249 07:44, 7 мая 2008 (UTC)Вадим Шловиков.

Ошибочен сам симплекс-метод или статья о нем? И зачем вам математики Швеции? :))) Акулов Ярослав 11:03, 7 мая 2008 (U Неполон подход симплекс-метода к решению подобных задач.Хочу уехать жить в Швецию. 78.36.176.249 12:12, 7 мая 2008 (UTC)Вадим Шловиков.

Что значит не полон? Если с его помощью нельзя решить любую нелинейную задачу на оптимизацию, то это не значит, что он ошибочен. Выражайтесь яснее — вы же математик, либо планируйте им стать. Иначе ни швецкие, ни какие-либо другие математики с вами дела иметь не захотят. halyavin 12:02, 8 мая 2008 (UTC)

Шведка откликнись. 78.36.177.102 10:15, 8 мая 2008 (UTC)Шловиков Вадим.Симплекс-метод дает ошибки при решении многих линейных задач на оптимизацию.Подход метода не связывает коэффициенты неизвестных линейной функции,коэффициенты неизвестных в ограничениях и свободные члены вместе.Подход Симплекс-метода к выбору переменных можно сравнить с лотереей. 78.36.177.102 13:01, 8 мая 2008 (UTC)Шловиков Вадим

каждый инструмент предполагает умение им пользоваться. плохо в швеции, скучно, и селёдка там тухлая :)//Berserkerus 14:48, 8 мая 2008 (UTC)

Я противоположного мнения. 78.36.177.102 15:04, 8 мая 2008 (UTC)Шловиков Вадим.

Приношу извинения,симплекс-метод неошибочен.Но согласимся,что для решения задач минимизации и максимизации линейной функции необходимо разработать метод эффективнее,чем симплекс-метод. Вадим Шловиков. 11:54, 23 июня 2009 (UTC)

Ну что ж, всего за год человек разобрался с симплекс-методом и перестал считать его ошибочным. Неплохой результат! :) //drVit 80.237.26.14 16:02, 1 февраля 2011 (UTC)

|. Задачи-исключения из симплекс-метода.

Прежде чем задавать сложные задачи-исключения из симплекс-метода, зададим простые задачи-исключения из симплекс-метода.

Задача №1.

$F\left(x\right)=2\cdot x_{1}-x_{2}\to \max$

${\begin{cases}x_{1}-x_{2}=0\\-x_{1}+x_{2}=0\\x_{j}\geq 0;j=1,2.\end{cases}}$

Какой здесь ответ?Вадим Шловиков 11:21, 25 октября 2012 (UTC)

А ответ задачи №1 такой, при $x_{1}=x_{2}$ получаем $F\left(x\right)=\infty$.

Задача №2.

$F\left(x\right)=2\cdot x_{1}-x_{2}\to \max$

${\begin{cases}2\cdot x_{1}-3\cdot x_{2}+x_{3}=4\\3\cdot x_{1}-4\cdot x_{2}+x_{4}=4\\x_{j}\geq 0;j=1,2,3,4.\end{cases}}$

Какой здесь ответ? Вадим Шловиков 15:45, 25 октября 2012 (UTC)

А ответ задачи №2 такой, при $x_{1}={\frac {4\cdot x_{2}}{3}};x_{3}={\frac {x_{2}+12}{3}};x_{4}=4$ получаем $F\left(x\right)=\infty$.

Подробней о задачах-исключениях из симплекс-метода написано тут http://mathhelpplanet.com/viewtopic.php?f=58&t=18403&st=0&sk=t&sd=a. Вадим Шловиков 05:08, 26 октября 2012 (UTC)

Ага. Задача-исключение №1 для решения квадратного уравнения

$x^{2}=(-x)^{2}$

Какое здесь решение? Правильно, любое

Задача-исключение №2

$x^{2}=-2$

Какое здесь решение? Правильно, нет решений

Вывод, квадратные уравнения неразрешимы. Jumpow (обс.) 18:46, 15 мая 2018 (UTC)

Пример

Было бы неплохо, если бы кто-нибудь добавил пример ручного расчета небольшой задачки с помощью симплекс-метода. Акулов Ярослав 11:48, 3 июня 2008 (UTC)

Пример

Предположим, что фермер использует A кв. км сельскохозяйственных земель, которые будут засеяны либо пшеницей либо ячменем, или обеими культурами в определенном соотношении. У фермера имеется ограниченные количества удобрений F и инсектицидов P, при чем на единицу площади этих веществ требуется различное количество для пшеницы (F₁, P₁) и для ячменя (F₂, P₂). Пусть S₁ цена на пшеницу, и S₂ цена на ячмень. Если мы обозначим площадь посевов пшеницы и ячменя как x₁ и x₂ соответственно, то нахождение оптимальных площадей посевов пшеницы и ячменя могут быть сформулированы как задача линейного программирования ЗЛП:

максимизировать $S_{1}x_{1}+S_{2}x_{2}\,$		(максимизировать прибыль — прибыль это "целевая функция")
при условиях	$x_{1}+x_{2}\leq A$	(ограничение по размеру земель)
	$F_{1}x_{1}+F_{2}x_{2}\leq F$	(ограничение по количеству удобрений)
	$P_{1}x_{1}+P_{2}x_{2}\leq P$	(ограничение по количеству инсектицидов)
	$x_{1}\geq 0,\,x_{2}\geq 0$	(невозможно засеять отрицательную площадь)

В матричной форме:

максимизировать ${\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}$

при условиях ${\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}A\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0$

Так как изложенное является лишь постановкой задачи, я решил не помещать его в тест статьи. Однако,желающие приглашаются дополнить этот пример своим решением. Ссылки на русскоязычные учебники приветствуются. M.Gogeshvili 09:48, 28 августа 2008 (UTC)

---

Задачи линейного программирования в общем виде не решаются. Поставим конкретную задачу

максимизировать $3x_{1}+4x_{2}\,$
при условиях	$x_{1}+x_{2}\leq 200$
$11x_{1}+7x_{2}\leq 1000$
$8x_{1}+9x_{2}\leq 950$
$x_{1}\geq 0,\,x_{2}\geq 0$

Будем решать её модифицированным методом

1. Приводим к каноническому виду

максимизировать $3x_{1}+4x_{2}\,$

при условиях

$x_{1}+x_{2}+d_{1}=200$

$11x_{1}+7x_{2}+d_{2}=1000$

$8x_{1}+9x_{2}+d_{3}=950$

$x_{1}\geq 0,\,x_{2}\geq 0$

Матрица ограничений

$A[M,N]={\begin{bmatrix}1&1\\11&7\\8&9\end{bmatrix}}$

Расширенная матрица ограничений (с дополнительными переменными)

$A[M,N+F]={\begin{bmatrix}1&1&1&0&0\\11&7&0&1&0\\8&9&0&0&1\end{bmatrix}}$

Вектор правых частей $H[M]={\begin{bmatrix}200\\1000\\950\end{bmatrix}}$, он же текущий план $p[{\overline {N}}]$

Строка целевой функции $C[M]={\begin{bmatrix}3&4&0&0&0\end{bmatrix}}$

2. Базис - ${\overline {N}}=\{d_{1},d_{2},d_{3}\}$

Базисная матрица

$B[M,{\overline {N}}]={\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}$

Обратная матрица

$B^{-1}[{\overline {N}},M]={\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}}$

Двойственные переменные $D[M]=C[{\overline {N}}]B^{-1}[{\overline {N}},M]={\begin{bmatrix}0&0&0\end{bmatrix}}$

Невязки: $P[N+F]=C[{\overline {N}}]-D[M]A[M,{\overline {N}}]={\begin{bmatrix}3&4&0&0&0\end{bmatrix}}$

Выбираем первый столбец ($x_{1}$)

Находим разложение по базису

$q[{\overline {N}}]=B^{-1}[{\overline {N}},M]A[M,x_{1}]={\begin{bmatrix}1\\11\\8\end{bmatrix}}$

Ищем $min_{r\in {\overline {N}},q[r]>0}{\tfrac {p[r]}{q[r]}}={\tfrac {1000}{11}}$ и достигается на $r=d_{2}$

Выводим $d_{2}$ из базиса, вводим $x_{1}$

Пересчитываем план $p[{\overline {N}}]=B^{-1}[{\overline {N}},M]P[M]={\begin{bmatrix}{\tfrac {1200}{11}}&{\tfrac {1000}{11}}&{\tfrac {2450}{11}}\end{bmatrix}}$

3. Базис - ${\overline {N}}=\{d_{1},x_{1},d_{3}\}$

Базисная матрица

$B[M,{\overline {N}}]={\begin{bmatrix}1&1&0\\0&11&0\\0&8&1\end{bmatrix}}$

Обратная матрица

$B^{-1}[{\overline {N}},M]={\begin{bmatrix}1&{\tfrac {-1}{11}}&0\\0&{\tfrac {1}{11}}&0\\0&{\tfrac {-8}{11}}&1\end{bmatrix}}$

Двойственные переменные $D[M]=C[{\overline {N}}]B^{-1}[{\overline {N}},M]={\begin{bmatrix}0&3&0\end{bmatrix}}B^{-1}[{\overline {N}},M]={\begin{bmatrix}0&{\tfrac {1}{11}}&0\end{bmatrix}}$

Невязки: $P[N+F]=C[{\overline {N}}]-D[M]A[M,{\overline {N}}]={\begin{bmatrix}0&{\tfrac {37}{11}}&0&{\tfrac {-1}{11}}&0\end{bmatrix}}$

Выбираем второй столбец ($x_{2}$)

Находим разложение по базису

$q[{\overline {N}}]=B^{-1}[{\overline {N}},M]A[M,x_{2}]={\begin{bmatrix}{\tfrac {4}{11}}\\{\tfrac {-7}{11}}\\{\tfrac {43}{11}}\end{bmatrix}}$

Ищем $min_{r\in {\overline {N}},q[r]>0}{\tfrac {p[r]}{q[r]}}={\tfrac {2450}{43}}$ и достигается на $r=d_{3}$

Выводим $d_{3}$ из базиса, вводим $x_{2}$

Пересчитываем план $p[{\overline {N}}]=B^{-1}[{\overline {N}},M]P[M]={\begin{bmatrix}{\tfrac {4000}{43}}&{\tfrac {2350}{43}}&{\tfrac {2450}{43}}\end{bmatrix}}$

4. Базис - ${\overline {N}}=\{d_{1},x_{1},x_{2}\}$

Базисная матрица

$B[M,{\overline {N}}]={\begin{bmatrix}1&1&1\\0&11&7\\0&8&9\end{bmatrix}}$

Обратная матрица

$B^{-1}[{\overline {N}},M]={\begin{bmatrix}1&{\tfrac {-1}{43}}&{\tfrac {-4}{43}}\\0&{\tfrac {9}{43}}&{\tfrac {-7}{43}}\\0&{\tfrac {-8}{43}}&{\tfrac {11}{43}}\end{bmatrix}}$

Двойственные переменные $D[M]=C[{\overline {N}}]B^{-1}[{\overline {N}},M]={\begin{bmatrix}0&3&4\end{bmatrix}}B^{-1}[{\overline {N}},M]={\begin{bmatrix}0&{\tfrac {-5}{43}}&{\tfrac {23}{43}}\end{bmatrix}}$

Невязки: $P[N+F]=C[{\overline {N}}]-D[M]A[M,{\overline {N}}]={\begin{bmatrix}0&0&0&{\tfrac {5}{43}}&{\tfrac {-23}{43}}\end{bmatrix}}$

Видим, что дополнительную переменную $d_{2}$, выведенную на шаге 2, нужно ввводить в базис

Находим разложение столбца по базису

$q[{\overline {N}}]=B^{-1}[{\overline {N}},M]A[M,d_{2}]={\begin{bmatrix}{\tfrac {-1}{43}}\\{\tfrac {9}{43}}\\{\tfrac {-8}{43}}\end{bmatrix}}$

Ищем $min_{r\in {\overline {N}},q[r]>0}{\tfrac {p[r]}{q[r]}}={\tfrac {2450}{43}}$ и достигается на $r=x_{1}$

Выводим $x_{1}$ из базиса, вводим $d_{2}$

Пересчитываем план $p[{\overline {N}}]=B^{-1}[{\overline {N}},M]P[M]={\begin{bmatrix}{\tfrac {850}{9}}&{\tfrac {2350}{9}}&{\tfrac {950}{9}}\end{bmatrix}}$

5. Базис - ${\overline {N}}=\{d_{1},d_{2},x_{2}\}$

Базисная матрица

$B[M,{\overline {N}}]={\begin{bmatrix}1&0&1\\0&1&7\\0&0&9\end{bmatrix}}$

Обратная матрица

$B^{-1}[{\overline {N}},M]={\begin{bmatrix}1&0&{\tfrac {-1}{9}}\\0&1&{\tfrac {-7}{9}}\\0&0&{\tfrac {1}{9}}\end{bmatrix}}$

Двойственные переменные $D[M]=C[{\overline {N}}]B^{-1}[{\overline {N}},M]={\begin{bmatrix}0&0&4\end{bmatrix}}B^{-1}[{\overline {N}},M]={\begin{bmatrix}0&0&{\tfrac {4}{9}}\end{bmatrix}}$

Невязки: $P[N+F]=C[{\overline {N}}]-D[M]A[M,{\overline {N}}]={\begin{bmatrix}{\tfrac {-5}{9}}&0&0&0&{\tfrac {-4}{9}}\end{bmatrix}}$

Нет положительных невязок, следовательно получили оптимальный план

Таким образом, отимальный план $x_{1}=0,x_{2}={\tfrac {950}{9}}$

Легко видеть, что даже такой маленький пример приводит к длительным выкладкам. Если включить его в текст статьи, вполне можете получить реплику "Википедия - не учебник" с последующим удалением примера. Jumpow (обс.) 15:59, 20 апреля 2019 (UTC)

Взято из

http://en.wikipedia.org/wiki/Linear_programming#Example

Вывод сложности алгоритма

Хотелось бы добавить. Кто-нибудь может написать раздел? --SigalX 04:08, 1 ноября 2008 (UTC)

Обращаю внимание читателей одну ошибку в двухфазном симплекс-методе

89.112.55.229 16:51, 5 августа 2010 (UTC)Крамарев Владимир

Цитата:¶ "...оптимальное значение z' равно нулю. Это означает, что все вспомогательные переменные были выведены из базиса, и текущее решение является допустимым. Во втором случае мы имеем допустимый базис, или, иначе говоря, исходное допустимое решение. Можно проводить дальнейшую оптимизацию с учётом исходной целевой функции, при этом уже не обращая внимания на вспомогательные переменные."¶ Это не так. Равенство вспомогательных переменной нулю не означает, что допустимый базис не содержит в себе столбцов с вспомогательными перменными. Неверно, что на столбце допустимого базиса переменная может быть только строго положительной. Видимо, это кочующая из источника в источник ошибка. Стоила мне в свое время больших нервов¶ Нужно производить проверку - находятся ли в допустимом базисе столбцы со вспомогательными переменными и заменять их на подходящие столбцы с дополнительными переменными, преобразуя соответственно и обратную матрицу.

Замечание

Из изложенного выше не прозвучало отчетливо почему если ограничения отличается от <= не всякий 0-вектор будет допустимым решением. В самом деле пусть i - уравнение имеет вид Ai1X1+...AinXn >=Bi но просто можно изменить знаки записав -Ai1X1- ... AinXn<=-Bi и тем самым привести все неравенства к канонической форме. Это было бы нельзя сделать если бы на вектор B было наложено условие неотрицательности Bi>=0 Но в формулировке выше ограничения вектор B отсутствуют. (это очевидная неточность для теоретической статьи в энциклопедии, где все предпосылки должны формулироваться полно) Если бы все было так просто и легко, непонятно зачем изобретали двухфазный метод... Кроме того по этой же причине классический симплекс метод не годится для решения задачи Min F (точнее не годится в случае положительности всех коэфф целевой функции, т.к. тогда метод не сделает ни одной итерации) — Эта реплика добавлена участником Eugrita (о • в) 17:53, 23 апреля 2010 (UTC)

Почему F?

Почему в качестве обозначения единичной матрицы (1 на диагонали, остальное - нули) используется буква F? Ведь общепринятым является E.

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

В статье применяются странные, нестандартные понятия (включая "усиление"). Зачем говорить о "простых" и "непростых" переменных, когда в литературе принято их называть "базисными" и "небазисными", что за отсебятина? Jumpow (обс.) 18:53, 15 мая 2018 (UTC)

Описание

Можете проще расписать, как в учебнике по методам оптимизации? Согласитесь, что этот мусор будут читать только такие же ботаны, как и вы. Вон один чел целый год его изучал, когда можно за один день с нуля, главное чтобы понятно было описано. А тут нихера не понятно! 188.92.0.199 16:04, 16 мая 2013 (UTC)аввыа

Удваиваю. Никакой логики в понимании этого мусора нет. Статья:

• не отвечает на вопрос зачем все это нужно
• не определяет сферы, где это можно применять
• не дает понимания ключевых навыков, которые необходимы для владения методом
• не объясняет никаких различий между способами метода

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

Интересные задачи, которые мог бы решать этот симплекс-метод:

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

(— 176.38.8.23 14:38, 17 ноября 2020 (UTC))