Решить симплекс методом онлайн: Симплекс метод онлайн | Калькулятор симплекс-метода | Решение основной задачи линейного программирования
Симплекс метод онлайн | Калькулятор симплекс-метода | Решение основной задачи линейного программирования
Количество переменных:
Количество ограничений:
Целевая функция:
→ minmax
Базовый симплекс-методМетод искусственного базисаОчистить
Решить
В двойственную
Выполнено действий:
Как пользоваться калькулятором
- Задайте количество переменных и ограничений
- Введите коэффициенты целевой функции
- Введите коэффициенты ограничений и выберите условия (≤, = или ≥)
- Выберите тип решения
- Нажмите кнопку «Решить»
Что умеет калькулятор симплекс-метода
- Решает основную задачу линейного программирования
- Позволяет получить решение с помощью основного симплекс-метода и метода искусственного базиса
- Работает с произвольным количеством переменных и ограничений
Что такое симплекс-метод
Задача линейного программирования — это задача поиска неотрицательных значений параметров, на которых заданная линейная функция достигает своего максимума или минимума при заданных линейных ограничениях.
Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Алгоритм является универсальным методом, которым можно решить любую задачу линейного программирования.
Если вам тоже ничего не понятно из этого определения, то вы на верном пути. Чаще всего статьи про симплекс-метод очень сильно углубляются в дебри теории задачи линейного программирования, из-за чего очень легко потерять суть и так ничего и не понять. Мы постараемся описать алгоритм симплекс-метода так, чтобы показать, что в нём нет ничего страшного и на самом деле он весьма простой. Но сначала нам всё-таки потребуется ввести несколько определений.
Целевая функция — функция, максимум (или минимум) которой нужно найти. Представляет собой сумму произведений коэффициентов на значения переменных: F = c1·x1 + c2·x2 + … + cn·xn
Ограничение — условие вида a1·x1 + a2·x2 + … + an·xn v b, где вместо v ставится один из знаков: ≤, = или ≥
План — произвольный набор значений переменных x1 … xn.
Алгоритм решения основной задачи ЛП симплекс-методом
Пусть в задаче есть m ограничений, а целевая функция заивисит от n основных переменных. Первым делом необходимо привести все ограничения к каноническому виду
Чтобы привести ограничения с неравенствами к каноническому виду, для каждого ограничения вводят переменную, называемую дополнительной с коэффициентом 1. В ответе эти переменные учитываться не будут, однако сильно упростят начальные вычисления. При этом дополнительные переменные являются базисными, а потому могут быть использованы для формирования начального опорного решения.
Пример 1
Привести к каноническому виду ограничения:
2·x1 + 3·x2 + 6·x3 ≤ 240
4·x1 + 6·x2 + 8·x3 ≥ 160
Меняем знаки у ограничений с ≥, путём умножения на -1 и добавляем дополнительные переменные к ограничениям с неравенством:
2·x1 + 3·x2 + 6·x3 + x4 = 240
4·x1 + 2·x2 + 4·x3 = 200
-4·x1 — 6·x2 — 8·x3 + x5 = -160
Формирование начального базиса
После того как задача приведена к каноническому виду, необходимо найти начальный базис для формирования первого опорного решения. Если в процессе приведения были добавлены дополнительные переменные, то они становятся базисными.
Иначе необходимо выделить среди коэффициентов ограничений столбец, который участвует в формировании единичной матрицы в заданной строке (например, если требуется определить вторую базисную переменную, то необходимо искать столбец, в котором второе число равно 1, а остальные равны нулю). Если такой столбец найден, то переменная, соответствующая этому столбцу, становится базисной.
В противном случае можно поискать столбец, в котором все значения кроме числа в заданной строке равны нулю, и, если он будет найден, то разделить все значения строки на число, стоящее на пересечении этих строки и столбца, тем самым образовав столбец, участвующий в формировании единичной матрицы.
Пример 2
9·x1 + 5·x2 + 4·x3 + 3·x4 + 2·x5 → max
x1 — 2·x2 + 2·x3 ≤ 6
x1 + 2·x2 + x3 + x4 = 24
2·x1 + x2 — 4·x3 + 2·x5 = 30
Для ограничения с неравенством добавляем дополнительную переменную x6.
Перепишем ограничения в каноническом виде:
x1 — 2·x2 + 2·x3 + x6 = 6
x1 + 2·x2 + x3 + x4 = 24
2·x1 + x2 — 4·x3 + 2·x5 = 30
Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x
Столбец 4 является частью единичной матрицы. Переменная x4 входит в начальный базис
В пятом столбце все значения кроме третьего равны нулю. Поэтому в качестве третьей базисной переменной берём x5, предварительно разделив третью строку на 2.
Симплекс-таблица
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x6 | 1 | -2 | 2 | 0 | 0 | 1 | 6 |
x4 | 1 | 2 | 1 | 1 | 0 | 0 | 24 |
? | 2 | 1 | -4 | 0 | 2 | 0 | 30 |
После преобразования получаем следующую таблицу:
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x6 | 1 | -2 | 2 | 0 | 0 | 1 | 6 |
x4 | 1 | 2 | 1 | 1 | 0 | 0 | 24 |
x5 | 1 | -2 | 1 | 0 | 15 |
Если такой столбец отсутствует, то для формирования базиса необходимо применить исключение Гаусса для первого ненулевого столбца, который ещё не является базисным. Для этого вся строка делится на элемент в найденном столбце, а из остальных строк вычитается полученная строка, разделённая на значение, стоящее в этом же столбце. После этой операции все значения вне данной строки будут обнулены, и столбец можно будет считать базисным.
Пример 3
4·x1 + 5·x2 + 4·x3 → max
2·x1 + 3·x2 + 6·x3 ≤ 240
4·x1 + 2·x2 + 4·x3 = 160
Для каждого ограничения с неравенством добавляем дополнительные переменные x4 и x5.
Перепишем ограничения в каноническом виде:
2·x1 + 3·x2 + 6·x3 + x4 = 240
4·x1 + 2·x2 + 4·x3 = 160
4·x1 + 6·x2 + 8·x3 + x5 = 200
Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x4
Ограничение 3 содержит неравенство, базисной будет добавленная дополнительная переменная x5
Начальная симплекс-таблица
базис | x1 | x2 | x3 | x4 | x5 | b |
---|---|---|---|---|---|---|
x4 | 2 | 3 | 6 | 1 | 0 | 240 |
? | 4 | 2 | 4 | 0 | 0 | 160 |
x5 | 4 | 6 | 8 | 0 | 1 | 200 |
Для определения второй базисной переменной ищем первый ненулевой столбец, который ещё не является базисным. Первый столбец не нулевой и не является базисным. Выполняем исключение Гаусса: делим строку 2 на 4, а из первой и третьей строк вычитаем вторую, умноженную на соответствующий элемент в первом столбце.
базис | x1 | x2 | x3 | x4 | x5 | b |
---|---|---|---|---|---|---|
x4 | 2 | 3 | 6 | 1 | 0 | 240 |
x1 | 4 | 2 | 4 | 0 | 0 | 160 |
x5 | 4 | 6 | 8 | 0 | 1 | 200 |
После исключения получаем следующую таблицу:
базис | x1 | x2 | x3 | x4 | x5 | b |
---|---|---|---|---|---|---|
x4 | 0 | 2 | 4 | 1 | 0 | 160 |
x1 | 1 | 1 | 0 | 0 | 40 | |
x5 | 0 | 4 | 4 | 0 | 1 | 40 |
После того как базис сформирован, нужно построить начальную симплекс-таблицу. Она строится следующим образом:
- Для удобства в первой строке можно записать коэффициенты Ci целевой функции (для дополнительных переменных эти коэффициенты равны нулю)
- Вторая строка формирует шапку таблицы. В ней первый столбец называется базис, а остальные перечисляют основные переменные x1..xn и дополнительные xn+1..xn+k
- Затем построчно перечисляются базисные переменные и коэффициенты ограничений
Схематично начальная таблица будет выглядеть примерно так:
C | с1 | c2 | … | cn | 0 | 0 | … | 0 | 0 |
---|---|---|---|---|---|---|---|---|---|
базис | x1 | x2 | … | xn | xn+1 | xn+2 | … | xn+k | b |
xe1 | a11 | a12 | … | a1n | a1n+1 | a1n+2 | … | a1n+k | b1 |
xe2 | a21 | a22 | … | a2n | a2n+1 | a2n+2 | … | a2n+k | b2 |
… | … | … | … | … | … | … | … | … | … |
xem | am1 | am2 | … | amn | amn+1 | amn+2 | … | amn+k | bm |
Избавляемся от отрицательных свободных коэффициентов
После приведения к каноническому виду или после алгебраических преобразований при формировании базиса некоторые из свободных коэффициентов (bi) могли стать отрицательными, что не позволяет перейти к дальнейшим вычислениям. Чтобы избавиться от отрицательных значений b необходимо:
- Найти строку, в которой находится максимальное по модулю значение b. Пусть это будет строка i;
- Найти максимальный по модулю элемент в этой строке. Пусть он находится в столбце j;
- Строку i разделить на элемент, стоящий на пересечении i-ой строки и j-го столбца;
- Из каждой оставшейся строки k вычесть строку i, умноженную на элемент строки k и столбца j;
- Переменную, соответствующую найденному столбцу j, сделать базисной (добавить в базис вместо переменной, находящейся в строке i).
Этот шаг необходимо повторять до тех пор, пока все отрицательные b не станут положительными или в строке не останется отрицательных элементов. Если строка с максимальным по модулю bi не содержит отрицательных элементов, то такая задача не имеет решений и на этом алгоритм заканчивает свою работу. В противном случае все bi положительны и алгоритм переходит к следующему этапу — расчёту дельт.
Пример 4
20·x1 + 20·x2 + 10·x3 → min
4·x1 + 3·x2 + 2·x3 ≥ 33
3·x1 + 2·x2 + x3 ≥ 23
x1 + x2 + 2·x3 ≥ 12
Меняем знаки у ограничений с ≥, путём умножения на -1:
-4·x1 — 3·x2 — 2·x3 ≤ -33
— 3·x1 — 2·x2 — x3 ≤ -23
— x1 — x2 — 2·x3 ≤ -12
Для каждого ограничения с неравенством добавляем дополнительные переменные x4..x6.
Перепишем ограничения в каноническом виде:
— 4·x1 — 3·x2 — 2·x3 + x4 = -33
— 3·x1 — 2·x2 — x3 + x5 = -23
— x1 — x2 — 2·x3 + x6 = -12
Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x4
Ограничение 2 содержит неравенство, базисной будет добавленная дополнительная переменная x5
Ограничение 3 содержит неравенство, базисной будет добавленная дополнительная переменная x6
Начальная симплекс-таблица
C | 20 | 20 | 10 | 0 | 0 | 0 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x4 | -4 | -3 | -2 | 1 | 0 | 0 | -33 |
x5 | -3 | -2 | -1 | 0 | 1 | 0 | -23 |
x6 | -1 | -1 | -2 | 0 | 0 | 1 | -12 |
В столбце b присутствуют отрицательные значения.
Максимальное по модулю |b|max = |-33| находится в первой строке.
Максимальный по модулю элемент в первой строке = -4 находится в первом столбце.
В качестве базисной переменной x4 берём x1.
Делим первую строку на -4. Из второй и третьей строк вычитаем первую, умноженную на соответствующий элемент в первом столбце.
Обновлённая таблица:
C | 20 | 20 | 10 | 0 | 0 | 0 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x1 | 1 | — | 0 | 0 | |||
x5 | 0 | — | 1 | 0 | |||
x6 | 0 | — | — | — | 0 | 1 | — |
В столбце b присутствуют отрицательные значения.
Максимальное по модулю |b|max = |- | находится в третьей строке.
Максимальный по модулю элемент в третьей строке = — находится в третьем столбце.
В качестве базисной переменной x6 берём x3.
Делим третью строку на — . Из первой и второй строк вычитаем третью, умноженную на соответствующий элемент в третьем столбце.
Обновлённая таблица:
C | 20 | 20 | 10 | 0 | 0 | 0 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x1 | 1 | 0 | — | 0 | 7 | ||
x5 | 0 | 0 | — | 1 | |||
x3 | 0 | 1 | 0 | — |
Расчёт дельт
Дельты — это параметры, на основании которых проверяется оптимальность текущего решения и улучшается функция. Они рассчитываются для каждой из переменных ограничений и записываются последней строкой таблицы.
Для расчёта дельт используется следующая формула: Δi = ce1·a1i + ce2·a2i + … + cem·ami — ci. Проще говоря, чтобы вычислить дельту по заданной i-ой переменной, нужно перемножить коэффициенты условий в i-ом столбце на коэффициенты целевой функции при соответствующих базисных переменных, сложить эти произведения и вычесть из полученной суммы коэффициент целевой функции столбца i.
Пример 5
Таблица:
C | 3 | 0 | 2 | 0 | 0 | -6 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x2 | 2 | 1 | -3 | 0 | 0 | 6 | 18 |
x4 | -3 | 0 | 2 | 1 | 0 | -2 | 24 |
x5 | 0 | 0 | 1 | — |
Вычисляем дельты: Δi = C2·a1i + C4·a2i + C5·a3i — Ci
Симплекс-таблица с дельтами
C | 3 | 0 | 2 | 0 | 0 | -6 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x2 | 2 | 1 | -3 | 0 | 0 | 6 | 18 |
x4 | -3 | 0 | 2 | 1 | 0 | -2 | 24 |
x5 | 0 | 0 | 1 | — | |||
Δ | -3 | 0 | -2 | 0 | 0 | 6 | 0 |
Проверка плана на оптимальность
После того как дельты рассчитаны, необходимо проверить оптимальность текущего плана. Критерий оптимальности формулируется следующим образом:
При максимизации функции: текущее решение считается оптимальным, если в таблице отсутствуют отрицательные дельты.
При минимизации функции: текущее решение считается оптимальным, если в таблице отсутствуют положительные дельты.
Пример 6
9·x1 + 5·x2 + 4·x3 + 3·x4 + 2·x5 → max
x1 — 2·x2 + 2·x3 ≤ 6
x1 + 2·x2 + x3 + x4 = 24
2·x1 + x2 — 4·x3 + x5 = 30
Симплекс-таблица с дельтами
C | 9 | 5 | 4 | 3 | 2 | 0 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x6 | 1 | -2 | 2 | 0 | 0 | 1 | 6 |
x4 | 1 | 2 | 1 | 1 | 0 | 0 | 24 |
x5 | 2 | 1 | -4 | 0 | 1 | 0 | 30 |
Δ | -2 | 3 | -9 | 0 | 0 | 0 | 132 |
Критерий оптимальности: план оптимален, если в таблице отсутствуют отрицательные дельты.
План не оптимален, так как ищется максимум функции, а Δ1 = -2 отрицательна.
Если текущий план оптимален, то алгоритм завершает свою работу. Значениям переменных соответствуют значения столбца свободных коэффициентов b. Если свободной переменной нет в базисе, то её значение считается нулевым. Значение целевой функции, принимаемой на данном наборе, находится в строке с дельтами в том же столбце. Если какое-либо из значений столбца b отрицательно, то решения задачи не существует.
Переход к более оптимальному решению
Если текущий план оказался не оптимальным, то алгоритм ищет столбец с наименьшей (с наибольшей, если ищется минимум) дельтой. После чего вычисляются симплекс-отношения Q. Для этого значения свободных коэффициентов делятся на ненулевые коэффициенты из найденного столбца. Если результат деления получается отрицательным, то такие отношение игнорируются.
Среди найденных симплекс-отношений ищется строка, в которой находится симплекс-отношение с наименьшим значением. Если таких отношений нет, то алгоритм останавливает свою работу, так как целевая функция не ограничена и решения не существует.
Пример 7
Симплекс-таблица с дельтами
C | 2 | 1 | -2 | 0 | 0 | 0 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x1 | 1 | -5 | 0 | -3 | 0 | -1 | 25 |
x5 | 0 | -16 | 0 | -7 | 1 | -3 | 57 |
x3 | 0 | -6 | 1 | -2 | 0 | -1 | 17 |
Δ | 0 | 1 | 0 | -2 | 0 | 0 | 16 |
Проверяем план на оптимальность: план не оптимален, так как ищется минимум функции, а Δ2 = 1 положительна.
Определяем разрешающий столбец — столбец, в котором находится максимальная дельта: 2, Δ2: 1
Находим симплекс-отношения Q, путём деления коэффициентов b на соответствующие значения второго столбца
C | 2 | 1 | -2 | 0 | 0 | 0 | 0 | |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b | Q |
---|---|---|---|---|---|---|---|---|
x1 | 1 | -5 | 0 | -3 | 0 | -1 | 25 | — |
x5 | 0 | -16 | 0 | -7 | 1 | -3 | 57 | — |
x3 | 0 | -6 | 1 | -2 | 0 | -1 | 17 | — |
Δ | 0 | 1 | 0 | -2 | 0 | 0 | 16 |
Все значения второго столбца отрицательны. Функция не ограничена. Оптимальное решение отсутствует.
В противном случае строка с наименьшим отношением считается разрешающей и, аналогично избавлению от отрицательных свободных коэффициентов, делится на разрешающий элемент, расположенный в найденных столбце и строке, и из остальных строк вычитается найденная строка, разделённая на значения, стоящие в этом же столбце соответствующей строки. Переменная, стоящая в разрешающем столбце заменяет базисную переменную, находящуюся в найденной строке.
После этого вычисляются новые дельты и проверяется новый план. Так продолжается до тех пор пока не будет выполнен критерий оптимальности плана или не будет установлено, что решение не существует.
Пример 8
Симплекс-таблица с дельтами
C | 9 | 5 | 4 | 3 | 2 | 0 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b |
---|---|---|---|---|---|---|---|
x6 | 1 | -2 | 2 | 0 | 0 | 1 | 6 |
x4 | 1 | 2 | 1 | 1 | 0 | 0 | 24 |
x5 | 2 | 1 | -4 | 0 | 1 | 0 | 30 |
Δ | -2 | 3 | -9 | 0 | 0 | 0 | 132 |
Проверяем план на оптимальность: план не оптимален, так как Δ1 = -2 отрицательна.
Итерация 1
Определяем разрешающий столбец — столбец, в котором находится минимальная дельта: 3, Δ3: -9Находим симплекс-отношения Q, путём деления коэффициентов b на соответствующие значения третьего столбца
В найденном столбце ищем строку с наименьшим значением Q: Qmin = 3, строка 1.
На пересечении найденных строки и столбца находится разрешающий элемент: 2
В качестве базисной переменной x6 берём x3.
C | 9 | 5 | 4 | 3 | 2 | 0 | 0 | |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b | Q |
---|---|---|---|---|---|---|---|---|
x3 | 1 | -2 | 2 | 0 | 0 | 1 | 6 | 6 / 2 = 3 |
x4 | 1 | 2 | 1 | 1 | 0 | 0 | 24 | 24 / 1 = 24 |
x5 | 2 | 1 | -4 | 0 | 1 | 0 | 30 | — |
Δ | -2 | 3 | -9 | 0 | 0 | 0 | 132 |
Делим первую строку на 2. Из второй и третьей строк вычитаем первую, умноженную на соответствующий элемент в третьем столбце.
Вычисляем новые дельты: Δi = C3·a1i + C4·a2i + C5·a3i — Ci
C | 9 | 5 | 4 | 3 | 2 | 0 | 0 | |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b | Q |
---|---|---|---|---|---|---|---|---|
x3 | -1 | 1 | 0 | 0 | 3 | 3 | ||
x4 | 3 | 0 | 1 | 0 | — | 21 | 24 | |
x5 | 4 | -3 | 0 | 0 | 1 | 2 | 42 | — |
Δ | -6 | 0 | 0 | 0 | 159 |
Текущий план X: [ 0, 0, 3, 21, 42, 0 ]
Целевая функция F: 9·0 + 5·0 + 4·3 + 3·21 + 2·42 + 0·0 = 159
Проверяем план на оптимальность: план не оптимален, так как Δ2 = -6 отрицательна.
Итерация 2
Определяем разрешающий столбец — столбец, в котором находится минимальная дельта: 2, Δ2: -6Находим симплекс-отношения Q, путём деления коэффициентов b на соответствующие значения второго столбца
В найденном столбце ищем строку с наименьшим значением Q: Qmin = 7, строка 2.
На пересечении найденных строки и столбца находится разрешающий элемент: 3
В качестве базисной переменной x4 берём x2.
C | 9 | 5 | 4 | 3 | 2 | 0 | 0 | |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b | Q |
---|---|---|---|---|---|---|---|---|
x3 | -1 | 1 | 0 | 0 | 3 | — | ||
x2 | 3 | 0 | 1 | 0 | — | 21 | 21 / 3 = 7 | |
x5 | 4 | -3 | 0 | 0 | 1 | 2 | 42 | — |
Δ | -6 | 0 | 0 | 0 | 159 |
Делим вторую строку на 3. Из первой и третьей строк вычитаем вторую, умноженную на соответствующий элемент во втором столбце.
Вычисляем новые дельты: Δi = C3·a1i + C2·a2i + C5·a3i — Ci
C | 9 | 5 | 4 | 3 | 2 | 0 | 0 | |
базис | x1 | x2 | x3 | x4 | x5 | x6 | b | Q |
---|---|---|---|---|---|---|---|---|
x3 | 0 | 1 | 0 | 10 | — | |||
x2 | 1 | 0 | 0 | — | 7 | 7 | ||
x5 | 0 | 0 | 1 | 1 | 63 | — | ||
Δ | 0 | 0 | 2 | 0 | 201 |
Текущий план X: [ 0, 7, 10, 0, 63, 0 ]
Целевая функция F: 9·0 + 5·7 + 4·10 + 3·0 + 2·63 + 0·0 = 201
Проверяем план на оптимальность: отрицательные дельты отсутствуют, следовательно план оптимален.
Ответ: x1 = 0, x2 = 7, x3 = 10, x4 = 0, x5 = 63, F = 201
Метод искусственного базиса
Очень часто при решении задачи линейной оптимизации бывает довольно сложно выполнять алгебраические преобразования над коэффициентами ограничений для поиска начального базиса. Для упрощения вычислений существует альтернативный метод решения, называемый методом искусственного базиса. Его суть заключается в том, что вместо того, чтобы искать базис среди имеющихся основных и дополнительных переменных, ввести так называемые искусственные переменные, которые сформируют начальный базис. Возможно, звучит сложно и непонятно, но сейчас мы всё объясним.
Подготовительный этап
Аналогично базовому симплекс-методу для всех ограничений с неравентством вводятся дополнительные переменные, причём для ограничений с ≥ они берутся с коэффициентом -1, а для ограничений с ≤ с коэффициентом 1. Ограничения с равенством остаются без изменений. Если свободный коэффициент какого-либо из ограничений меньше нуля, то такое ограничение умножается на -1 (знак неравенства при этом меняется на противоположный). После этого приступают к поиску базиса.
Пример 9
3·x1 + 2·x2 + 3·x3 → min
-2·x1 — x2 — x3 ≥ -2
3·x1 + 8·x2 + 2·x3 ≥ 8
2·x1 + x3 = 1
Меняем знаки у ограничений с отрицательными свободными коэффициентами, путём умножения на -1:
2·x1 + x2 + x3 ≤ 2
3·x1 + 8·x2 + 2·x3 ≥ 8
2·x1 + x3 = 1
Для каждого ограничения с неравенством добавляем дополнительные переменные x4 и x5.
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x4
Ограничение 2 содержит неравенство с ≥. Базисная переменная для этого ограничения будет определена позднее.
Ограничение 3 содержит равенство. Базисная переменная для этого ограничения будет определена позднее.
Начальная симплекс-таблица
C | 3 | 2 | 3 | 0 | 0 | 0 |
базис | x1 | x2 | x3 | x4 | x5 | b |
---|---|---|---|---|---|---|
x4 | 2 | 1 | 1 | 1 | 0 | 2 |
?1 | 3 | 8 | 2 | 0 | -1 | 8 |
?2 | 2 | 0 | 1 | 0 | 0 | 1 |
Формирование начального базиса
Для того, чтобы сформировать начальный базис в первую очередь можно поискать столбец, у которого одно значение равно единице, а все значения остальные значения равны нулю, и сделать соответствующую переменную базисной для этой строки. Однако такое случается довольно редко, поэтому проще сразу перейти к следующему пункту. Для всех ограничений, не имеющих базисной переменной, добавляем искусственную переменную с коэффициентом 1. В целевую функцию добавляем эту же переменную с коэффициентов -M, если ищется максимум или с коэффициентом M, если ищется минимум. M всего лишь является очень большим числом.
Пример 10
x1 — x2 → min
2·x1 + x2 = 1
x1 — 3·x2 + x3 = 3
x1 + 11·x2 = 11
Ограничение 1 содержит равенство. Базисная переменная для этого ограничения будет определена позднее.
Столбец 3 является частью единичной матрицы. Переменная x3 входит в начальный базис
Ограничение 3 содержит равенство. Базисная переменная для этого ограничения будет определена позднее.
Начальная симплекс-таблица
C | 1 | -1 | 0 | 0 |
базис | x1 | x2 | x3 | b |
---|---|---|---|---|
?1 | 2 | 1 | 0 | 1 |
x3 | 1 | -3 | 1 | 3 |
?3 | 1 | 11 | 0 | 11 |
Для ограничения 1 добавляем искусственную переменную u1 и делаем её базисной.
Для ограничения 3 добавляем искусственную переменную u2 и делаем её базисной.
В целевую функцию добавляем искусственные пременные с коэффициентом M, где M — очень большое число.
Таблица с искусственными переменными
C | 1 | -1 | 0 | M | M | 0 |
базис | x1 | x2 | x3 | u1 | u2 | b |
---|---|---|---|---|---|---|
u1 | 2 | 1 | 0 | 1 | 0 | 1 |
x3 | 1 | -3 | 1 | 0 | 0 | 3 |
u2 | 1 | 11 | 0 | 0 | 1 | 11 |
Перепишем условие задачи с учётом добавленных искусственных переменных:
F = 1x1 -1x2 + Mu1 + Mu2 → min
2·x1 + x2 + u1 = 1
x1 — 3·x2 + x3 = 3
x1 + 11·x2 + u2 = 11
Расчёт дельт и проверка плана на оптимальность
После того, как начальный базис сформирован необходимо вычислить дельты. Дельты вычисляются полностью аналогично базовому методу: Δi = ce1·a1i + ce2·a2i + … + cem·ami — ci. Единственным отличием будет тот факт, что результат может содержать значения с M. Когда дельты будут получены необходимо проверить текущий опорный план на оптимальность (см. проверку плана на оптимальность в базовом симплекс-методе). Если план оптимален, то алгоритм завершает свою работу, иначе формирует более оптимальное решение и повторяет процесс.
Пример 11
Таблица с искусственными переменными
C | 3 | 2 | 3 | 0 | 0 | 0 | M | M | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | u1 | u2 | b |
---|---|---|---|---|---|---|---|---|---|
x4 | 2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 2 |
u1 | 3 | 0 | 2 | 0 | -1 | 0 | 1 | 0 | 3 |
u2 | 0 | 0 | 1 | 0 | 0 | -1 | 0 | 1 | 1 |
Вычисляем дельты: Δi = C4·a1i + C7·a2i + C8·a3i — Ci
Δ1 = C4·a11 + C7·a21 + C8·a31 — C1 = 0·2 + M·3 + M·0 — 3 = -3 + 3M
Δ2 = C4·a12 + C7·a22 + C8·a32 — C2 = 0·1 + M·0 + M·0 — 2 = -2
Δ3 = C4·a13 + C7·a23 + C8·a33 — C3 = 0·1 + M·2 + M·1 — 3 = -3 + 3M
Δ4 = C4·a14 + C7·a24 + C8·a34 — C4 = 0·1 + M·0 + M·0 — 0 = 0
Δ5 = C4·a15 + C7·a25 + C8·a35 — C5 = 0·0 + M·(-1) + M·0 — 0 = -M
Δ6 = C4·a16 + C7·a26 + C8·a36 — C6 = 0·0 + M·0 + M·(-1) — 0 = -M
Δ7 = C4·a17 + C7·a27 + C8·a37 — C7 = 0·0 + M·1 + M·0 — M = 0
Δ8 = C4·a18 + C7·a28 + C8·a38 — C8 = 0·0 + M·0 + M·1 — M = 0
Δb = C4·b1 + C7·b2 + C8·b3 — C9 = 0·2 + M·3 + M·1 — 0 = 4M
C | 3 | 2 | 3 | 0 | 0 | 0 | M | M | 0 |
базис | x1 | x2 | x3 | x4 | x5 | x6 | u1 | u2 | b |
---|---|---|---|---|---|---|---|---|---|
x4 | 2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 2 |
u1 | 3 | 0 | 2 | 0 | -1 | 0 | 1 | 0 | 3 |
u2 | 0 | 0 | 1 | 0 | 0 | -1 | 0 | 1 | 1 |
Δ | -3 + 3M | -2 | -3 + 3M | 0 | -M | -M | 0 | 0 | 4M |
Текущий план X: [ 0, 0, 0, 2, 0, 0, 3, 1 ]
Целевая функция F: 3·0 + 2·0 + 3·0 + 0·2 + 0·0 + 0·0 + M·3 + M·1 = 4M
Проверяем план на оптимальность: план не оптимален, так как Δ1 = -3 + 3M положительна.
задачи линейного программирования решение онлайн
Вы искали задачи линейного программирования решение онлайн? На нашем сайте вы можете получить ответ на любой математический вопрос здесь. Подробное решение с описанием и пояснениями поможет вам разобраться даже с самой сложной задачей и калькулятор онлайн симплексный метод, не исключение. Мы поможем вам подготовиться к домашним работам, контрольным, олимпиадам, а так же к поступлению в вуз. И какой бы пример, какой бы запрос по математике вы не ввели — у нас уже есть решение. Например, «задачи линейного программирования решение онлайн».
Применение различных математических задач, калькуляторов, уравнений и функций широко распространено в нашей жизни. Они используются во многих расчетах, строительстве сооружений и даже спорте. Математику человек использовал еще в древности и с тех пор их применение только возрастает. Однако сейчас наука не стоит на месте и мы можем наслаждаться плодами ее деятельности, такими, например, как онлайн-калькулятор, который может решить задачи, такие, как задачи линейного программирования решение онлайн,калькулятор онлайн симплексный метод,калькулятор симплекс,калькулятор симплекс метод,калькулятор симплекс метода онлайн,метод искусственного базиса калькулятор онлайн,метод искусственного базиса онлайн калькулятор,метод оптимальных решений онлайн калькулятор,методы оптимальных решений калькулятор онлайн,методы оптимальных решений онлайн калькулятор,онлайн калькулятор метод искусственного базиса,онлайн калькулятор методы оптимальных решений,онлайн калькулятор симплекс метод,онлайн калькулятор симплекс метод с подробным решением,онлайн калькулятор симплекс метода,онлайн калькулятор симплексный метод,онлайн решение задач линейного программирования,онлайн решение задачи линейного программирования,онлайн решение симплекс метод,онлайн решение симплекс методом,решение задач линейного программирования онлайн,решение задач линейного программирования симплекс методом онлайн,решение задач симплекс методом онлайн,решение задач симплекс методом онлайн с решением,решение задачи линейного программирования онлайн,решение задачи линейного программирования симплекс методом онлайн,решение задачи симплекс методом онлайн,решение злп симплекс методом онлайн,решение онлайн симплекс методом,решение симплекс метод онлайн,решение симплекс методом,решение симплекс методом онлайн,решения задачи табличным симплексным методом онлайн,решить задачу линейного программирования онлайн,решить задачу линейного программирования симплекс методом онлайн,решить задачу симплекс методом онлайн,решить онлайн задачу линейного программирования,решить онлайн симплекс методом,решить симплекс методом задачу,решить симплекс методом задачу линейного программирования онлайн,решить симплекс методом онлайн,симплекс калькулятор,симплекс калькулятор онлайн,симплекс метод калькулятор,симплекс метод калькулятор онлайн,симплекс метод онлайн,симплекс метод онлайн калькулятор,симплекс метод онлайн калькулятор с подробным решением,симплекс метод онлайн решение,симплекс метод онлайн с параметром,симплекс метод онлайн с подробным решением,симплекс метод онлайн с подробным решением онлайн,симплекс метод решение онлайн,симплекс метод с параметром онлайн,симплекс онлайн,симплекс онлайн калькулятор,симплекс таблица онлайн,симплексный метод калькулятор онлайн,симплексный метод онлайн,симплексный метод онлайн калькулятор. На этой странице вы найдёте калькулятор, который поможет решить любой вопрос, в том числе и задачи линейного программирования решение онлайн. Просто введите задачу в окошко и нажмите «решить» здесь (например, калькулятор симплекс).
Где можно решить любую задачу по математике, а так же задачи линейного программирования решение онлайн Онлайн?
Решить задачу задачи линейного программирования решение онлайн вы можете на нашем сайте https://pocketteacher.ru. Бесплатный онлайн решатель позволит решить онлайн задачу любой сложности за считанные секунды. Все, что вам необходимо сделать — это просто ввести свои данные в решателе. Так же вы можете посмотреть видео инструкцию и узнать, как правильно ввести вашу задачу на нашем сайте. А если у вас остались вопросы, то вы можете задать их в чате снизу слева на странице калькулятора.
Решение двойственной задачи 📝 симплекс методом онлайн
Изучая аналитические методы и МЛП, вам приходилось иметь дело с различными заданиями и решение двойственной задачи онлайн – это верный способ получить качественно выполненную работу и хорошую оценку. Но как говорится «врага нужно знать в лицо», поэтому стоит разобраться, что такое линейное программирование. Данный термин предназначен для обозначения раздела математики, который ориентирован на поиск экстремума (максимума или минимума) в задачах, что описываются линейными уравнениями. Существует масса методов, которые широко используются специалистами, но студентам часто приходится оперировать знаниями симплекс-метода. Такая тактика нередко вызывает трудности, но когда на кону оценка за курс, приходится быстро искать оптимальные решения.
Наш сайт представляет собой аукцион, где находятся исполнители, готовые приступить к выполнению вашего заказа, а вот цену за работу устанавливаете вы сами. Анализируя рейтинг цен и отзывы заказчиков, студент выбирает подходящий вариант. Заказать решение двойственной задачи симплекс методом онлайн – это значит:
- Гарантия на все виды работ
- Демократичные цены
- Оперативность и высокое качество выполнения решений
- Грамотность оформления и достоверность результатов
- Никаких посредников, студент и исполнитель сотрудничают напрямую
Если вам надоело разбираться в этой теме, решение двойственной задачи линейного программирования онлайн поможет сохранить нервы и время. Помощь студенту доступна 24 часа в сутки 7 дней в неделю. Даже особенно сложная ЗЛП без проблем будет решена симплекс-методом прямо на сайте, с интерпретацией необходимых симплекс- таблиц и комментариями.
Иногда студенты могут прибегать к использованию онлайн калькуляторов, непроверенных таблиц и готовых ответов, которые в широком доступе есть в Интернете. Но зачастую условия заданий могут не совпадать, имеются опечатки и неточности, которые являются грубейшей ошибкой в математике. Основываясь на теории двойственности, симплекс метод применяют для выполнения заданий, в которых свободные члены bi способны выступать при любом значении, а система ограничений задана неравенствами смысла «=» или равенством «=».
Все для студента
Мы как никто другой понимаем, что студенты – это категория населения, которая не отличается большим достатком, поэтому ценовая политика ресурса будет всем по карману. Кроме того, решение будет подробным и понятным, ведь наша задача – помочь в обучении и заполнить пробелы в знаниях. Все шаги по подготовке данных к симплекс- методу будут выполнены грамотно, с учетом всех правил и теорий. Заказывая решение на сайте, заказчик может не сомневаться в его достоверности и смело претендовать на хорошую оценку. Нашими услугами пользуются эрудированные студенты, которые с особой ответственностью подходят к подготовке задания, а свободное время тратят на свое усмотрение. Онлайн помощь студентам – это реализация принципа «Я хочу заказать, а я могу выполнить!»
Решение злп симплекс методом онлайн
ЗЛП (задача линейного программирования) – задача для нахождения наибольшего (наименьшего) значения линейной функции многих переменных при линейных ограничениях типа равенств (неравенств), когда на переменные задачи есть (нет) ограничений на знак. И в большинстве случаев, всегда возникает вопрос: “Где найти решение злп симплекс методом онлайн?”
Сессия? Необходима помощь с решением задач? Узнайте стоимость и срок в один клик. Опытные преподаватели. Срок от 1 дня. Всегда отличный результат за короткие сроки.Для решения задач линейного программирования существует много различных методов. Одним из них является симплекс метод. Данный метод – один из универсальных для решения такого типа задач. На первый взгляд, все это кажется непонятным. Но для помощи студентам существуют программы, где можно получить решение злп симплекс методом онлайн.
Этапы алгоритма симплекс-метода:
- для начала составляется первый опорный план;
- далее план проверяется на оптимальность;
- определяется ведущий столбец и строка;
- строится новый опорный план.
Задачи, которые решаются симплекс методом, для удобства и наглядности записываются в таблицах. Последняя таблица уже с оптимальным решением содержит дополнительную информацию: остатки ресурсов, решение и иные сведения, которые дают возможность провести экономический анализ задачи.
Не нашли что искали?
Преподаватели спешат на помощь
Если Вы все таки выбрали решить задачу симплекс методом онлайн. Для этого необходимо выбрать нужную программу. После чего задать количество ограничений и количество переменных. Ввести в таблицу данные. И вы получите решенную задачу с использованием симплекс метода с подробным решением.
Нет времени и желания разбираться в задачах линейного программирования? В таком случае, Вы всегда можете обратиться в “Студент-Сервис”. Оставить заявку можно с помощью онлайн-формы на сайте, либо по телефону, либо по эл. почте, либо в офисах компании.
Преподаватели спешат на помощь. Заказать решение у профессионалов- очень просто. Учитесь хорошо – присоединяйтесь к нам.
Похожие статьи
- Цена научной статьи
- Сделать чертеж онлайн 2d недорого и срочно
Решение игры симплекс-методом | Контрольные работы по математике и др
Пример. Найти решение матричной игры с платежной матрицей:
Решение. Матричной игре с данной платежной матрицей будет соответствовать пара двойственных задач линейного программирования:
Найти минимум функции F(Х) = x1 + x2 + x3 при ограничениях:
Найти максимум функции T(Y) = y1 + y2 + y3 при ограничениях:
Здесь
Решаем последнюю задачу симплексным методом.
Базисные перемен- Ные | ДО | |||||||
1 | 1 | 2 | 3 | 1 | 0 | 0 | 1 | |
1 | 3 | 1 | 1 | 0 | 1 | 0 | ||
1 | 1 | 3 | 1 | 0 | 0 | 1 | 1 | |
0 | -1 | -1 | -1 | 0 | 0 | 0 | ||
0 | 5/3 | 1 | 0 | |||||
1 | 1/3 | 0 | 0 | 1 | ||||
2/3 | 0 | 8/3 | 2/3 | 0 | -1/3 | 1 | ||
0 | -2/3 | 0 | 0 | |||||
1/4 | 0 | 0 | 9/4 | 1 | -1/8 | -5/8 | ||
1 | 0 | 1/4 | 0 | 1 | ||||
0 | 1 | 1/4 | 0 | 1 | ||||
0 | 0 | -1/2 | 0 | |||||
0 | 0 | 1 | ||||||
1 | 0 | 0 | ||||||
0 | 1 | 0 | ||||||
0 | 0 | 0 | ||||||
Решение этой задачи
.
Тогда цена игры а вероятности применения стратегий игрока II будут:
Из симплекс-таблицы находим решение двойственной задачи:
Следовательно, вероятности применения стратегий игрока I:
,
Таким образом, оптимальные смешанные стратегии игроков:
, , .
< Предыдущая | Следующая > |
---|
Как советские ученые создали «атомную бомбу» в линейном программировании – Наука – Коммерсантъ
текст Александр Горяшко доктор физико-математических наук
иллюстрации Галя Панченко
Понятие «сложность» как фундамент компьютерной науки
Когда школьника учат решать задачи, понятие «сложность» для него исключительно субъективно, таким и остается на всю жизнь. Да и математики на протяжении веков не были озабочены объективной оценкой сложности задач, пока к этому их не подтолкнуло появление компьютеров. На первых порах теория алгоритмов ограничилась бинарной классификацией сложности: класс задач, которые можно решить за конечное время, и класс задач, для которых можно доказать принципиальную невозможность решения в конечное время. До середины прошлого века ученый, предлагающий новый алгоритм, не считал необходимым оценивать время его работы. Важно было лишь, что оно конечно, то есть алгоритм сходится. А неявно предполагалось, что усовершенствование компьютеров делает вопрос об оценке необходимых ресурсов бессмысленным.
Но в СССР с 1960-х годов возникает несколько математических семинаров, участники которых пытаются понять, что такое «сложность» решения задачи в конечное время. Результаты математические оказались чрезвычайно интересными и неожиданными. Результаты же «метафизические» могли вызвать тревогу. Стало очевидно, что теория алгоритмической сложности плохо дружит с так называемым здравым смыслом, а получение новых результатов, как правило, требует отказа от привычных методов и подходов.
Задача тысячелетия
В 1970 году Л.А. Левин — ученик А.Н. Колмогорова и А.А. Маркова и недавний выпускник мехмата МГУ — сделал работу, которая у многих специалистов вызвала разве что недоумение. Трехстраничная заметка «Универсальные задачи перебора» была опубликована в журнале «Проблемы передачи информации» только в 1973 году, на третий год после поступления. А годом ранее (в Союзе об этом тогда никто не подозревал) вышла статья американского математика Р.М. Карпа «Сводимость комбинаторных проблем». Эти пионерские статьи и последовавший за ними шквал работ, развивающих идеи Левина и Карпа, предопределили пути развития всей области computer sciences на следующие десятилетия.
В 2000 году Математический институт Клея сформулировал семь «задач тысячелетия». За решение каждой обещан The Millennium Prize в $ 1 000 000. Первой значилась проблема, поставленная в работах Левина и Карпа и до сих пор не решенная.
Современная теория алгоритмической сложности ограничивается рассмотрением двух ее классов: экспоненциальной и полиномиальной. Эти названия показывают, с какой именно трудоемкостью (по порядку величины числа шагов вычисления, например) возможно решение любой задачи из заданного класса. В качестве аргумента функции, определяющей трудоемкость, служит длина n того входного слова, которое задает эту задачу. Если число шагов вычисления оценивается сверху некоторым полиномом от n, соответствующую задачу называют полиномиально разрешимой. Принято считать, что если задача полиномиально разрешима, то она может быть решена за «приемлемое» время.
В работах Левина и Карпа было доказано существование универсальных задач, из полиномиальной разрешимости которых следует полиномиальная разрешимость любой так называемой переборной задачи. В настоящее время известно более 2000 таких задач, причем техника сводимости позволяет (как правило, без особого труда) каждую новую вычислительную задачу проверять на «универсальность».
Таким образом, нет необходимости отдельно выяснять трудоемкость задачи — достаточно установить ее сводимость к любой из полиномиально разрешимых задач. А после этого остается «самая малость» — хотя бы для одной из тысяч универсальных задач найти алгоритм, который позволит решить ее за полиномиальное время. Если такой алгоритм найдется, станет ясно, что все остальные задачи из этого класса решаются в полиномиальное время тем же самым алгоритмом. А если хотя бы для одной из них будет доказано, что такого алгоритма не существует, это будет означать отсутствие полиномиальной разрешимости для любой универсальной задачи. Так что институт Клея не продешевил, назначая приз за решение вопроса о совпадении классов переборных и полиномиально разрешимых задач. Хотя подавляющая часть специалистов не верит, что задачи из класса универсальных переборных могут быть полиномиально разрешимы (только 9 из 100 опрошенных математиков допустили такую возможность), точного доказательства еще никто не представил.
Сложность решения «простых» задач линейного программирования
Советский математик Л.В. Канторович и американец Тьяллинг Купманс стали лауреатами Нобелевской премии по экономике 1975 года за работы по «оптимальному распределению ресурсов». Результаты их работ применяются при решении практических задач оптимального проектирования всего, что производится в современном обществе, — особенно после того, как в 1947 году американский математик Дж. Данциг предложил алгоритм решения задач линейного программирования, которому он дал имя симплекс-метода. Это до сих пор наиболее известный и используемый вычислительный алгоритм.
Его эффективность подтверждалась решением сотен тысяч задач линейного программирования. Для сонма прикладников сомнения в эффективности симплекс-метода были равноценны сомнениям в законе тяготения. Но у чистых математиков основания для сомнений были. Ведь в процессе решения симплекс-метод перебирает по специальным правилам некоторое число вариантов. Опасность в том, что это число растет экспоненциально с ростом числа переменных. Почему же симплекс-метод, который в принципе может столкнуться с необходимостью перебора астрономического числа вариантов, на практике с этим не сталкивается?
25 лет потребовалось, чтобы гипотезе о необыкновенной эффективности симплекс-метода пришел конец: появились примеры задач линейного программирования, для которых оптимальное решение симплекс-методом невозможно быстрее, чем за экспоненциально растущее (с ростом параметров задачи) число шагов. Прикладники не беспокоились — они продолжали использовать симплекс-метод и получать оптимальные решения за приемлемое время. Но математики не были готовы смириться со странной ситуацией: существуют задачи, на которых симплекс-метод не должен сходиться, но почему-то сходится. Как же устроен класс задач линейного программирования: то ли доля сложных задач в нем мала, то ли этот класс задач полиномиально разрешим, но симплекс-метод не обеспечивает полиномиальных оценок трудоемкости. В последнем случае следует искать другой алгоритм, который любую задачу из класса задач линейного программирования будет решать за время, растущее не быстрее полинома от числа переменных и ограничений.
О разрешимости задач в линейном программировании
Соученик Л.А. Левина А.С. Немировский после защиты кандидатской диссертации оказался в теоретическом отделе одного московского «почтового ящика». Начальник отдела профессор Д.Б. Юдин предложил новичку исследовать «сложность задач математического программирования». Проблемами алгоритмической сложности Немировский дотоле не интересовался, а дискретную математику вообще не жаловал. Потому и обратился к тому, что понимал: подходу к оценке сложности непрерывных задач, предложенному проф. Н.С. Бахваловым для оценок скорости сходимости решений дифференциальных и интегральных уравнений.
Если в компьютерной науке оценки сложности носили дискретный характер (число шагов вычислений, количество элементов в схемах или букв в формулах), то методология Бахвалова предполагала, что численный метод решения может быть связан с накоплением информации о решаемой задаче — путем задания «оракулу» вопросов из заданного множества. Минимально возможное количество вопросов, достаточных, чтобы сформировать решение с заданной точностью, как раз и оценивало «сложность» задачи. Подход предполагает, что «оракул» не всеведущ, то есть не может сразу указать решение задачи (ему можно задавать только локальные вопросы типа: «Куда пойти на следующем шаге?»). За методом, предложенным Немировским, в мире впоследствии закрепилось название «метод эллипсоидов».
После того как эти результаты Немировского были опубликованы, Л.Г. Хачиян, молодой математик, работавший в Вычислительном центре АН СССР, заметил, как их можно «подать» наиболее впечатляющим образом. Он показал, что на основании метода эллипсоидов можно доказать полиномиальную разрешимость задач линейного программирования. Вскоре после опубликования работы Хачияна американская New York Times вышла со статьей, озаглавленной «Русская атомная бомба в линейном программировании». В 1982 году Mathematical Optimization Society and the American Mathematical Society наградили А. Немировского, Л. Хачияна и Д. Юдина премией Фалкерсона (Fulkerson Prize) за статьи, в которых содержались результаты, позволившие получить полиномиальный алгоритм для задач линейного программирования.
В Штатах сразу же после появления информации об оптимальном методе развернулась работа по доведению алгоритмов «эллипсоидального типа» до программной реализации, способной соперничать с лучшими версиями симплекс-метода. Уже в новом тысячелетии были продемонстрированы примеры задач, для которых алгоритмы этого класса работают в сотни раз эффективнее стандартных реализаций симплекс-метода. А в американских учебниках по исследованию операций алгоритмы, основанные на методе эллипсоидов, без обиняков называют «методом Кармаркара» по имени американского математика, который усовершенствовал программную реализацию метода, изложенную в статье Хачияна.
Оптимальность vs робастность
В 1997 году А.С. Немировским сделан решающий шаг, который не удался его предшественникам (в том числе и нобелевскому лауреату Г. Саймону). Он впервые обнаружил, что задачи линейного программирования могут обладать особенностями, крайне неприятным для пользователя. Разница (даже в доли процента) между данными, которыми оперирует оптимальный алгоритм решения, и теми, которые будут иметь место в случае применения полученного решения, может привести к тому, что в большой доле задач полученное оптимальное решение окажется не только не оптимальным, но и вообще недопустимым, то есть будут нарушены заданные ограничения.
Следовательно, доверять оптимальному решению можно лишь, если заранее определить подверженность задачи «болезни неопределенности» — и найти «лекарство». Немировский предложил математически строгий способ, который обеспечивает надежность применения оптимального решения, назвав его «робастная оптимизация» (англ. robust— надежный, устойчивый, грубый). Этот способ менял и традиционную постановку задач линейного программирования, и алгоритм ее решения. Задача решалась при дополнительном условии, что все коэффициенты могут принимать любые значения из некоторого множества — множества неопределенности. Какими бы ни оказались коэффициенты, если они принадлежат множеству неопределенности, решение обязательно будет допустимым (точнее, робастно допустимым). Робастная оптимизация находит оптимальное решение только среди всех робастно допустимых решений.
Введение множества неопределенностей в стандартную задачу линейного программирования превращает ее в некоторое множество задач. А значит, стандартные методы решения задач линейного программирования непригодны. Но такая задача может быть решена как задача «выпуклой оптимизации», а для этого класса Немировским ранее уже были получены оптимальные алгоритмы решения (метод эллипсоидов). Это открывало дорогу для широкого применения методов робастной оптимизации в прикладных задачах. Сразу после опубликования первых результатов идеи робастности были подхвачены всеми, кто на практике или в теории занимался теорией оптимизации. Было ощущение, что именно такого подхода специалисты ожидали долгие годы.
Любой прикладник мечтает, чтобы полученное им решение обеспечивало максимум возможного в реальном мире. До сих пор математика предлагала ему этот реальный мир задать некоторым вероятностным распределением и максимизировать ожидаемый результат. Хотя все понимали, что задание такого распределения в большинстве реальных ситуаций не более чем фикция. Робастная оптимизация гарантирует максимум возможного при самом неблагоприятном стечении обстоятельств. Если вдуматься, это единственное, на что можно всерьез рассчитывать в реальном мире, не будучи патологическим оптимистом. И хотя за все приходится платить, в данном случае природа оказалась «не злонамеренна» — плата за гарантированно допустимое решение вполне приемлема как по сложности алгоритма (он полиномиальный), так и по потере в качестве решения, которое во многих случаях лишь на единицы процентов хуже номинальных оптимальных решений.
Робастная оптимизация — наиболее последовательная из существующих сегодня методология преодоления неопределенности будущего. Признавая невозможность победить неопределенность, мы согласны платить, но платим справедливую цену.
Одним из первых больших проектов, в где была испробована робастная оптимизация, стал проект ЕС по оптимальному распределению водных ресурсов в крупных городах. Нужно было выбрать такой режим насосных станций, чтобы он обеспечил минимальную стоимость энергии и учел некоторые гидравлических ограничений (например, давление). Почти все данные в реальных гидравлических системах (истинные диаметры труб, электрические и гидравлические характеристики насосов, поведение потребителей) — это трудно измеряемые и предсказываемые величины.
Немировский считал, что решение можно найти с помощью точных методов робастной оптимизации. Дело в том, что многие практические задачи оптимизации обладают достаточно большим множеством «почти оптимальных» решений. Игнорируя неопределенность и решая задачу с номинальными данными, такие методы, как симплекс, получают в качестве решения граничную точку допустимого множества, которая часто становится недопустимой при возмущении данных. Робастные методы выбирают в допустимом множестве не граничное, а внутреннее решение, и, если множество «почти оптимальных» решений номинальной задачи достаточно массивно, близкое к оптимальному внутреннее решение всегда будет робастно допустимым [рис. ].
Робастное решение — всегда допустимое — Задача линейного программирования может быть представлена в виде многогранника ограничений. Область внутри многогранника — это множество допустимых решений, а вне его — область недопустимых решений, так как нарушаются условия задачи. Известно, что оптимальное решение всегда находится в одной из вершин многогранника, и симплекс-метод обходит вершины в поиске оптимального решения. Но малейшее отклонение от условий может допустимое решение превратить в недопустимое. В отличие от симплекса, робастное решение ищется как внутреннее и поэтому всегда остается допустимым, хотя может быть несколько хуже истинно оптимального решения.
Фото: Галя Панченко
Численное моделирование показало, что по затрачиваемой энергии метод вполне сопоставим с эвристическими подходами, но, в отличие от них, точно указывает, в каком интервале неопределенности исходных данных он робастно допустим. Задача оптимального распределения водных ресурсов — типичная задача управления любыми ресурсами: и распределение энергоресурсов в электрических сетях, и выбор оптимальных биржевых портфелей.
Область практического применения робастной оптимизации давно вышла за пределы линейного программирования и включает в себя, например, оптимизацию инженерных конструкций и нанофотонный инжиниринг. В 2003 году Institute for Operations Research and the Management Sciences за работы по робастной оптимизации наградил А.С. Немировского премией Дж. Неймана (John von Neumann Theory Prize).
Как можно ошибиться на 15%, сделав неверное допущение в 1%
Одной из причин существенного влияния малых воздействий на результат являются «уравнения баланса», наиболее общий тип уравнений, как в экономике, так и во многих физических процессах.
Вот простой пример. Пусть работа автозавода описана линейной моделью, в которой показателем качества является годовая прибыль. Предположим, что в соответствующей модели оптимизации (в задаче линейного программирования) необходимо максимизировать прибыль. Среди различных линейных неравенств обязательно возникнет уравнение баланса следующего вида:
(количество проданных за год автомобилей) х (средняя цена одного проданного автомобиля) — (количество произведенных за год автомобилей) х (себестоимость производства одного автомобиля) Предположим, за год было произведено 200 000 автомобилей и себестоимость производства каждого составляет 10 000 условных единиц. Анализ рынка показал, что можно будет продать не менее 180 000 автомобилей по цене 14 000. Таким образом, предполагаемая прибыль должна быть не меньше 180 000 x 14 000-200 000 x 10 000 = 5,2 x 108 условных единиц. Теперь представим, что в связи с неточностью экономических прогнозов реально было продано не 180 000 автомобилей, а 178 000 (разница чуть больше 1%), а себестоимость каждого из реально произведенных составила 10 200 условных единиц (разница 2%). Реальная прибыль составит 178 000 x 14 000-200 000 x 10200 = 4,5×108 условных единиц. Неточность в 1-2 процента в расчетных данных привела к ошибке в значении предполагаемой прибыли в 15%. А ведь реальные расхождения данных, как правило, превышают один процент.
Люди
Леонид Анатольевич Левин — Род. в 1948 г., российский математик. В 1978 году эмигрировал в США, профессор Бостонского университета. Теория вычислительной сложности.
Ричард М. Карп — Род. в 1935 г., американский математик. Теория вычислительной сложности, биоинформатика.
Аркадий Семенович Немировский — Род. в 1947 г., российский математик, доктор физико-математических наук, работает в ЦЭМИ РАН. Автор метода эллипсоидов и робастной оптимизации.
Леонид Витальевич Канторович — 1912-1986, российский математик и экономист. Академик, Нобелевская премия по экономике 1975 года. Линейное программирование, теория оптимального распределения ресурсов.
Джордж Бернард Данциг — 1914-2005, американский математик, автор симплекс-метода. Линейное программирование.
Тьяллинг Купманс — 1910-1985, американский математик и экономист голландского происхождения. Нобелевская премия по экономике 1975 года. Теория оптимального распределения ресурсов.
Леонид Генрихович Хачиян — 1952-2005, российский математик, доктор физико-математических наук. В 1989 году эмигрировал в США. Автор полиномиального алгоритма для задач линейного программирования.
Математическое программирование. Графический и симплекс метод. Примеры решения задач
Графический и симплекс метод
Видеоурок: «Решение ЗЛП графическим методом»
Видеоурок: «Решение ЗЛП симплексным методом»
Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 1 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 3 часа.
Для производства единицы изделия В оборудование первого типа используется в течении 2 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 1 час.
На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часа, оборудование второго типа – 60 часов, оборудование третьего типа – 50 часов.
Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы.
Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.
1) Составить математическую модель задачи
2) Решить графическим методом
3)Решить симплекс-методом путем преобразования симплекс-таблиц
Решение
Перед нами – классическая задача линейного программирования. Под планом производства понимается ответ на простой вопрос: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.
Прибыль рассчитывается по формуле: .
Запишем математическую модель задачи:
Чтобы проиллюстрировать применение симплекс-метода решения этой задачи, решим ее графически.
Для этого построим на плоскости области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией.
Три записанных выше неравенства ограничивают на плоскости многоугольник (построен красным цветом), ограниченный слева и снизу координатными осями (т.к. искомое количество изделий положительно).
График целевой функции (построен синим цветом) передвигается в направлении, обозначенном стрелкой (по-научному – в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (15 ; 5). В этой точке целевая функция будет достигать максимума.
А теперь решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные .
Симплекс-таблица составляется так:
В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – A3, A4, A5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.
В следующий столбец записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов Аi при i –й переменной.
Под столбцом свободных членов записывается начальная оценка
Остальные оценки записываются под столбцами соответствующих векторов .
Следует отметить, что оценки для базисных векторов всегда равны нулю.
Преобразование симплекс-таблицы ведется следующим образом:
Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.
Шаг 2: Для отрицательных оценок вычисляются величины:
Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае минимально, поэтому в качестве так называемого разрешающего элемента выбирается третий элемент первого столбца – 3 (выделен в таблице).
Шаг 3: Третья строка таблицы делится на 3 и вычитается из первой и второй строк. В сущности, применяется метод исключения неизвестных, известный как метод Жордана – Гаусса.
Таким образом, новыми базисными переменными становятся A3, A4, A1.
Возвращаемся к шагу 1 и повторяем весь процесс.
Под столбцом свободных членов записывается начальная оценка
Остальные оценки записываются под столбцами соответствующих векторов .
Следует отметить, что оценки для базисных векторов всегда равны нулю.
Опять проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А2.
Вычисляем:
Разрешающим элементом будет второй элемент второго столбца – 2/3.
Новыми базисными переменными становятся A3, A2, A1
Делим вторую строку на 2 и вычитаем из третьей.
Умножаем вторую строку на 5/2 и вычитаем из первой.
На этот раз отрицательных оценок нет, т.е. критерий оптимальности выполнен.
Таким образом, получается искомое значение целевой функции F(15; 5; 7; 0; 0) = 70, т.е. возвращаясь к системе неравенств, получаем:
Ответы, полученные различными методами, совпадают.
Калькулятор симплексного метода— двухфазный онлайн 🥇
Найдите оптимальное решение в упражнениях по линейному программированию с помощью нашего онлайн-калькулятора Simplex Method Online Calculator , который позволит вам разрабатывать задачи максимизации и минимизации с помощью обычного метода и, при необходимости, применения двухфазного метода. Наш инструмент имеет удобный и простой в использовании дизайн. Он также показывает нам все промежуточные шаги, необходимые для достижения окончательного решения, что облегчит ваше обучение.
Калькулятор симплексного метода — Бесплатная версия
Хотите видеть детали расчета каждой итерации?
Присоединяйтесь к нашей членской группе и получите полный доступ к Simplex Method Calculator — Two Phase с объяснениями для каждого выполненного расчета.
Как пользоваться онлайн-калькулятором симплекс-методом
Для использования нашего инструмента необходимо выполнить следующие шаги:
- Введите количество переменных и ограничений задачи.
- Выберите тип проблемы: увеличить или свернуть .
- Введите коэффициенты целевой функции и ограничений. Вы можете вводить отрицательные числа, дроби и десятичные дроби (с точкой).
- Щелкните «Решить».
- Онлайн-программное обеспечение адаптирует введенные значения к стандартной форме симплексного алгоритма и создаст первую таблицу .
- В зависимости от знака ограничений используется обычный симплексный алгоритм или двухфазный метод .
- Мы можем шаг за шагом увидеть итераций и таблицы калькулятора симплекс-метода.
- В последней части покажу результаты задачи.
Мы рассмотрели для нашего приложения решение задач с максимум 20 переменными и 50 ограничениями; это связано с тем, что упражнения с большим количеством переменных затрудняют выполнение шагов с использованием симплексного метода. Для проблем с большим количеством переменных мы рекомендуем использовать другие более продвинутые инструменты.
Окончательное отражение
Используя наш калькулятор, мы уверены, что вы лучше подготовитесь к изучению симплекс-метода. Не забывайте, что у нас есть другие калькуляторы линейного программирования.
Вы должны помнить, что целью этого инструмента является изучение симплекс-метода и применение двухфазного метода , поэтому вы можете использовать его только под вашей ответственностью. Также мы не несем ответственности за какие-либо ошибки или неточности в результатах.
Если у вас есть вопросы по этому поводу или вы обнаружите ошибку в нашем приложении, мы будем признательны, если вы напишите нам на нашей странице контактов.
Онлайн-калькулятор: симплекс-метод
Для результатов расчетов предыдущей итерации мы убираем из базиса переменную x 8 и подставляем вместо нее x 2 . Все остальные ячейки остаются без изменений.
Каждая ячейка этого столбца равна коэффициенту, который соответствует базовой переменной в соответствующей строке.
Переносим строку с разрешающим элементом из предыдущей таблицы в текущую таблицу, поэлементно разделяя ее значения на разрешающий элемент:
Вычисляются оставшиеся пустые ячейки, кроме строки оценок и столбца Q используя метод прямоугольника, относительно разрешающего элемента:
P 1 = (P 1 * x 4,2 ) — (x 1,2 * P 4 ) / x 4, 2 = ((600 * 2) — (1 * 150)) / 2 = 525;
P 2 = (P 2 * x 4,2 ) — (x 2,2 * P 4 ) / x 4,2 = ((225 * 2) — ( 0 * 150)) / 2 = 225;
P 3 = (P 3 * x 4,2 ) — (x 3,2 * P 4 ) / x 4,2 = ((1000 * 2) — ( 4 * 150)) / 2 = 700;
P 5 = (P 5 * x 4,2 ) — (x 5,2 * P 4 ) / x 4,2 = ((0 * 2) — ( 0 * 150)) / 2 = 0;
x 1,1 = ((x 1,1 * x 4,2 ) — (x 1,2 * x 4,1 )) / x 4,2 = ((2 * 2) — (1 * 0)) / 2 = 2;
x 1,2 = ((x 1,2 * x 4,2 ) — (x 1,2 * x 4,2 )) / x 4,2 = ((1 * 2) — (1 * 2)) / 2 = 0;
x 1,4 = ((x 1,4 * x 4,2 ) — (x 1,2 * x 4,4 )) / x 4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;
x 1,5 = ((x 1,5 * x 4,2 ) — (x 1,2 * x 4,5 )) / x 4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;
x 1,6 = ((x 1,6 * x 4,2 ) — (x 1,2 * x 4,6 )) / x 4,2 = ((0 * 2) — (1 * -1)) / 2 = 0.5;
x 1,7 = ((x 1,7 * x 4,2 ) — (x 1,2 * x 4,7 )) / x 4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;
x 1,8 = ((x 1,8 * x 4,2 ) — (x 1,2 * x 4,8 )) / x 4,2 = ((0 * 2) — (1 * 1)) / 2 = -0,5;
x 1,9 = ((x 1,9 * x 4,2 ) — (x 1,2 * x 4,9 )) / x 4,2 = ((0 * 2) — (1 * 0)) / 2 = 0;
x 2,1 = ((x 2,1 * x 4,2 ) — (x 2,2 * x 4,1 )) / x 4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;
x 2,2 = ((x 2,2 * x 4,2 ) — (x 2,2 * x 4,2 )) / x 4,2 = ((0 * 2) — (0 * 2)) / 2 = 0;
x 2,4 = ((x 2,4 * x 4,2 ) — (x 2,2 * x 4,4 )) / x 4,2 = ((1 * 2) — (0 * 0)) / 2 = 1;
x 2,5 = ((x 2,5 * x 4,2 ) — (x 2,2 * x 4,5 )) / x 4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;
x 2,6 = ((x 2,6 * x 4,2 ) — (x 2,2 * x 4,6 )) / x 4,2 = ((0 * 2) — (0 * -1)) / 2 = 0;
x 2,7 = ((x 2,7 * x 4,2 ) — (x 2,2 * x 4,7 )) / x 4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;
x 2,8 = ((x 2,8 * x 4,2 ) — (x 2,2 * x 4,8 )) / x 4,2 = ((0 * 2) — (0 * 1)) / 2 = 0;
x 2,9 = ((x 2,9 * x 4,2 ) — (x 2,2 * x 4,9 )) / x 4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;
x 3,1 = ((x 3,1 * x 4,2 ) — (x 3,2 * x 4,1 )) / x 4,2 = ((5 * 2) — (4 * 0)) / 2 = 5;
x 3,2 = ((x 3,2 * x 4,2 ) — (x 3,2 * x 4,2 )) / x 4,2 = ((4 * 2) — (4 * 2)) / 2 = 0;
x 3,4 = ((x 3,4 * x 4,2 ) — (x 3,2 * x 4,4 )) / x 4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;
x 3,5 = ((x 3,5 * x 4,2 ) — (x 3,2 * x 4,5 )) / x 4,2 = ((1 * 2) — (4 * 0)) / 2 = 1;
x 3,6 = ((x 3,6 * x 4,2 ) — (x 3,2 * x 4,6 )) / x 4,2 = ((0 * 2) — (4 * -1)) / 2 = 2;
x 3,7 = ((x 3,7 * x 4,2 ) — (x 3,2 * x 4,7 )) / x 4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;
x 3,8 = ((x 3,8 * x 4,2 ) — (x 3,2 * x 4,8 )) / x 4,2 = ((0 * 2) — (4 * 1)) / 2 = -2;
x 3,9 = ((x 3,9 * x 4,2 ) — (x 3,2 * x 4,9 )) / x 4,2 = ((0 * 2) — (4 * 0)) / 2 = 0;
x 5,1 = ((x 5,1 * x 4,2 ) — (x 5,2 * x 4,1 )) / x 4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;
x 5,2 = ((x 5,2 * x 4,2 ) — (x 5,2 * x 4,2 )) / x 4,2 = ((0 * 2) — (0 * 2)) / 2 = 0;
x 5,4 = ((x 5,4 * x 4,2 ) — (x 5,2 * x 4,4 )) / x 4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;
x 5,5 = ((x 5,5 * x 4,2 ) — (x 5,2 * x 4,5 )) / x 4,2 = ((0 * 2) — (0 * 0)) / 2 = 0;
x 5,6 = ((x 5,6 * x 4,2 ) — (x 5,2 * x 4,6 )) / x 4,2 = ((0 * 2) — (0 * -1)) / 2 = 0;
x 5,7 = ((x 5,7 * x 4,2 ) — (x 5,2 * x 4,7 )) / x 4,2 = ((-1 * 2) — (0 * 0)) / 2 = -1;
x 5,8 = ((x 5,8 * x 4,2 ) — (x 5,2 * x 4,8 )) / x 4,2 = ((0 * 2) — (0 * 1)) / 2 = 0;
x 5,9 = ((x 5,9 * x 4,2 ) — (x 5,2 * x 4,9 )) / x 4,2 = ((1 * 2) — (0 * 0)) / 2 = 1;
Мы вычисляем значение целевой функции, поэлементно умножая столбец Cb на столбец P, складывая результаты продуктов.
Макс P = (Cb 1 * P 1 ) + (Cb 11 * P 2 + (Cb 21 * P 3 + (Cb 31 * P 4) + (Cb 41 * P 5 = (0 * 525) + (0 * 225) + (0 * 700) + (4 * 75) + (-M * 0) = 300;
Вычисляем оценки для каждой контролируемой переменной путем поэлементного умножения значения из столбца переменных на значение из столбца Cb, суммирования результатов продуктов и вычитания коэффициента целевой функции из их суммы с этой переменной .
Макс. x 1 = ((Cb 1 * x 1,1 ) + (Cb 2 * x 2,1 ) + (Cb 3 * x 3,1 ) + (Cb 4 * x 4,1 ) + (Cb 5 * x 5,1 )) — k x 1 = ((0 * 2) + (0 * 0) + (0 * 5) + (4 * 0) + (-M * 0)) — 3 = -3;
Макс. x 2 = ((Cb 1 * x 1,2 ) + (Cb 2 * x 2,2 ) + (Cb 3 * x 3,2 ) + (Cb 4 * x 4,2 ) + (Cb 5 * x 5,2 )) — k x 2 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 1) + (-M * 0)) — 4 = 0;
Макс. x 3 = ((Cb 1 * x 1,3 ) + (Cb 2 * x 2,3 ) + (Cb 3 * x 3,3 ) + (Cb 4 * x 4,3 ) + (Cb 5 * x 5,3 )) — k x 3 = ((0 * 1) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 0)) — 0 = 0;
Макс. x 4 = ((Cb 1 * x 1,4 ) + (Cb 2 * x 2,4 ) + (Cb 3 * x 3,4 ) + (Cb 4 * x 4,4 ) + (Cb 5 * x 5,4 )) — k x 4 = ((0 * 0) + (0 * 1) + (0 * 0) + (4 * 0) + (-M * 0)) — 0 = 0;
Макс. x 5 = ((Cb 1 * x 1,5 ) + (Cb 2 * x 2,5 ) + (Cb 3 * x 3,5 ) + (Cb 4 * x 4,5 ) + (Cb 5 * x 5,5 )) — k x 5 = ((0 * 0) + (0 * 0) + (0 * 1) + (4 * 0) + (-M * 0)) — 0 = 0;
Макс. x 6 = ((Cb 1 * x 1,6 ) + (Cb 2 * x 2,6 ) + (Cb 3 * x 3,6 ) + (Cb 4 * x 4,6 ) + (Cb 5 * x 5,6 )) — k x 6 = ((0 * 0.5) + (0 * 0) + (0 * 2) + (4 * -0,5) + (-M * 0)) — 0 = -2;
Макс. x 7 = ((Cb 1 * x 1,7 ) + (Cb 2 * x 2,7 ) + (Cb 3 * x 3,7 ) + (Cb 4 * x 4,7 ) + (Cb 5 * x 5,7 )) — k x 7 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * -1)) — 0 = M;
Макс. x 8 = ((Cb 1 * x 1,8 ) + (Cb 2 * x 2,8 ) + (Cb 3 * x 3,8 ) + (Cb 4 * x 4,8 ) + (Cb 5 * x 5,8 )) — k x 8 = ((0 * -0.5) + (0 * 0) + (0 * -2) + (4 * 0,5) + (-M * 0)) — -M = M + 2;
Макс. x 9 = ((Cb 1 * x 1,9 ) + (Cb 2 * x 2,9 ) + (Cb 3 * x 3,9 ) + (Cb 4 * x 4,9 ) + (Cb 5 * x 5,9 )) — k x 9 = ((0 * 0) + (0 * 0) + (0 * 0) + (4 * 0) + (-M * 1)) — -M = 0;
Поскольку среди оценок контролируемых переменных есть отрицательные значения, текущая таблица еще не имеет оптимального решения.Поэтому в базис вводим переменную с наименьшей отрицательной оценкой.
Количество переменных в базисе всегда постоянно, поэтому необходимо выбрать, какую переменную извлекать из базиса, для которого мы вычисляем Q.
Элементы столбца Q вычисляются путем деления значений из столбец P на значение из столбца, соответствующего переменной, которая введена в базис:
Выведем из базиса переменную с наименьшим положительным значением Q.
На пересечении линии, соответствующей переменной, полученной из базиса, и столбца, который соответствует переменной, введенной в базис, является разрешающий элемент.
Калькулятор симплексного метода -: Простое решение задач линейного программирования
Оцените лучший и удивительный калькулятор линейного программирования с нами. Этот калькулятор — замечательный инструмент, который может помочь вам в легко решать уравнения линейного программирования.С мотивом чтобы помочь вам сделать ваши расчеты простыми и интересными, мы разработали этот инструмент для вас. Все, что вам нужно сделать, это ввести ваша функция, и он легко покажет вам результат в секунд. Для решения задач линейного программирования симплекс был использован метод.
Чтобы помочь вам разобраться в калькуляторе симплекс-метода
с шагами, мы взяли задачу линейного программирования, которая
минимизация стоимости в соответствии с ограничениями.
Стоимость: C = 5×1
+ 3×2
Ограничения:
Шаг 1
Прежде всего, будет составлена начальная таблица. Прежде всего, вам нужно решить, какова ваша цель — минимизировать или максимизировать цена. Кроме того, вам необходимо решить, сколько переменных там в ограничениях и типе константы. На на основе этой информации будет создана эта таблица из правильный размер.Вам необходимо заполнить его, введя имена переменные и коэффициенты, фигурирующие в константах а также целевая функция.
Шаг 2
Применение симплексного метода Прежде всего, необходимо выбрать столбец и оставьте строку. Та же процедура будет выполняться до тех пор, пока решение помогло. В строке состояния вы узнаете по поводу продолжения шагов. Как только процесс будет завершен, вы получите окончательное решение вашей проблемы.
Симплексный алгоритм
Это один из популярных методов, которые используются для численное решение задач линейного программирования. Лучшая часть об этом калькуляторе легко решить проблемы точно небольшими шагами. Если вы хотите оптимизировать свой практики, то вы должны использовать симплекс-метод линейного программирования калькулятор.
Линейное программирование
Симплексный метод — один из популярных методов решения, используются при решении задач линейного программирования.В в этом методе задействованы две переменные и ограничения. В этом, основные переменные — это решения, указанные для уравнения связи с ненулевыми переменными. Чтобы получить оптимальное значение целевой функции используется этот систематический метод.
Калькулятор симплексного алгоритма
Онлайн-калькулятор симплекс-метода или программа для решения симплексной удивительная роль в решении задач линейного программирования с легкостью.Самое приятное в этом калькуляторе то, что он также может генерировать примеры, чтобы вы могли понять метод.
Калькулятор двухфазного симплексного метода
Приведенный здесь калькулятор может легко решить проблемы, связанные с
симплекс-метод, двухфазный метод и графический метод как
хорошо. В этом калькуляторе вы можете ввести неограниченное количество
переменные или константы.
Лучшее в этой максимизации
калькулятор заключается в том, что вам не нужно говорить на каком-либо языке
проблема конкретно.Пользовательский интерфейс этого инструмента так
легко, что любой пользователь без каких-либо технических знаний может использовать
Это.
Очков, которые следует помнить при использовании калькулятора:
- Не используйте запятые в больших числах при использовании симплексного метода. калькулятор таблиц.
- В правой части каждой константы не вводите e отрицательное число.
- В десятичном режиме все результаты будут отображаться в десятичные дроби.
- Режим дроби помогает преобразовать все десятичные дроби в фракции.
- Внутренний режим помогает исключить десятичные дроби и дроби из таблиц.
Калькулятор двойного симплексного метода
Калькулятор максимизации двойного симплексного метода играет важную роль.
роль в преобразовании исходной таблицы в финальную. В
Финальная таблица всегда содержит как первичное, так и дуальное
проблемы связанные решения.Каждый этап алгоритма воспроизводится
удивительно в создании промежуточной таблицы, поскольку алгоритм
карабкается к окончательному результату.
Наконец, это все важные детали, касающиеся
Симплексный калькулятор. Вы можете легко использовать этот калькулятор и сделать
ваши простые задачи с уравнениями линейного программирования легко и просто, как
хорошо.
Simplex Method Calculator Step by Step.
Пример 5. Решение задачи линейного программирования симплекс-методом.
Решение не единственное
Это решение было сделано с помощью калькулятора, представленного на сайте.
Задача:
Найти максимальное значение функции
с учетом ограничений:
x 1 | + | 2 | x 271 | x 1 ≥ 0 x 2 ≥ 0 |
x 1 | + | 2 | x 2 | ≤ | 6 | |||
2 909 2 | ≤ | 8 | | |||||
x 2 | ≤ | 2 |
909 | 909 2 | + | S 1 | = | 6 | ||||||||||
2 | x 1 | 968 2 | + | S 2 | = | 8 | |||||||||
9065 9065 9065 | 909 909 909 909 909 S 3 | = | 2 |
S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0.Введенные переменные S 1 , S 2 , S 3 называются переменными резерва.
3. Нахождение исходного базиса и значения функции F, соответствующего найденному исходному базису.
Что такое основа?
Переменная называется базовой переменной для уравнения, если она входит в это уравнение с коэффициентом, равным единице, и не входит в другие системы уравнений (при условии, что в правой части уравнения есть неотрицательное число).
Если в каждом уравнении есть базовая переменная, то говорят, что у системы есть базис.
Неосновные переменные называются неосновными.
В чем идея симплекс-метода?
Каждой базе соответствует одно значение функции. Одно из них — максимальное значение функции F.
Будем переходить от одной основы к другой.
Следующий базис будет выбран таким образом, чтобы значение функции F было не меньше, чем у нас сейчас.
Очевидно, что количество возможных оснований для любой задачи невелико.
Так что рано или поздно ответ будет получен.
Как мы будем переходить с одной базы на другую?
Решение удобнее записывать в виде таблиц.Каждая строка таблицы эквивалентна системному уравнению. Выделенная строка состоит из коэффициентов функции (см. Таблицу ниже). Это позволяет нам не перезаписывать переменные каждый раз. Экономит время.
В выделенной строке выберите максимальный положительный коэффициент (мы можем выбрать любой положительный коэффициент).
Это необходимо для того, чтобы получить значение функции F не меньше, чем у нас.
Столбец выбран.
Для положительных коэффициентов выбранного столбца подсчитываем коэффициент Θ и выбираем минимальное значение.
Это необходимо для того, чтобы после перехода на другой базис получить неотрицательные числа в правой части уравнений.
Строка выбрана.
Найден элемент, который будет основным. Далее нам нужно будет произвести расчет.
Есть ли у нашей системы база?
x 1 | + | 2 | x 2 | + | S 1 64 | 2 | x 1 | + | x 2 | + | S 2 | 3 8909 909 909 909 909 909 909 909 x 2 | + | S 3 | = | 2 |
Есть основу в нашей системе.Мы можем приступить к решению нашей проблемы.
Неосновные переменные равны нулю. В уме мы можем найти значения основных переменных. (см. систему)
Функция F содержит только неосновные переменные. Следовательно, значение функции F для этого базиса можно найти в уме.
x 1 = 0 x 2 = 0 S 1 = 6 S 2 = 8 S 3 = 2 | => F = 0 |
Исходная база найдена.Найдено значение функции F, соответствующее исходному базису.
4. Нахождение максимального значения функции F.
Шаг 1
x 1 | x 2 | S 1 | S 2 | S 3 | конст. | Θ |
1 | 2 | 1 | 0 | 0 | 6 | 6: 2 = 3 |
2 | 1 | 0 | 0 | 8: 1 = 8 | ||
0 | 1 | 0 | 0 | 1 | 2 | 2: 1 = 2 |
1 | 2 | 0 | 0 | 0 | Ф — 0 | |
1 | 0 | 1 | 0 | -2 | 2 | |
2 | 0 | 1 | 6 | |||
0 | 1 | 0 | 0 | 1 | 2 | |
1 | 0 9 0964 | 0 | 0 | -2 | F — 4 |
Неосновные переменные равны нулю.В уме мы можем найти значения основных переменных. (см. таблицу)
Функция F содержит только неосновные переменные. Следовательно, значение функции F для этого базиса можно найти в уме. (см. выделенную строку в таблице)
x 1 = 0 S 3 = 0 x 2 = 2 S 1 = 2 S 2 = 6 | => F — 4 = 0 => F = 4 |
Шаг 2
x 1 | x 2 | S 1 | S 2 | S 3 | конст. | Θ |
1 | 0 | 1 | 0 | -2 | 2 | 2: 1 = 2 |
2 | 0 | -10 | 6 | 6: 2 = 3 | ||
0 | 1 | 0 | 0 | 1 | 2 | |
1 | 0 | 0 | Ф — 4||||
1 | 0 | 1 | 0 | -2 | 2 | |
0 | 0 | -2 | 909 2 909 2965 | |||
0 | 1 | 0 | 0 | 1 | 2 | |
0 | 0 | -1 | 0 | 0 | F — 6 |
Неосновные переменные равны нулю.В уме мы можем найти значения основных переменных. (см. таблицу)
Функция F содержит только неосновные переменные. Следовательно, значение функции F для этого базиса можно найти в уме. (см. выделенную строку в таблице)
S 1 = 0 S 3 = 0 x 1 = 2 x 2 = 2 S 2 = 2 | => F — 6 = 0 => F = 6 |
В выделенной строке нет положительных коэффициентов.Таким образом, было найдено максимальное значение функции F.
Коэффициент равен нулю в позиции 5 выделенной строки. В столбце 5 нет базовой переменной.
Это позволяет нам найти другое решение, в котором F = 6.
Шаг 3
x 1 | x 2 | S 1 | S 2 | S 3 | конст. | Θ | |
1 | 0 | 1 | 0 | -2 | 2 | ||
0 | 0 | -2 | 1 | 2 | 3 ≈ 0,67|||
0 | 1 | 0 | 0 | 1 | 2 | 2: 1 = 2 | |
0 | 0 | -1 | Ф — 6 | ||||
1 | 0 | 1 | 0 | -2 | 2 | ||
0 | 0 | -2/3 909 909 1 | 2/3 | ||||
0 | 1 | 0 | 0 | 1 | 2 | ||
0 | 0 | 90 967-10 | 0 | F — 6 | |||
1 | 0 | -1/3 | 2/3 | 0 | 0/3 | ||
3 | 3 | 0 | -2/3 | 1/3 | 1 | 2/3 | |
0 | 1 | 2/3 | -1/3 | 0 | 4/3 | ||
0 | 0 | -1 | 0 | 0 | F — 6 |
Неосновные переменные равны нулю.В уме мы можем найти значения основных переменных. (см. таблицу)
Функция F содержит только неосновные переменные. Следовательно, значение функции F для этого базиса можно найти в уме. (см. выделенную строку в таблице)
S 1 = 0 S 2 = 0 x 1 = 10/3 x 2 = 4/3 S 3 = 2/3 | => F — 6 = 0 => F = 6 |
С геометрической точки зрения оба решения представляют собой точки пространства, т.е.е. образуют отрезок прямой.
Любая точка (любое решение) на этом отрезке линии также будет решением.
Результат:
X
1 = 2 * t + 10/3 * (1 — t)X
2 = 2 * t + 4/3 * (1 — t)0 ≤ t ≤ 1
F
макс = 62010-2021
Если есть комментарии, пишите на [email protected]
Решение задач линейного программирования — MATLAB linprog
Основан метод 'internal-point-legacy'
на LIPSOL (Linear Interior Point Solver, [3]), который является вариантом предсказателя-корректора Mehrotra.
алгоритм [2], прямодвойственная внутренняя точка
метод.Перед алгоритмом выполняется ряд этапов предварительной обработки.
начинает повторяться. См. Раздел «Внутреннее-точечное-устаревшее линейное программирование».
Первый этап алгоритма может включать некоторую предварительную обработку.
ограничений (см. Линейное программирование внутренних точек и прежних версий). Несколько условий могут
заставить linprog
выйти с сообщением о невозможности выполнения.
В каждом случае linprog
возвращает отрицательный exitflag
,
указывает на сбой.
Если строка всех нулей обнаружена в
Aeq
, но соответствующий элементbeq
не равен нулю, то сообщение о выходе:Выход из-за невозможности: строка со всеми нулями в матрица ограничений не имеет нуля в соответствующем правосторонний вход.
Если один из элементов
x
является обнаружено, что не ограничено снизу, то сообщение о выходе:Выход из-за невозможности: Цель f '* x не ограничена снизу.
Если в одной из строк
Aeq
есть только один ненулевой элемент, тогда соответствующее значение вx
будет называется одноэлементной переменной . В этом случае значение этого компонентаx
может быть вычислено изAeq
иbeq
.Если вычисленное значение нарушает другое ограничение, то сообщение о выходе isВыход из-за невозможности: переменные Singleton в ограничения равенства невозможны.
Если одноэлементная переменная может быть решена для, но решение нарушает верхнюю или нижнюю границы, тогда сообщение о выходе is
Выход из-за невозможности: переменные Singleton в ограничения на равенство выходят за рамки установленных ограничений.
Примечание
Шаги предварительной обработки являются кумулятивными.Например, даже если ваша матрица ограничений не имеет в начале строки всех нулей, другие шаги предварительной обработки могут вызвать появление такой строки.
По окончании предварительной обработки итерационная часть алгоритма начинается до тех пор, пока не будут выполнены критерии остановки. (Для дополнительной информации об остатках, прямой проблеме, двойственной проблеме и связанных критерии остановки см. в разделе «Внутреннее линейное программирование — устаревшее».) Если остатки растут вместо того, чтобы становиться меньше, или остатки не растут и не при сжатии отображается одно из двух следующих сообщений о завершении, соответственно,
Один или несколько остатков, разрыв двойственности или общая относительная ошибка выросло в 100000 раз по сравнению с минимальным значением:
или
Один или несколько остатков, разрыв двойственности или общая относительная ошибка остановился:
После отображения одного из этих сообщений за ним следует одно из следующих сообщений, указывающих, что двойственное, первичное, или оба кажутся невозможными.
Двойник кажется невозможным (и первичный безграничный). (Первичный остаток
Первичный остаток кажется недопустимым (и двойственное неограниченное). (Двойной остаток
Двойственный остаток кажется недопустимым (и прямая неограниченная), поскольку двойная невязка> sqrt (OptimalityTolerance). (Первичный остаток <10 * OptimalityTolerance.)
Первичный вариант кажется невозможным (и двойственный неограниченный), поскольку прямая невязка> sqrt (OptimalityTolerance). (Двойной остаток <10 * OptimalityTolerance.)
Двойной кажется недопустимым и первичная неограниченная, поскольку первичная цель <-1e + 10 и двойная цель <1e + 6.
Первичный выглядит невыполнима, а двойственная неограниченна, поскольку двойная цель> 1e + 10 и основная цель> -1e + 6.
И первичный, и двойной кажутся невозможными.
Например, первичная (цель) может быть неограниченной, а первичный остаток, который является мерой удовлетворения первичного ограничения, может быть маленьким.
Разработка симплекс-метода с помощью NumPy и матричных операций | Сэмюэл Эверетт
После прохождения курсов по исследованию или оптимизации операций (особенно на уровне бакалавриата) и изучения доступных в Интернете ресурсов, охватывающих симплекс-метод, вы почти наверняка познакомитесь с методом таблицы для решения задач линейного программирования с помощью Симплексный метод.Здесь и здесь приведены некоторые примеры решения задач линейного программирования табличным методом.
К сожалению, табличный метод часто является единственным методом, упоминаемым в классах или текстах, посвященных симплексному методу. Таким образом, многие компьютерные программы, реализующие симплекс-метод, напрямую реализуют табличный метод. Табличный метод был разработан для решения задач линейного программирования вручную, карандашом и бумагой. Таким образом, он не является эффективным с вычислительной точки зрения, и его не следует выбирать при реализации симплекс-метода в вычислительной форме.
В связанном здесь блокноте Jupyter я реализую версию симплексного метода, который использует матричные операции в NumPy вместо табличного метода для решения задач оптимизации с линейными ограничениями. Таким образом, мы получаем гораздо более эффективную, лаконичную и естественную реализацию симплексного метода.
Если читатель желает ознакомиться с точной математикой и обозначениями, используемыми в следующей программе, обратитесь к главе 5 книги «Линейное и нелинейное программирование » Нэша и Софера.
Симплексный метод сегодня редко используется на практике, поскольку его преодолели более быстрые методы внутренней точки. Однако, когда симплексный метод реализуется на практике, он обычно разрабатывается с матричной факторизацией, которая предлагает реализацию симплексного метода, которая даже быстрее, чем использование метода матричных операций, приведенного в этом посте. Для задач линейного программирования более низкой размерности приведенный здесь метод матричных операций подходит, однако, когда кто-то начинает решать проблемы с сотнями или тысячами переменных, имеет смысл реализовать симплексный метод с использованием матричных факторизаций.
Я надеюсь, что этот пост дал читателю интуитивное понимание менее упомянутых, но в конечном итоге более совершенных методов реализации симплекс-метода, и что предлагаемая программа служит полезной альтернативой другим менее эффективным реализациям симплекс-метода, которые используйте табличный метод.
Книжный список- Линейное программирование и сетевые потоки, Bazaraa
- Линейное и нелинейное программирование, Нэш
- Линейное и нелинейное программирование 1424 920 Conveberger 920
Использование симплексного метода транспортировки для решения проблем транспортировки
Симплексный алгоритм транспортировки
Симплексный алгоритм транспортировки - это линейная программа, математическая модель, представляющая линейные отношения, такие как транспортировка между поставщиком и пунктом назначения. Линейное программирование позволяет пользователю найти оптимальный или лучший результат. Мы хотим перевезти нашу продукцию с минимальными затратами, чтобы получить максимальную прибыль.
Во-первых, нам нужно знать наши параметры или аргументы, по сути, данные, которые нам нужны для решения проблемы:
- Стоимость доставки за единицу : Сколько стоит отгрузка каждого грузовика с продуктом?
- Припасы : количество грузовиков, которое может предоставить каждое предприятие.
- Спрос : количество грузовиков, необходимое для каждого пункта назначения.
Как это выглядит
Давайте начнем заполнять транспортную матрицу, чтобы у нас были все наши данные в одном месте. Во-первых, мы находим стоимость одной грузовой партии от каждого из наших поставщиков в каждый из наших пунктов назначения. Доставка от Поставщика 1 до пункта назначения 1 будет стоить 464 доллара США за грузовик, а доставка от Поставщика 1 до пункта назначения 2 и т. Д. Будет стоить 513 долларов США за грузовик.
Матрица транспортировки: стоимость доставки Затем мы включаем количество грузовиков, которые может поставить каждый поставщик и которые требуются каждому пункту назначения.Мы сделаем это легко, и наши предложения будут соответствовать нашему спросу.
Транспортная матрица: спрос и предложение Метод наименьшей стоимости
Мы хотим найти базовое возможное решение (BFS) , означающее потенциальное решение нашей транспортной проблемы. Мы можем использовать правило северо-западного угла, метод наименьших затрат или метод аппроксимации Фогеля. Поскольку мы хотим максимизировать нашу прибыль, давайте воспользуемся методом минимальной стоимости ячейки.
Мы ищем в нашей транспортной матрице ячейку с наименьшей стоимостью (отмечена здесь красным). Мы хотим направить на этот транспортный маршрут как можно больше поставок. В пункте назначения 2 нужно 85 грузовиков, в пункте снабжения 2 - 125, поэтому мы собираемся выполнить все заказы пункта назначения 2 из пункта снабжения 2 (синим цветом).
Теперь мы находим следующую наименьшую стоимость, Поставщик 2 для пункта назначения 1 (снова показан красным). Мы уже назначили 85 из доступных запасов Припуска 2, поэтому у нас есть только 40, которые можно назначить Пункту назначения 1 из Припуска 2.
Это уничтожает снабжение 2, поэтому мы избавляемся от снабжения 2 в пункте назначения 3 и находим следующую наименьшую стоимость, то есть снабжение 3 в пункт назначения 3. Мы можем заполнить 100 из 110 грузовиков, что уничтожит снабжение 3.
Следующая наименьшая стоимость - Поставка 1 в пункт назначения 1.
Это оставляет нам 10 из Ресурса 1, чтобы заполнить Пункт назначения 3 по 654 доллара.
Расчет затрат
Теперь давайте рассчитаем наши затраты, умножив количество грузовых автомобилей на стоимость назначенного маршрута транспортировки.
Как узнать, что у нас есть лучшее решение нашей транспортной проблемы? Надо это проверить!
Тест оптимальности
Мы могли бы проделать много математических вычислений линейного программирования, чтобы проверить это, но зачем делать это, если у нас есть доступ к отличному инструменту в Excel под названием Solver ? Solver доступен как надстройка к вашей программе Excel и значительно упрощает тестирование на оптимальность.
Сначала, как и наша транспортная матрица, настроим данные о затратах:
Решатель Excel: стоимость доставки Затем мы настроим объемные данные, включая формулы для суммирования спроса и предложения, а также общих транспортных расходов.
Решатель: Объем Теперь мы готовы использовать Решатель. Давайте разберем диалоговое окно на более мелкие части, чтобы вы могли четко видеть каждую из них.
Мы устанавливаем нашу целевую ячейку как B17, ячейку, в которой нам нужны общие транспортные расходы, и мы хотим, чтобы это значение было как можно меньше. Затем установите изменения в ячейках, которые содержат количество единиц для каждого пункта назначения от каждого поставщика (B11: D13).
Решатель Excel: Целевая ячейка Затем мы добавляем наши ограничения. Общая поставка не может быть больше, чем мощность предложения, а общий спрос должен быть меньше или равен требуемому спросу.
Решатель: ограничения Мы устанавливаем наш метод решения как Simplex LP (что является линейным программированием), а затем выбираем «Решить»
Excel Solver: метод решения Как видите, решение, которое мы разработали с использованием метода наименьших затрат, оказалось оптимальным из имеющихся.
Решатель: Решение Заставляет задуматься, почему мы просто не использовали для начала Excel Solver, не так ли?
Краткое содержание урока
Симплексный метод транспортировки использует линейное программирование для решения транспортных задач.Цель состоит в том, чтобы создать оптимальное решение при наличии нескольких поставщиков и направлений. Требуемые данные включают стоимость доставки за единицу, сколько может произвести каждый поставщик и сколько нужно каждому пункту назначения. Мы создаем транспортную матрицу с этими данными и применяем один из многих методов, чтобы найти базовое возможное решение (BFS) .
Если вы хотите увеличить прибыль и минимизировать расходы, наиболее точным методом является метод минимальной стоимости ячейки .Затем результаты подвергаются тесту на оптимальность, чтобы убедиться, что найдено лучшее решение.