Решение задач симплекс методом примеры для чайников: Решение симплекс методом задачи ЛП: пример и алгоритм

Решение симплекс методом задачи ЛП: пример и алгоритм

Симплекс метод — это метод последовательного перехода от одного базисного решения (вершины многогранника решений) системы ограничений задачи линейного программирования к другому базисному решению до тех пор, пока функция цели не примет оптимального значения (максимума или минимума).

Симплекс метод был предложен американским математиком Р.Данцигом в 1947 году, с тех пор для нужд промышленности этим методом нередко решаются задачи линейного программирования с тысячами переменных и ограничений.

Перед тем, как перейти к алгоритму симплекс метода, несколько определений.

Всякое неотрицательное решение системы ограничений называется допустимым решением.

Пусть имеется система m ограничений с n переменными (m n).

Допустимым базисным решением является решение, содержащее m неотрицательных основных (базисных) переменных и n — m неосновных. (небазисных, или свободных) переменных. Неосновные переменные в базисном решении равны нулю, основные же переменные, как правило, отличны от нуля, то есть являются положительными числами.

Любые m переменных системы m линейных уравнений с n переменными называются основными, если определитель из коэффициентов при них отличен от нуля. Тогда остальные

Алгоритм симплекс метода

• Шаг 1. Привести задачу линейного программирования к канонической форме. Для этого перенести свободные члены в правые части (если среди этих свободных членов окажутся отрицательные, то соответствующее уравнение или неравенство умножить на — 1) и в каждое ограничение ввести дополнительные переменные (со знаком «плюс», если в исходном неравенстве знак «меньше или равно», и со знаком «минус», если «больше или равно»).
• Шаг 2. Если в полученной системе m уравнений, то m переменных принять за основные, выразить основные переменные через неосновные и найти соответствующее базисное решение. Если найденное базисное решение окажется допустимым, перейти к допустимому базисному решению.
• Шаг 3. Выразить функцию цели через неосновные переменные допустимого базисного решения. Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с отрицательными (положительными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным — решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с отрицательными (положительными) коэффициентами, перейти к новому базисному решению.
• Шаг 4. Из неосновных переменных, входящих в линейную форму с отрицательными (положительными) коэффициентами, выбирают ту, которой соответствует наибольший (по модулю) коэффициент, и переводят её в основные. Переход к шагу 2.

• Если допустимое базисное решение даёт оптимум линейной формы (критерий оптимальности выполнен), а в выражении линейной формы через неосновные переменные отсутствует хотя бы одна из них, то полученное оптимальное решение — не единственное.
• Если в выражении линейной формы имеется неосновная переменная с отрицательным коэффициентом в случае её максимизации (с положительным — в случае минимизации), а во все уравнения системы ограничений этого шага указанная переменная входит также с отрицательными коэффициентами или отсутствует, то линейная форма не ограничена при данной системе ограничений. В этом случае её максимальное (минимальное) значение записывают в виде .

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

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

Пример. Найти максимум функции при ограничениях

Решение.

Вводим добавочные неотрицательные переменные и сводим данную систему неравенств к эквивалентной ей системе уравнений

.

Это было сделано с соблюдением следующего правила: если в первоначальном ограничении знак «меньше или равно», то добавочную переменную нужно прибавлять, а если «больше или равно», то добавочную переменную нужно отнимать.

Введённые добавочные переменные принимаем за основные (базисные). Тогда и — неосновные (свободные) переменные.

Выразив основные (базисные) переменные через неосновные (свободные), получим

Функцию цели также выразим через неосновные (свободные) переменные:

Из коэффициентов при переменных (неизвестных) построим первую симплексную таблицу.

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

Полученное решение не оптимально, так как в индексной строке коэффициенты при свободных переменных отрицательны. То есть оптимальным будет то решение, в котором коэффициенты при свободных переменных в индексной строке будут больше или равны нулю.

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Для перехода к следующей таблице найдём наибольшее (по модулю) из чисел и . Это число 2. Поэтому ведущий столбец — тот столбец, в котором записано

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

Итак,

.

Поэтому ведущая строка — та, в которой записано

Ведущим элементом, таким образом, является -2.

Составляем вторую симплексную таблицу.

Новый базисный элемент вписываем первой строкой, а столбец, в котором стояло , вписываем новую свободную переменную

Заполняем первую строку. Для этого все числа, стоящие в ведущей строке таблицы 1, делим на ведущий элемент и записываем в соответствующий столбец первой строки таблицы 2, кроме числа, стоящего в ведущем столбце, куда записывается величина, обратная ведущему элементу (то есть, единица, делённая на ведущий элемент).

Заполняем столбец вспомогательных коэффициентов. Для этого числа ведущего столбца таблицы 1, кроме ведущего элемента, записываем с противоположными знаками в графу вспомогательных коэффициентов таблицы 2.

Кто ещё не открыл в новом окне пособие Действия с дробями, может сделать это сейчас, поскольку самое время.

Для получения остальных строк таблицы 2 числа, уже стоящие в первой строке этой таблицы, умножаем на вспомогательный коэффициент, стоящий в заполняемой строке, и к результату прибавляем число из таблицы 1, стоящее в той же строке при соответствующей переменной.

Например, для получения свободного члена второй строки число 1 умножаем на 1 и прибавляем из таблицы 1 число -4. Получаем -3. Коэффициент при во второй строке находим так же: . Так как в предыдущей таблице отсутствует столбец с новой свободной переменной , то коэффициент второй строки в столбце новой свободной переменной будет (то есть из таблицы 1 прибавляем 0, так как в таблице 1 столбец с отсутствует).

Так же заполняется и индексная строка:

Полученное таким образом решение вновь не оптимально, так как в индексной строке коэффициенты при свободных переменных вновь отрицательны.

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Для перехода к следующей симплексной таблице найдём наибольшее (по модулю) из чисел и , то есть, модулей коэффициентов в индексной строке. Это число 2. Поэтому ведущий столбец — тот столбец, в котором записано .

Для поиска ведущей строки найдём минимум отношений свободных членов к элементам ведущей строки. Получаем:

.

Следовательно, ведущая строка — та, в которой записано , а ведущим элементом является -3/2.

Составляем третью симплексную таблицу

Новую базисную переменную записываем первой строкой. В столбец, в котором было , вписываем новую свободную переменную .

Первая строка:

Вспомогательные коэффициенты:

Вычисление остальных строк на примере второй строки:

Полученное решение вновь не оптимальное, поскольку коэффициенты при свободных неизвестных в индексной строке вновь отрицательные.

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Для перехода к четвёртой симплексной таблице найдём наибольшее из чисел и . Это число .

Следовательно, ведущий столбец — тот, в котором записано .

Для нахождения ведущей строки найдём минимум модулей отношений свободных членов к элементам ведущего столбца:

.

Поэтому ведущая строка — та, в которой записано , а ведущий элемент 1/3.

В четвёртой симплексной таблице новую базисную переменную записываем первой строкой. В столбец, где было , записываем новую свободную переменную .

Первая строка:

Вспомогательные коэффициенты:

.

Вычисление остальных строк на примере второй строки:

Полученное решение так же не оптимально, но оно уже лучше предыдущих, так как один из коэффициентов при свободных переменных в индексной строке неотрицателено.

Для улучшения плана перейдём к следующей симплексной таблице.

Найдём наибольшее из чисел 4 и . Это число 4. Следовательно, ведущий столбец .

Для нахождения ведущей строки найдём

.

Следовательно, ведущая строка — та, в которой записано . Но и уже были вместе среди свободных переменных. Поэтому для перевода очередной переменной из свободных в базисные выбираем другой ведущий столбец — тот, в котором записано .

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Для нахождения ведущей строки найдём

.

Следовательно, ключевая строка — та, в которой записано , а ведущий элемент 1.

В пятой симплексной таблице новую базисную переменную записываем первой строкой. В столбец, где было , записываем новую свободную переменную .

Первая строка:

Вспомогательные коэффициенты:

.

Попробуем сразу узнать, не является ли решение оптимальным. Поэтому для остальных строк вычислим только свободные члены (чтобы узнать значения базисных переменных при равенстве свободных переменных нулю) и коэффициенты при свободных переменных в индексной строке.

Свободные члены:

— во второй строке ;

— в третьей строке ;

— в четвёртой строке .

Индексная строка:

Смотрим в симплексную таблицу 5. Видим, что получено оптимальное решение, так как коэффициенты при свободных неизвестных в индексной строке неотрицательны.

Ответ:

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс методом.

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

Если отыскивается максимум (минимум) линейной формы и в её выражении нет неосновных переменных с положительными (отрицательными) коэффициентами, то критерий оптимальности выполнен и полученное базисное решение является оптимальным — решение окончено. Если при нахождении максимума (минимума) линейной формы в её выражении имеется одна или несколько неосновных переменных с положительными (отрицательными) коэффициентами, перейти к новому базисному решению.

Пример. Найти максимум функции при ограничениях

Решение.

Шаг I. Вводим добавочные неотрицательные переменные и сводим данную систему неравенств к эквивалентной ей системе уравнений

.

Введённые добавочные переменные принимаем за основные, так как в этом случае базисное решение системы легко находится. Тогда и — неосновные переменные.

Выразив основные переменные через неосновные, получим

Следовательно, данному разбиению переменных на основные и неосновные соответствует базисное решение , которое является недопустимым (две переменные отрицательны), а поэтому оно не оптимальное. От этого базисного решения перейдём к улучшенному.

Чтобы решить, какую переменную следует перевести из неосновных в основные, рассмотрим любое из двух имеющихся уравнений последней системы с отрицательными свободными членами, например второе. Оно показывает, что в основные переменные можно перевести и , так как в этом уравнении они имеют положительные коэффициенты (следовательно, при их увеличении, а это произойдёт, если переведём любую из них в основные переменные, переменная увеличится).

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

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

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Шаг II.

Основные переменные , неосновные переменные .

Выразим новые основные переменные через новые неосновные, начиная с выделенного на шаге I уравнения. В результате получим

Следовательно, имеем новое базисное решение , которое также является недопустимым, а поэтому не оптимальным. Но в нём, как мы и предвидели, только одна переменная отрицательна (а именно ).

От полученного базисного решения необходимо перейти к другому. Рассмотрим уравнение с отрицательным свободным членом, т. е. второе уравнение. Оно показывает, что в основные переменные можно перевести и . Переведём в основные переменные . Найдём наименьшее из абсолютных величин отношений свободных членов системы к коэффициентам при . Имеем . Значит, в неосновные переменные нужно перенести . Так как наименьшее отношение получено из второго уравнения, то его выделяем. В новом базисном решении уже не окажется отрицательных компонент, т. е. оно является допустимым.

В особых случаях решение завершается на II шаге: это, например, случаи, когда максимум целевой функции — бесконечность и когда система не имеет ни одного решения.

Шаг III.

Основные переменные: , неосновные переменные: . Выразив основные переменные через неосновные, получим

Новое базисное решение имеет вид . Является ли оно оптимальным, можно установить, если выразить линейную форму через неосновные переменные рассматриваемого базисного решения. Сделав это, получим . Так как мы ищем максимум линейной формы, а нашли лишь одно допустимое решение, то продолжим перебор.

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

В некотором особом случае решение завершается на III шаге: это случай, когда оптимальное решение — не единственное.

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Шаг IV.

Основные переменные: , неосновные переменные: . Выразив основные переменные через неосновные, получим

Линейная форма, выраженная через те же неосновные переменные, примет вид . Продолжим перебор для поиска максимума.

Увеличение линейной формы возможно при переходе к новому базисному решению, в котором переменная является основной. Находим . Это наименьшее отношение получено из четвёртого уравнения системы и показывает, что при переменная и переходит в число неосновных.

Шаг V.

Основные переменные: , неосновные переменные: . Выразив основные переменные через неосновные, получим

Линейная форма, выраженная через неосновные переменные нового базисного решения, имеет вид . Критерий оптимальности для случая максимизации линейной формы выполнен. Следовательно, базисное решение является оптимальным, а максимум линейной формы

На сайте есть Онлайн калькулятор решения задач линейного программирования симплекс-методом.

Начало темы «Линейное программирование»

Продолжение темы «Линейное программирование»

Поделиться с друзьями

Симплекс-метод, примеры решения задач

Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач симплекс-методом. Первая задача содержит знаки неравенства только » ≤ » (задача с начальным базисом), вторая может содержить знаки » ≥ «, » ≤ » или » = » (задача с искусственным базисом), они решаются по разному.

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

1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений » ≤ «).

Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:

Эта система является системой с базисом (базис s₁, s₂, s₃, каждая из них входит только в одно уравнение системы с коэффициентом 1), x₁ и x₂ — свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: -система ограничений должна быть системой уравнений с базисом; -свободные члены всех уравнений в системе должны быть неотрицательны.

Полученная система — система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод, т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь «БП» означает столбец базисных переменных, «Решение» — столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

симплекс-метод итерация 0

Для улучшения решения перейдем к следующей итерации симплекс-метода, получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец, т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации симплекс-метода это столбец x₂ (коэффициент -6).

Затем выбирается разрешающая строка, т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца «Решение» к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s₃ (коэффициент 20).

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x₂ заменит в базисе s₁. Заметим, что в z-строке отношение не ищется, там ставится прочерк » — «. В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований — превратить разрешающий столбец х₂ в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).

1)Вычисление строки х₂ таблицы «Итерация 1». Сначала делим все члены разрешающей строки s₃ таблицы «Итерация 0» на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x₂ в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s₃ таблицы «Итерация 0» будет совпадать со строкой х₂ таблицы «Итерация 1». Строку x₂ таблицы «Итерации 1» мы получили 0 1 0 0 1 20, остальные строки таблицы «Итерация 1» будут получены из этой строки и строк таблицы «Итерация 0» следующим образом:

2) Вычисление z-строки таблицы «Итерация 1». На месте -6 в первой строке (z-строке) в столбце х₂ таблицы «Итерация 0» должен быть 0 в первой строке таблицы «Итерация 1». Для этого все элементы строки х₂ таблицы «Итерация 1» 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z — строкой) таблицы «Итерация 0» -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x₂ появился ноль 0, цель достигнута. Элементы разрешающего столбца х₂ выделены красным цветом.

3) Вычисление строки s₁ таблицы «Итерация 1». На месте 1 в s₁ строке таблицы «Итерация 0» должен быть 0 в таблице «Итерация 1». Для этого все элементы строки х₂ таблицы «Итерация 1» 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s₁ — строкой таблицы «Итерация 0» 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х₂ получен необходимый 0.

4) Вычисление строки s₂ таблицы «Итерация 1». На месте 3 в s₂ строке таблицы «Итерация 0» должен быть 0 в таблице «Итерация 1». Для этого все элементы строки х₂ таблицы «Итерация 1» 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s₁ — строкой таблицы «Итерация 0» 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х₂ получен нужный 0. Столбец х₂ в таблице «Итерация 1» стал единичным, он содержит одну 1 и остальные 0.

Строки таблицы «Итерация 1» получаем по следующему правилу:

Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).

Например для z-строки имеем:

Старая z-строка                                              (-4   -6 0 0 0 0) -(-6)*Новая разрешающая строка                 -(0 -6 0 0 -6 -120) =Новая z-строка (-4 0 0 0 6 120).

Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.

симплекс-метод итерация 1

Разрешающий столбец х₁, разрешающая строка s₂, s₂ выходит из базиса, х₁ входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.

симплекс-метод итерация 2

Разрешающий столбец s₃, разрешающая строка s₁, s₁ выходит из базиса, s₃ входит в базис.

симплекс-метод итерация 3

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x₁ = 24, x₂ = 16, z_max = 192.

Линейное программирование. Симплекс-метод | Решатель

Рассмотрим симплекс-метод для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
 

Алгоритм симплекс-метода следующий:
 

1. Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+), если же вида ≥ то со знаком (—). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0, т.к. целевая функция не должна при этом менять свой экономический смысл.
2. Выписываются вектора P_i из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.
3. После этого исходные данные вводятся в симплекс-таблицу. В базис вносятся единичные вектора, и исключая их из базиса, находят оптимальное решение. Коэффициенты целевой функции записывают с противоположным знаком.
4. Признак оптимальности для задачи ЛП – решение оптимально, если в f – строке все коэффициенты положительны. Правило нахождения разрешающего столбца – просматривается f – строка и среди ее отрицательных элементов выбирается наименьшее. Вектор P_i его содержащий становится разрешающим. Правило выбора разрешающего элемента – составляются отношения положительных элементов разрешающего столбца к элементам вектора Р₀ и то число, которое дает наименьшее отношение становится разрешающим элементом, относительно которого будет произведен пересчет симплекс-таблицы. Строка, содержащая этот элемент называется разрешающей строкой. Если в разрешающем столбце нет положительных элементов, то задача не имеет решения. После определения разрешающего элемента переходят к пересчету новой симплекс – таблицы.
5. Правила заполнения новой симплекс – таблицы. На месте разрешающего элемента проставляют единицу, а другие элементы полагают равными 0. Разрешающий вектор вносят в базис, из которого исключают соответствующий нулевой вектор, а остальные базисные вектора записывают без изменений. Элементы разрешающей строки делят на разрешающий элемент, а остальные элементы пересчитывают по правилу прямоугольников.
6. Так поступают до тех пор, пока в f – строке все элементы не станут положительными.

Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:

Приводим задачу к каноническому виду:

Составляем вектора:

Заполняем симплекс – таблицу:

Правило прямоугольников:
Пересчитаем первый элемент вектора Р₀, для чего составляем прямоугольник из чисел: и получаем: .

Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:

В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P₁. Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:

Отсутствие отрицательных элементов в f – строке означает, что найден оптимальный план:
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).
 

Рекомендуемая литература

• Ашманов С. А. Линейное программирование, М: Наука, 1998г.,
• Вентцель Е.С. Исследование операций, М: Советское радио, 2001г.,
• Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б. Математическое программирование, М: Высшая школа, 1986г.

Решение линейного программирования на заказ

Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на странице заказа.

Симплекс метод онлайн

Данный онлайн калькулятор решает задачу линейного программирования симплекс методом. Дается подробное решение с пояснениями. Для решения задачи линейного программирования задайте количество ограничений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить». Теоретическую часть смотрите в статье: Решение задачи линейного программирования. Симплекс метод.

Очистить все ячейки?

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

Симплекс метод − это метод решения задачи линейного программирования (ЗЛП). Суть метода заключается в нахождении начального допустимого плана, и в последующем улучшении плана до достижения максимального (или минимального) значения целевой функции в данном выпуклом многогранном множестве или выяснения неразрешимости задачи. Подробнее в статье: Решение задачи линейного программирования. Симплекс метод.

Примеры решения ЗЛП симплекс методом

Пример 1. Решить следующую задачу линейного программирования:

Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1. Последние три векторы столбцы обазуют базис в трехмерном пространствое. Следовательно базисные переменные , а свободные переменные :

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x₃. Сделаем исключение Гаусса для столбца x₂, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x₁. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x₄. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F(X)=.

Пример 2. Найти максимум функции

при условиях

Р е ш е н и е. Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последняя строка — это целевая функция, умноженная на −1:

Базисные векторы x₄, x₃, следовательно, все элементы в столбцах x₄, x₃, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₄, кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x₃, кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x₂. Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

при условиях

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x₂. Сделаем исключение Гаусса для столбца x₁, учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x₃. Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x₅. Сделаем исключение Гаусса для столбца x₃, учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Симплекс таблица примет следующий вид:

Запишем текущий опорный план:

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

Значение целевой функции в данной точке:

Пример 2. Найти оптимальный план задачи линейного программирования:

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственные переменные, а в целевую функцию добавляем эти переменные, умноженные на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Правая часть ограничений системы уравнений имеет вид:

Составляем симплексную таблицу. В столбец x₀ записывается правая часть ограничений. С правой стороны записывается матрица коэффициентов A. Последние две строки − это целевая функция, умноженная на −1 и разделенная на две части. Последняя строка − строка с исскуственными переменными:

Базисные векторы x₄, x₅, x₆, следовательно, все элементы в столбцах x₄, x₅, x₆, ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x₄, кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x₅, кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x₆, кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

Запишем текущий опорный план:

В строке 5 элементы, соответствующие переменным x₁, x₂, x₃, x₄, x₅, x₆ неотрицательны, а число находящийся в пересечении данной строки и столбца x₀ отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

Подробный разбор симплекс-метода / Хабр

Пролог

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

§1. Постановка задачи линейного программирования

Общая задача линейного программирования (далее – ЛП) имеет вид:

§2. Каноническая форма задачи ЛП

Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

1. Неравенства с отрицательными $inline$b_i$inline$ умножаем на (-1).
2. Если неравенство вида (≤), то к левой части добавляем $inline$s_i$inline$ – добавочную переменную, и получаем равенство.
3. Если неравенство вида (≥), то из левой части вычитаем $inline$s_i$inline$, и получаем равенство.
4. Делаем замену переменных:

• Если $inline$x_i ≤ 0$inline$, то $inline$x_i’= -x_i ≥ 0$inline$
• Если $inline$x_i$inline$ — любой, то $inline$x_i= x_i’ — x_i»$inline$, где $inline$x_i’, x_i»≥ 0$inline$

Иными словами, невозможно найти две точки в области, интервал проходящий через которые содержит $inline$Х$inline$ (т.е. $inline$Х$inline$ – не внутренняя точка).

Графический способ решения задачи ЛП показывает, что нахождение оптимального решения ассоциируется с угловой точкой. Это является основной концепцией при разработке симплекс-метода.

Определение: Пусть есть система m уравнений и n неизвестных (m < n). Разделим переменные на два множества: (n-m) переменные положим равными нулю, а остальные m переменных определяются решением системы исходных уравнений. Если это решение единственно, то тогда ненулевые m переменных называют базисными; нулевые (n-m) переменных – свободными (небазисными), а соответствующие результирующие значения переменных называют базисным решением.

§4. Симплекс-метод

Замечание: Базисный вектор имеет размерность (m*1), где m – количество уравнений в системе ограничений.

Для удобства вычислений и наглядности обычно пользуются симплекс-таблицами:

• В первой строке указывают «наименование» всех переменных.
• В первом столбце указывают номера базисных переменных, а в последней ячейке – букву Z (это строка функционала).
• В «середине таблицы» указывают коэффициенты матрицы ограничений — aij.
• Последний столбец – вектор правых частей соответствующих уравнений системы ограничений.
• Крайняя правая ячейка – значение целевой функции. На первой итерации ее полагают равной 0.

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

Замечание: Коэффициенты в строке функционала берутся со знаком “-”.

Алгоритм симплекс-метода:

1. Выбираем переменную, которую будем вводить в базис. Это делается в соответствии с указанным ранее принципом: мы должны выбрать переменную, возрастание которой приведет к росту функционала. Выбор происходит по следующему правилу:

• Если задача на минимум – выбираем максимальный положительный элемент в последней строке.
• Если задача на максимум – выбираем минимальный отрицательный.

Замечание: Хотя мы и берем минимальное отрицательное число в задаче на максимум, этот коэффициент показывает направление роста функционала, т.к. строка функционала в симплекс-таблице взята со знаком “-”. Аналогичная ситуация с минимизацией.

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

2. Выбираем переменную, которую будем вводить в базис. Для этого нужно определить, какая из базисных переменных быстрее всего обратится в нуль при росте новой базисной переменной. Алгебраически это делается так:

• Вектор правых частей почленно делится на ведущий столбец
• Среди полученных значений выбирают минимальное положительное (отрицательные и нулевые ответы не рассматривают)

Замечание: Фактически, мы выражаем старые базисные переменные из каждого уравнения системы ограничений через остальные переменные и смотрим, в каком уравнении возрастание новой базисной переменной быстрее всего даст 0. Попадание в такую ситуацию означает, что мы «наткнулись» на новую вершину. Именно поэтому нулевые и отрицательные элементы не рассматриваются, т.к. получение такого результата означает, что выбор такой новой базисной переменной будет уводить нас из области, вне которой решений не существует.

3. Ищем элемент, стоящий на пересечении ведущих строки и столбца.

Определение: Такой элемент называется ведущим элементом.

4. Вместо исключаемой переменной в первом столбце (с названиями базисных переменных) записываем название переменной, которую мы вводим в базис.

5. Далее начинается процесс вычисления нового базисного решения. Он происходит с помощью метода Жордана-Гаусса.

• Новая Ведущая строка = Старая ведущая строка / Ведущий элемент
• Новая строка = Новая строка – Коэффициент строки в ведущем столбце * Новая Ведущая строка

6. После этого проверяем условие оптимальности. Если полученное решение неоптимально – повторяем весь процесс снова.

§5. Интерпретация результата работы симплекс-метода

Условие оптимальности полученного решения:

• Если задача на максимум – в строке функционала нет отрицательных коэффициентов (т.е. при любом изменении переменных значение итогового функционала расти не будет).
• Если задача на минимум – в строке функционала нет положительных коэффициентов (т.е. при любом изменении переменных значение итогового функционала уменьшаться не будет).

Однако, стоит отметить, что заданный функционал может не и достигать максимума/минимума в заданной области. Алгебраический признак этого можно сформулировать следующим образом:

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

Фактически, это значит, что какой бы рост мы не задавали новой базисной переменной, мы никогда не найдем новую вершину. А значит, наша функция не ограничена на множестве допустимых решений.

3. Альтернативные решения

При нахождении оптимального решения возможен еще один вариант – есть альтернативные решения (другая угловая точка, дающая то же самое значение функционала).

Алгебраический признак существования альтернативы:

После достижения оптимального решения имеются нулевые коэффициенты при свободных переменных в строке функционала.

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

Эпилог

Чуть позже напишу статью о практической реализации симплекс-метода, а также несколько статей о Методе искусственных переменных (М-Метод), Методе Гомори и Методе ветвей и границ.

Спасибо за внимание!

P.S.

Если уже сейчас Вы мучаетесь с реализацией симплекс-метода, советую почитать книгу А. Таха Введение в исследование операций — там все неплохо разобрано и в теории, и на примерах; а также посмотрите примеры решения задач matburo.ru — это поможет с реализацией в коде.

Пример — Табличный симплекс метод

Необходимо решить задачу линейного программирования.
Целевая функция:
2x ₁+5x₂+3x₃+8x₄ →min
Ограничивающие условия:
3x₁+6x₂-4x₃+x₄≤12
4x₁-13x₂+10x₃+5x₄≥6
3x₁+7x₂+x₃≥1
Приведем систему ограничений к каноническому виду, для этого необходимо перейти от неравенств к равенствам, с добавлением дополнительных переменных.
Так как наша задача – задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x₅ и изменив знак “≤” на “=”. Т. к. второе и третье неравенства имеют знаки “≥” необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x₆ и x₇ соответственно. В результате получем эквивалентную задачу:
3x₁+6x₂-4x₃+x₄+x₅=12
-4x₁+13x₂-10x₃-5x₄+x₆=-6
-3x₁-7x₂-x₃+x₇=-1
Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции с противоположным знаком.

В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю – это элемент: -6, он задает ведущую строку – X6. В этой строке так же находим максимальный по модулю отрицательный элемент: -10 он находится в столбце X3 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:

В составленой нами таблице имеются отрицательные элементы в столбце свободных членов, находим среди них максимальный по модулю – это элемент: -0.4, он задает ведущую строку – X7. В этой строке так же находим максимальный по модулю отрицательный элемент: -8.3 он находится в столбце X2 который будет ведущим столбцом. Переменная в ведущей строке исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис. Пересчитаем симплекс-таблицу:

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент – это -1.988 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X2, а ведущий элемент: 0.313.

Так как в строке F нет отрицательных элементов, то
найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. F=1.924
при значениях переменных равных: x₃=0.539, x₁=0.153. Переменные x₂ и x₄ не входят в базис, поэтому x₂=0 x₄=0.

Решение задач симплекс методом. Пример работы программы

Разработка сайтов и программного обеспечения, системное администрирование, обучение программированию и работе с СУБД MySQL

Главная → Проекты → Реализация метода искусственного базиса (М-метода) → Пример

Реализация симплекс-метода в случае произвольных свободных членов методом искусственного базиса (M-методом)

Исходные данные:

F(x)= 1.0*x₁+ 4.0*x₂

Введем выравнивающие и искусственные переменные:

F(x)= 1.0*x₁+ 4.0*x₂ — M*(y₁ +y₂) → max

Начнем решение задачи:

Шаг №1

Шаг №2

Шаг №3

Шаг №4

Шаг №5

Реклама:

Метки: симплекс метод.

Комментарии:

имя:

e-mail (не публикуется):

комментарий:

4.2: Максимизация симплексным методом

В предыдущей главе мы использовали геометрический метод для решения задач линейного программирования, но геометрический подход не будет работать для задач, которые содержат более двух переменных. В реальных жизненных ситуациях задачи линейного программирования состоят буквально из тысяч переменных и решаются компьютерами. Мы можем решить эти задачи алгебраически, но это будет не очень эффективно. Предположим, нам поставили задачу с, скажем, 5 переменными и 10 ограничениями.Выбирая все комбинации пяти уравнений с пятью неизвестными, мы могли найти все угловые точки, проверить их на выполнимость и найти решение, если оно существует. Но проблема в том, что даже для задачи с таким небольшим количеством переменных мы получим более 250 угловых точек, и проверка каждой точки будет очень утомительной. Итак, нам нужен метод, который имеет систематический алгоритм и может быть запрограммирован для компьютера. Метод должен быть достаточно эффективным, чтобы нам не приходилось оценивать целевую функцию в каждой угловой точке.У нас есть как раз такой метод, и он называется симплексным методом .

Симплексный метод был разработан во время Второй мировой войны доктором Джорджем Данцигом. Его модели линейного программирования помогли союзным войскам с проблемами транспортировки и планирования. В 1979 году советский ученый Леонид Хачян разработал метод под названием эллипсоидный алгоритм, который должен был стать революционным, но, как оказалось, он не лучше симплексного метода. В 1984 году Нарендра Кармаркар, научный сотрудник AT&T Bell Laboratories, разработал алгоритм Кармаркара, который оказался в четыре раза быстрее симплексного метода для решения некоторых задач.Но симплексный метод по-прежнему лучше всего подходит для большинства задач.

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

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

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

Теперь мы используем симплексный метод для решения примера 3.1.1, геометрически решенного в разделе 3.1.

Пример \ (\ PageIndex {1} \)

Ники работает с неполным рабочим днем ​​на двух работах: I и II. Она никогда не хочет работать больше 12 часов в неделю. Она определила, что на каждый час, который она работает в Задании I, ей нужно 2 часа времени на подготовку, и на каждый час, который она работает в Задании II, ей требуется один час времени на подготовку, и она не может потратить более 16 часов на подготовку.Если она зарабатывает 40 долларов в час на работе I и 30 долларов в час на работе II, сколько часов она должна работать в неделю на каждой работе, чтобы максимизировать свой доход?

Решение

При решении этой проблемы мы будем следовать алгоритму, указанному выше.

ШАГ 1. Устраните проблему. Напишите целевую функцию и ограничения.

Поскольку симплексный метод используется для задач, состоящих из многих переменных, нецелесообразно использовать переменные \ (x \), \ (y \), \ (z \) и т. Д.Мы используем символы \ (x_1 \), \ (x_2 \), \ (x_3 \) и так далее.

Пусть

• \ (x_1 \) = Количество часов в неделю Ники будет работать на работе I и
• \ (x_2 \) = Количество часов в неделю Ники будет работать на Работе II.

Обычно выбирают максимальную переменную как \ (Z \).

Задача формулируется так же, как и в предыдущей главе.

\ [\ begin {array} {ll}
\ textbf {Maximize} & \ mathrm {Z} = 40 \ mathrm {x} _ {1} +30 \ mathrm {x} _ {2} \\
\ textbf {При условии:} & \ mathrm {x} _ {1} + \ mathrm {x} _ {2} \ leq 12 \\
& 2 \ mathrm {x} _ {1} + \ mathrm {x} _ { 2} \ leq 16 \\
& \ mathrm {x} _ {1} \ geq 0; \ mathrm {x} _ {2} \ geq 0
\ end {array} \ nonumber \]

ШАГ 2.Преобразуйте неравенства в уравнения. Это делается путем добавления одной резервной переменной для каждого неравенства.

Например, чтобы преобразовать неравенство \ (x_1 + x_2 ≤ 12 \) в уравнение, мы добавляем неотрицательную переменную \ (y_1 \), и получаем

\ [x_1 + x_2 + y_1 = 12 \ nonumber \]

Здесь переменная \ (y_1 \) подбирает провисание и представляет величину, на которую \ (x_1 + x_2 \) отстает от 12. В этой задаче, если Ники работает менее 12 часов, скажем 10, то \ (y_1 \) равно 2.Позже, когда мы считываем окончательное решение из симплексной таблицы, значения переменных резервирования будут определять неиспользованные суммы.

Перепишем целевую функцию \ (Z = 40x_1 + 30x_2 \) как \ (- 40x_1 — 30x_2 + Z = 0 \).

После добавления переменных резервирования наша задача читает

\ [\ begin {array} {ll}
\ text {Целевая функция} & — 40x_1 — 30x_2 + Z = 0 \\
\ text {Подлежит ограничению:} & x_1 + x_2 + y_1 = 12 \\
& 2x_1 + x_2 + y_2 = 16 \\
& x1 ≥ 0; x2 ≥ 0
\ конец {массив} \ nonumber \]

ШАГ 3.Построить исходную симплексную таблицу . Каждое ограничение неравенства отображается в отдельной строке. (Ограничения неотрицательности не отображаются в виде строк в симплексной таблице , а не .) Запишите целевую функцию в нижней строке.

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

Здесь вертикальная линия отделяет левую часть уравнения от правой.Горизонтальная линия отделяет ограничения от целевой функции. Правая часть уравнения представлена ​​столбцом C.

Читателю необходимо заметить, что последние четыре столбца этой матрицы выглядят как окончательная матрица для решения системы уравнений. Если мы произвольно выберем \ (x_1 = 0 \) и \ (x_2 = 0 \), мы получим

\ [\ left [\ begin {array} {ccccc}
y_ {1} & y_ {2} & Z & | & C \\
1 & 0 & 0 & | & 12 \\
0 & 1 & 0 & | & 16 \\
0 & 0 & 1 & | & 0
\ конец {массив} \ right] \ nonumber \]

, что означает

\ [y_1 = 12 \ quad y_2 = 16 \ quad Z = 0 \ nonumber \]

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

ШАГ 4. Самая отрицательная запись в нижней строке определяет сводный столбец.

Самая отрицательная запись в нижней строке -40; поэтому столбец 1 идентифицируется.

Вопрос Почему мы выбираем наиболее отрицательную запись в нижней строке?

Ответ Самая отрицательная запись в нижней строке представляет собой наибольший коэффициент в целевой функции — коэффициент, вход которого будет увеличивать значение целевой функции быстрее всего.

Симплексный метод начинается в угловой точке, где все основные переменные, переменные с такими символами, как \ (x_1 \), \ (x_2 \), \ (x_3 \) и т. Д., Равны нулю. Затем он перемещается от угловой точки к соседней угловой точке, всегда увеличивая значение целевой функции. В случае целевой функции \ (Z = 40x_1 + 30x_2 \) имеет смысл увеличивать значение \ (x_1 \), а не \ (x_2 \). Переменная \ (x_1 \) представляет количество часов в неделю, которые Ники работает на Job I.Поскольку работа I платит 40 долларов в час, в то время как работа II платит только 30 долларов, переменная \ (x_1 \) увеличит целевую функцию на 40 долларов за единицу увеличения переменной \ (x_1 \).

ШАГ 5. Рассчитайте частные. Наименьшее частное определяет строку. Элемент на пересечении столбца, указанного на шаге 4, и строки, указанной на этом шаге, идентифицируется как опорный элемент.

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

Наименьшее из двух частных, 12 и 8, равно 8. Следовательно, строка 2 идентифицируется. Пересечение столбца 1 и строки 2 — это запись 2, которая была выделена. Это наш стержневой элемент.

Вопрос Почему мы находим частные и почему наименьшее частное определяет строку?

Ответ Когда мы выбираем наиболее отрицательную запись в нижней строке, мы пытаемся увеличить значение целевой функции, вводя переменную \ (x_1 \).Но мы не можем выбрать какое-либо значение для \ (x_1 \). Можем ли мы позволить \ (x_1 = 100 \)? Точно нет! Это потому, что Ники никогда не хочет работать более 12 часов на обеих работах вместе: \ (x_1 + x_2 ≤ 12 \). Можем ли мы позволить \ (x_1 = 12 \)? Опять же, ответ — нет, потому что время на подготовку к работе I в два раза больше времени, затрачиваемого на работу. Поскольку Ники никогда не хочет тратить на подготовку более 16 часов, максимальное время, которое она может работать, составляет 16 ÷ 2 = 8.

Теперь вы видите цель вычисления частных; использование частных для определения опорного элемента гарантирует, что мы не нарушаем ограничения.

Вопрос Почему мы идентифицируем элемент поворота?

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

Переменная, единицы измерения которой добавляются, называется входной переменной , , а переменная, единицы измерения которой заменяются, называется исходящей переменной . Входящей переменной в приведенной выше таблице является \ (x_1 \), и она была идентифицирована самой отрицательной записью в нижней строке. Исходящая переменная \ (y_2 \) была идентифицирована наименьшим из всех частных.

ШАГ 6. Выполните поворот, чтобы обнулить все остальные записи в этом столбце.

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

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

Чтобы получить ноль в элементе ниже точки поворота, мы умножаем вторую строку на 40 и добавляем ее к последней строке.

Теперь мы определяем базовое решение, связанное с этой таблицей. Произвольно выбирая \ (x_2 = 0 \) и \ (y_2 = 0 \), мы получаем \ (x_1 = 8 \), \ (y_1 = 4 \) и \ (z = 320 \). Если мы напишем расширенную матрицу, левая часть которой представляет собой матрицу со столбцами, в которых одна единица и все остальные нули, мы получим следующую матрицу, указывающую то же самое.

\ [\ left [\ begin {array} {ccccc}
\ mathrm {x} _ {1} & \ mathrm {y} _1 & \ mathrm {Z} & | & \ mathrm {C} \\
0 & 1 & 0 & | & 4 \\
1 & 0 & 0 & | & 8 \\
0 & 0 & 1 & | & 320
\ end {array} \ right] \ nonumber \]

Мы можем переформулировать решение, связанное с этой матрицей, как \ (x_1 = 8 \), \ (x_2 = 0 \), \ (y_1 = 4 \), \ (y_2 = 0 \) и \ (z = 320 \) .На этом этапе игры говорится, что если Ники проработает 8 часов на Работе I и не будет часов на Работе II, ее прибыль Z составит 320 долларов. Напомним из примера 3.1.1 в разделе 3.1, что (8, 0) была одной из наших угловых точек. Здесь \ (y_1 = 4 \) и \ (y_2 = 0 \) означают, что у нее останется 4 часа рабочего времени и никакого времени на подготовку.

ШАГ 7. Когда в нижнем ряду больше нет отрицательных записей, мы закончили; в противном случае мы снова начинаем с шага 4.

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

Делаем опорный элемент 1, умножая строку 1 на 2, и получаем

Теперь, чтобы сделать все остальные записи в этом столбце нулями, мы сначала умножаем строку 1 на -1/2 и добавляем ее к строке 2, а затем умножаем строку 1 на 10 и добавляем ее к нижней строке.

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

Вопрос Почему мы закончили, если в нижней строке нет отрицательных записей?

Ответ Ответ находится в нижней строке. Нижняя строка соответствует уравнению:

\ [\ begin {array} {l}
0 x_ {1} +0 x_ {2} +20 y_ {1} +10 y_ {2} + Z = 400 \ quad \ text {или} \\
z = 400-20 лет 1-10 лет 2
\ end {array} \ nonumber \]

Поскольку все переменные неотрицательны, максимальное значение \ (Z \), которое когда-либо может быть достигнуто, равно 400, и это произойдет только тогда, когда \ (y_1 \) и \ (y_2 \) равны нулю.

ШАГ 8. Зачитай свои ответы.

Теперь мы зачитываем наши ответы, то есть определяем базовое решение, связанное с окончательной симплексной таблицей. Опять же, мы смотрим на столбцы, в которых есть 1, а все остальные записи — нули. Поскольку столбцы с метками \ (y_1 \) и \ (y_2 \) не являются такими столбцами, мы произвольно выбираем \ (y_1 = 0 \) и \ (y_2 = 0 \), и получаем

\ [\ left [\ begin {array} {ccccc}
\ mathrm {x} _ {1} & \ mathrm {x} _ {2} & \ mathrm {Z} & | & \ mathrm {C} \\
0 & 1 & 0 & | & 8 \\
1 & 0 & 0 & | & 4 \\
0 & 0 & 1 & | & 400
\ end {array} \ right] \ nonumber \]

Матрица читает \ (x_1 = 4 \), \ (x_2 = 8 \) и \ (z = 400 \).

Окончательное решение гласит, что если Ники проработает 4 часа на Работе I и 8 часов на Работе II, она максимизирует свой доход до 400 долларов. Поскольку обе переменные Slack равны нулю, это означает, что она израсходовала бы все рабочее время, а также время на подготовку, и ничего не останется.

3.3a. Решение стандартных задач максимизации с помощью симплекс-метода

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

Для решения задач линейного программирования, содержащих более двух переменных, математики разработали то, что теперь известно как симплекс-метод
. Это эффективный алгоритм (набор механических шагов), который «переключает» угловые точки, пока не найдет ту, которая максимизирует целевую функцию.Хотя это заманчиво, есть несколько вещей, на которые нам нужно обратить внимание, прежде чем использовать его.

Прежде чем приступить к математическим деталям, давайте рассмотрим пример задачи линейного программирования, для которой
подходит для симплекс-метода:

Пример 1

С помощью симплекс-метода можно решить следующую систему:

Цель Функция: P = 2 x + 3 y + z

При соблюдении ограничений:

3 x + 2 y ≤ 5

2 x + y — z ≤ 13

z ≤ 4

х, у, z≥0

Стандартная задача максимизации

С математической точки зрения, чтобы использовать симплексный метод для решения задачи линейного программирования, нам нужна стандартная задача максимизации:

,
• — целевая функция, а
—
• одно или несколько ограничений в форме a ₁ x ₁ + a ₂ x ₂ +… a _n x le n В
  • Все числа a представляют собой действительные коэффициенты, а
  • x _число представляет соответствующие переменные.
  • V — неотрицательное (0 или большее) действительное число

Наличие ограничений с верхними пределами должно иметь смысл, поскольку при максимизации количества у нас, вероятно, есть ограничения на то, что мы можем сделать. Если бы у нас не было ограничений, мы могли бы продолжать увеличивать, скажем, прибыль, бесконечно! Это противоречит тому, что мы знаем о реальном мире.

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

Во-первых, матрицы плохо справляются с неравенством. Во-первых, у матрицы нет простого способа отслеживать направление неравенства. Уже одно это препятствует использованию неравенств в матрицах. Как же нам этого избежать?

Рассмотрим следующую задачу линейного программирования

Развернуть:

P = 7 x + 12 y

При условии:

2 x + 3 y ≤ 6

3 x + 7 y ≤12

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

2 x + 3 y + s ₁ = 6

3 x + 7 y + s ₂ = 12

Например, предположим, что
x = 1, y = 1, тогда

2 + 3 + s ₁ = 6 или s ₁ = 1

3 + 7 + s ₂ = 12 или s ₂ = 2

Важно отметить, что эти две переменные, s ₁ и s ₂ , не обязательно одинаковы.Они просто действуют на неравенство, подбирая «слабину», которая не дает левой стороне выглядеть как правая. Следовательно, мы называем их резервными переменными . Это устраняет неравенство за нас. Поскольку расширенные матрицы содержат все переменные слева и константы справа, мы перепишем целевую функцию в соответствии с этим форматом:

–7 x — 12 y + P = 0

Теперь мы можем написать исходную систему уравнений :

Для этого нам потребуется матрица, которая может обрабатывать x , y , s ₁ , s ₂ и P .Мы разместим это в таком порядке. Наконец, симплексный метод требует, чтобы целевая функция была указана в нижней строке матрицы, чтобы мы имели:

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

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

1. Выберите столбец поворота

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

Таким образом, наша точка поворота — это столбец и .

2. Выберите сводную строку

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

Сначала рассчитаем тестовые соотношения:

[латекс] \ displaystyle {\ left [\ matrix {{6 ÷ 3 = 2} \\ {12 ÷ 7≈1.7}} \ right]} [/ latex]

Поскольку тестовое соотношение для строки 2 меньше, мы выбираем ее в качестве сводной строки. Теперь значение в рамке называется нашей опорной точкой . Чтобы объяснить, почему мы это делаем, заметим, что 2 и 1.7 — это просто вертикальные пересечения двух неравенств. Мы выбираем меньшее, чтобы убедиться, что угловая точка находится в допустимой области:

3. Используя исключение Гаусса, удалите строки 1 и 3

Умножьте R2 на (1/7), чтобы преобразовать 7 в 1.

Затем используйте 1, чтобы удалить 3 в R1: -3R ₂ + R ₁ → R ₁

И используйте 1, чтобы удалить -12 в R3: 12R ₂ + R ₃ → R ₃

Получаем следующую матрицу (возможно, дроби)

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

[латекс] \ displaystyle {\ left [\ matrix {{5/7} & {0} & {1} & {- 3/7} & {0} & {|} {6/7} \\ {3 / 7} & {1} & {0} & {1/7} & {0} & {|} {12/7} \\ {- 13/7} & {0} & {0} & {12 / 7} & {1} & {|} {144/7}} \ right]} [/ latex]

[латекс] \ displaystyle {\ left [\ matrix {{(6/7) ÷ (5/7) ≈1.2} \\ {12 ÷ 3≈4}} \ right]} [/ latex]

Начиная с 1.2 <4, R1 - наша новая сводная строка.

Интересно, что это тестовое соотношение соответствует входному значению пересечения двух линий!

Аналогичным образом мы переходим к удалению всех неповоротных значений.

Умножьте R1 на (1 / 0,71), чтобы преобразовать 0,71 в 1.

Затем используйте 1, чтобы удалить 3 в R3: -3R ₁ + R ₂ → R ₂

И используйте 1, чтобы удалить -12 в R3: 1.86R ₁ + R ₃ → R ₃

Получаем следующую матрицу

[латекс] \ displaystyle {\ left [\ matrix {{1} & {0} & {7/5} & {- 3/5} & {0} & {|} {6/5} \\ {0 } & {1} & {- 3/5} & {2/5} & {0} & {|} {6/5} \\ {0} & {0} & {13/5} & {3 / 5} & {1} & {|} {114/5}} \ right]} [/ latex]

В строке целевой функции не осталось дополнительных отрицательных записей.Таким образом, мы имеем следующую матрицу:

[латекс] \ displaystyle {\ left [\ matrix {{1} & {0} & {7/5} & {- 3/5} & {0} & {|} {6/5} \\ {0 } & {1} & {- 3/5} & {2/5} & {0} & {|} {6/5} \\ {0} & {0} & {13/5} & {3 / 5} & {1} & {|} {114/5}} \ right]} [/ latex]

Таким образом, мы готовы читать решения.

4. Определите набор решений

Чтобы идентифицировать набор решений, мы сосредотачиваемся только на столбцах с ровно одной ненулевой записью — они называются базовыми переменными (столбцы с более чем одной ненулевой записью, таким образом, называются небазовыми переменными ) .

Мы замечаем, что оба столбца x any являются базовыми переменными. Нас действительно не волнуют переменные резервов, так же как мы игнорируем неравенство, когда находим пересечения. Теперь мы видим, что

[латекс] \ displaystyle {\ left [\ matrix {{1} & {0} & {7/5} & {- 3/5} & {0} & {|} {6/5} \\ {0 } & {1} & {- 3/5} & {2/5} & {0} & {|} {6/5} \\ {0} & {0} & {13/5} & {3 / 5} & {1} & {|} {114/5}} \ right]} [/ latex]

Установка переменных резерва на 0 дает:

x ≈ 1.2

y ≈ 1,2

P = 22,8

Таким образом, x = 1,2, y = 1,2, P = 22,8 — это решение задачи линейного программирования. То есть, входные данные x = 1,2 и y = 1,2 дадут максимальное значение целевой функции 22,8

  # Создать модель
model = LpProblem (name = "small-проблема", смысл = LpMaximize)
  

  # Инициализировать переменные решения
x = LpVariable (name = "x", lowBound = 0)
y = LpVariable (name = "y", lowBound = 0)
  

  >>> выражение = 2 * x + 4 * y
>>> тип (выражение)
<класс 'pulp.pulp.LpAffineExpression'>

>>> ограничение = 2 * x + 4 * y> = 8
>>> тип (ограничение)
<класс "мякоть.pulp.LpConstraint '>
  

  # Добавить ограничения в модель
модель + = (2 * x + y <= 20, "красное_ограничение")
модель + = (4 * x - 5 * y> = -10, "blue_constraint")
модель + = (-x + 2 * y> = -2, "желтое_ограничение")
модель + = (-x + 5 * y == 15, "зеленое_ограничение")
  

  # Добавить в модель целевую функцию
obj_func = х + 2 * у
модель + = obj_func
  

  # Добавить в модель целевую функцию
модель + = x + 2 * y
  

  # Добавить в модель целевую функцию
модель + = lpSum ([x, 2 * y])
  

  >>> модель
маленькая проблема:
МАКСИМАЛЬНО
1 * х + 2 * у + 0
ПРИ УСЛОВИИ
красное_ограничение: 2 x + y <= 20

blue_constraint: 4 x - 5 y> = -10

желтое_ограничение: - x + 2 y> = -2

зеленое_ограничение: - x + 5 y = 15

ПЕРЕМЕННЫЕ
x Непрерывный
y Непрерывный
  

  # Решаем проблему
status = model.solve ()
  

  >>> print (f "status: {model.status}, {LpStatus [model.status]}")
статус: 1, Оптимальный

>>> print (f "objective: {model.objective.value ()}")
цель: 16.8181817

>>> для var в model.variables ():
... print (f "{var.name}: {var.значение()}")
...
х: 7.7272727
y: 4.5454545

>>> для имени, ограничения в model.constraints.items ():
... print (f "{имя}: {constraint.value ()}")
...
красное_ограничение: -9.999999939e-08
blue_constraint: 18.181818300000003
желтое_ограничение: 3.3636362999999996
green_constraint: -2.0000000233721948e-07)
  

  >>> model.variables ()
[x, y]
>>> model.variables () [0] равно x
Правда
>>> model.variables () [1] равно y
Правда
  

  >>> model.solver
<объект pulp.apis.coin_api.PULP_CBC_CMD по адресу 0x7f60aea19e50>
  

  # Создать модель
model = LpProblem (name = "small-проблема", смысл = LpMaximize)

# Инициализировать переменные решения
x = LpVariable (name = "x", lowBound = 0)
y = LpVariable (name = "y", lowBound = 0)

# Добавляем ограничения в модель
модель + = (2 * x + y <= 20, "красное_ограничение")
модель + = (4 * x - 5 * y> = -10, "blue_constraint")
модель + = (-x + 2 * y> = -2, "желтое_ограничение")
модель + = (-x + 5 * y == 15, "зеленое_ограничение")

# Добавляем в модель целевую функцию
модель + = lpSum ([x, 2 * y])

# Решать проблему
статус = модель.решить (solver = GLPK (msg = False))
  

  >>> print (f "status: {model.status}, {LpStatus [model.статус]}")
статус: 1, Оптимальный

>>> print (f "objective: {model.objective.value ()}")
цель: 16.81817

>>> для var в model.variables ():
... print (f "{var.name}: {var.value ()}")
...
х: 7.72727
y: 4.54545

>>> для имени, ограничения в model.constraints.items ():
... print (f "{имя}: {constraint.value ()}")
...
красное_ограничение: -1.0000000000509601e-05
blue_constraint: 18.181830000000005
желтое_ограничение: 3.3636299999999997
зеленое_ограничение: -2.000000000279556e-05
  

  >>> model.solver
<объект pulp.apis.glpk_api.GLPK_CMD по адресу 0x7f60aeb04d50>
  

  # Создать модель
model = LpProblem (name = "small-проблема", смысл = LpMaximize)

# Инициализировать переменные решения: x - целое число, y - непрерывное
x = LpVariable (name = "x", lowBound = 0, cat = "Integer")
y = LpVariable (name = "y", lowBound = 0)

# Добавляем ограничения в модель
модель + = (2 * x + y <= 20, "красное_ограничение")
модель + = (4 * x - 5 * y> = -10, "blue_constraint")
модель + = (-x + 2 * y> = -2, "желтое_ограничение")
модель + = (-x + 5 * y == 15, "зеленое_ограничение")

# Добавляем в модель целевую функцию
модель + = lpSum ([x, 2 * y])

# Решать проблему
статус = модель.решать()
  

  >>> print (f "status: {model.status}, {LpStatus [model.status]}")
статус: 1, Оптимальный

>>> print (f "objective: {model.objective.value ()}")
цель: 15,8

>>> для var в model.variables ():
... print (f "{var.name}: {var.value ()}")
...
х: 7.0
y: 4.4

>>> для имени, ограничения в model.constraints.items ():
... print (f "{имя}: {ограничение.значение()}")
...
красное_ограничение: -1.5999999999999996
blue_constraint: 16.0
желтое_ограничение: 3.8000000000000007
green_constraint: 0,0)

>>> model.solver

  

  # Определить модель
model = LpProblem (name = "распределение ресурсов", смысл = LpMaximize)

# Определить переменные решения
x = {i: LpVariable (name = f "x {i}", lowBound = 0) для i в диапазоне (1, 5)}

# Добавить ограничения
модель + = (lpSum (x.values ​​()) <= 50, "рабочая сила")
модель + = (3 * x [1] + 2 * x [2] + x [3] <= 100, "material_a")
модель + = (x [2] + 2 * x [3] + 3 * x [4] <= 90, "material_b")

# Ставим цель
модель + = 20 * x [1] + 12 * x [2] + 40 * x [3] + 25 * x [4]

# Решаем проблему оптимизации
status = model.solve ()

# Получите результаты
print (f "status: {model.status}, {LpStatus [model.status]}")
print (f "objective: {model.objective.value ()}")

для var в x.values ​​():
    print (f "{var.name}: {var.value ()}")

для имени, ограничения в модели.constraints.items ():
    print (f "{имя}: {constraint.value ()}")
  

  статус: 1, Оптимальный
цель: 1900 г.0
x1: 5,0
х2: 0,0
x3: 45,0
x4: 0,0
рабочая сила: 0,0
material_a: -40.0
material_b: 0,0
  

  1model = LpProblem (name = "распределение ресурсов", смысл = LpMaximize)
 2
 3 # Определите переменные решения
 4x = {i: LpVariable (name = f "x {i}", lowBound = 0) для i в диапазоне (1, 5)}
 5y = {i: LpVariable (name = f "y {i}", cat = "Binary") для i в (1, 3)}
 6
 7 # Добавить ограничения
 8model + = (lpSum (x.values ​​()) <= 50, "рабочая сила")
 9модель + = (3 * x [1] + 2 * x [2] + x [3] <= 100, "material_a")
10модель + = (x [2] + 2 * x [3] + 3 * x [4] <= 90, "material_b")
11
12M = 100
13model + = (x [1] <= y [1] * M, "x1_constraint")
14model + = (x [3] <= y [3] * M, "x3_constraint")
15модель + = (y [1] + y [3] <= 1, "y_constraint")
16
17 # Установить цель
18модель + = 20 * x [1] + 12 * x [2] + 40 * x [3] + 25 * x [4]
19
20 # Решить проблему оптимизации
21status = model.solve ()
22
23print (f "status: {model.status}, {LpStatus [model.статус]}")
24print (f "objective: {model.objective.value ()}")
25
26 для var в model.variables ():
27 print (f "{var.name}: {var.value ()}")
28 год
29 для имени, ограничение в model.constraints.items ():
30 print (f "{name}: {constraint.value ()}")
  

  статус: 1, Оптимальный
цель: 1800.0
x1: 0,0
х2: 0,0
x3: 45,0
x4: 0,0
y1: 0,0
y3: 1.0
рабочая сила: -5.0
material_a: -55.0
material_b: 0,0
x1_constraint: 0.0
x3_constraint: -55.0
y_constraint: 0.0