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

Решение производственной задачи табличным симплекс-методом

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

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

Решение задачи табличным симплекс-методом

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

1. Определение исходных данных

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

Исходные данные для производственной задачи запишем в формате матриц :

• Матрица A — нормы времени на обработку изделий;
• Матрица B — фонд времени работы станков;
• Матрица C — продажи производимых изделий.

Таким образом, нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:

Фонд времени работы станков (мин.) задан в матрице B:

Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:

Кроме того, обозначим через X_i планируемое количество изделий каждого вида. Тогда искомый план: X₁, X₂, X₃, X₄.

2. Запись ограничений плана в виде системы неравенств

Запишем ограничения плана в виде системы неравенств:

Коэффициенты при переменных в левой части системы неравенств берем из матрицы A, значения из правой части — из матрицы B.

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

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

3. Определение целевого показателя

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

Тогда целевая прибыль может быть записана через следующее равенство:

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

4. Приведение системы неравенств к системе линейных уравнений

Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X₅, X₆, X₇).

Эти переменные являются фиктивными изделиями, на которые мы списываем неиспользованные остатки фондов времени работы станков.

5. Формирование опорного плана

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

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

6. Составление симплекс-таблицы

Занесем исходные данные в специальную симплекс-таблицу.

В столбец Базис выписываем дополнительные переменные (X₅..X₇). В колонку H вносим величины фонда времени работы станков. В столбцы X₁..X₇ помещаем коэффициенты при этих переменных из составленной ранее системы уравнений (если переменных в уравнении нет, как например, X₆ и X₇ в первом равенстве, то коэффициенты будут равны 0). Кроме того, следует предусмотреть дополнительный столбец (b) для показателя, который мы будем рассчитывать на следующем этапе.

Количество строк в таблице соответствует числу дополнительных переменных (X₅..X₇). В последнюю строку (c) заносим коэффициенты при целевой функции с обратным знаком (коэффициенты при дополнительных переменных X₅..X₇ будут нулевыми).

7. Вычисление показателя b

Выбираем в последней строке наибольшее (по модулю!) отрицательное число.

В нашем примере это -48 (еще раз подчеркнем, что отрицательные числа сравниваем без учета знака).

Далее вычислим для столбца, которому соответствует выбранное число, специальный показатель b_i = Н_i / a_i, где a_i — значение ячейки выбранного столбца и соответствующей строки.

8. Нахождение разрешающего элемента

Среди вычисленных значений b выбираем наименьшее.

Пересечение выбранных столбца и строки даст нам разрешающий элемент (РЭ). Меняем базисную переменную (из первой колонки в выбранной строке) на переменную соответствующую разрешающему элементу (X₅ на X₁).

9. Перерасчет элементов симплекс-таблицы

Теперь необходимо пересчитать все элементы симплекс-таблицы, кроме столбца b (который очищается).

При перерасчете элементов симплекс-таблицы следует придерживаться следующих правил:

• Сам разрешающий элемент (РЭ) обращается в единицу;
• Для элементов разрешающей строки применяется формула: a_ij * = a_ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные);
• Для элементов разрешающего столбца — они просто обнуляются;
• Остальные элементы таблицы пересчитываем по правилу прямоугольника:

Формула здесь следующая: a_ij * = a_ij — ( A × B / РЭ )

Как видите, мы берем пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A × B) делим на разрешающий элемент (РЭ) и вычитаем из текущей пересчитываемой ячейки (a_ij) то, что получилось. В итоге имеем новое значение — a_ij * .

Полученные в результате перерасчета значения заносим в новую симплекс-таблицу:

10. Проверяем последнюю строку симплекс-таблицы на наличие отрицательных чисел: если их нет — оптимальный план найден (п. 11), если есть — план требует улучшения (п. 7)

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

Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию (повторение) вычислений с пункта 7.

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

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

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

11. Определение производственного плана и вычисление общей прибыли

В соответствии с найденным планом (смотрим какие переменные перешли в колонку «Базис») выпускать мы будем изделия X₁ и X₂ (X₇ не учитываем, т. к. это фиктивное изделие, не производимое на предприятии и введенное для приведения системы неравенств к системе уравнений).

Прибыль от производства каждой единицы продукции нам известна (матрица C). Остается перемножить ее с найденными объемами выпуска изделий X₁ и X₂ (значения X₃ и X₄ нулевые, т. к. эти изделия производить оказалось невыгодно), для получения общей (максимально возможной!) прибыли.

Ответ План производства: X₁ = 32 шт., X₂ = 20 шт., X₃ = 0 шт., X₄ = 0 шт., общая прибыль: P = 48 × 32 + 33 × 20 = 2 196 руб.

1. Галяутдинов Р. Р. Курс лекций по логистике
2. Симплекс-метод // Википедия. URL: http://ru.wikipedia.org/wiki/Симплекс-метод (дата обращения: 25.11.2013)

© Копирование любых материалов статьи допустимо только при указании прямой индексируемой ссылки на источник: Галяутдинов Р.Р.

Источник

Метод симплекса для чайников — описание с примером подробного решения

Понятие и алгоритм

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

Метод был разработан в 1947 году математиком из США Бернардом Данцигом. Предложенный способ оказался весьма эффективным для решения задач, связанных с оптимизацией использования ограниченных ресурсов. То есть он позволяет оценить и откорректировать параметры системы, а также получить качественные аналитические результаты.

Существует два подхода решения задачи:

Первый можно использовать для оптимизационного решения двухмерных задач. Например, существует два производственных цикла по сборке ящиков. Выпуск товара характеризуется ограничением в поставках древесины и временем формовки изделия. Для одного необходимо 30 досок, а для другого — 40. Поставщики доставляют в неделю 2 тыс. единиц материала. Первый ящик собирается за 15 минут, а второй — за 30. Нужно определить, какое количество ящиков необходимо производить за неделю на первом конвейере и на втором. При этом первое изделие приносит 10 рублей прибыли, а второе — пять. Время изготовление ограничено 160 часами.

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

Это типовая двухмерная задача, условия неотрицательности которой определяются границами прямых: 30*Х1 + 4 0*Х 2 ≤ 2000 (для досок) и 20*Х 1 ≤ 50*Х 2 = 1600 (для сборки). Отложив по оси ординат Х1, а Х2 по абсцисс, и указав на них точки соответствующие уравнениям, можно будет подобрать оптимальное решение для использования сырья и времени.

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

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

Впервые способ был изложен Данцигом в книге «Линейное программирование, его обобщения и применения», изданной на русском языке в 1966 году. Эта теория основывалась на вычислительной процедуре и представлялась в виде стандартных алгебраических форм. Основное направление метода заключается в указании способа нахождения опорного решения, переходе к другому, более оптимальному расчёту и определении критериев, позволяющих остановить перебор опорных вариантов.

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

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

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

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

Двухфазный способ

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

Например, существует ограниченность, описываемая функцией:

F = C 1 X 1+ C 2 X 2+…+ CnXn. Используется условие, что Х1Р1+Х2Р2+…+Х(m +1) P (m +1)+ +… XnPn = Р0, где Х j больше либо равно 0 (j =1, n). Принимается, что среди чисел bi (i =1, m) имеются отрицательные.

Решением будет выражение: х= (b1; b2;…; bm ;0;…;0), однако этот ответ не будет разрешать задание, так как к нему могут относиться и отрицательные числа. Так как векторы Р1, Р2… Рм единичные, то каждый из них можно описать линейной областью, состоящей из них же. При этом коэффициентами разложения векторов Рj по области будут числа: Xij = aij (i =1, m; j =1, n) по модулю.

Выражение х= ( b1; b2;…; bm ;0;…;0) определяется базисом. Называют его псевдоплан. Считается, что если дельта j больше либо равна нулю, то для любого: j ( j =1, n ) по модулю. В то же время если в псевдоплане с находимым базисом существует хотя бы одно отрицательное число, то тогда задача вообще не будет иметь планов. Но когда для этих отрицательных чисел верно, что аij меньше нуля, то можно будет перейти к новому псевдоплану.

Объяснение псевдоплана помогает построить алгоритм двойственного метода. Если взять за основу х = (b1; b2;…; bm ;0;…;0) и представить это выражение псевдопланом, то, учитывая исходные данные, можно составить симплекс-таблицу. В ней часть элементов будет отрицательная. Так как дельта j должна быть больше либо равна нулю, то при отсутствии таких чисел в таблице уже будет записан оптимальный план. В обратном случае выбирается по модулю наибольшее из чисел с минусом.

Принцип решения задачи включает следующее:

• нахождение псевдоплана;
• проверка его на оптимальность;
• выбор разрешающей строки путём нахождения абсолютной величины отрицательного числа, отношения элементов (m+1) и соответствующей им строке;
• нахождение нового псевдоплана.

Если анализ оптимален, считается, что найдено верное решение. В другом случае устанавливается неразрешимость задачи либо составляется новый псевдоплан. Делается это в результате пересчёта табличных данных, например, методом Жордана-Гаусса.

Пример задачи

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

Задачи линейного программирования (ЗЛП) позволяют выбрать оптимальную загрузку при перемещении какого-либо товара из одних мест в другие. Во вводных данных указывается число пунктов отправления (м) и количество мест назначения (n). Первые обозначаются как А1, А2…Ам, а вторые – В1, В2…Вn. За аi принимается объём продукции на складе, а bi – потребность. Затраты на перевозку с i пункта в j обозначаются Сij.

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

Записываем уравнение ограничения. Сумма всего перевезённого песка с первого карьера должна быть меньше или равна 140. Поэтому можно записать: x11+x12+x12+x14+T1 = 140, где Т1 переменная для хранения остатка. Сумма ограничений будет записана как х11+х21+х31 =115. Аналогичные уравнения составляют и для оставшихся карьеров.

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

• A0 – последний столбец из матрицы;
• Сб – стоимость перевозок;
• Х11, Т3 – данные из полученной матрица.

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

Наибольшее число определяется пересечением ранее выбранных значений, на базе которых создают новый базис. После в соответствии с единичными базисами меняют Сб и Хб. Операцию повторяют до тех пор, пока не исчезнут все положительные числа из последней строки. Заполняют новую таблицу.

Расчёт в Excel

Для включения пакета анализа в программе необходимо перейти в раздел «Параметры» и выбрать строчку «Перейти». В новом окне найти строчку «Пакет анализа», кликнуть по ней и нажать кнопку ОК.

Затем понадобится загрузить и открыть шаблон для проверки в Excel. Используя манипулятор типа «мышь» или клавиатуру, выбрать ячейку G4 и выполнить команду «Сервис/Поиск решения». Далее указать исходные данные, а после нажать кнопку «Выполнить».

Полученное решение можно представить в форме отчёта, содержащего:

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

Онлайн-сервис для чайников

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

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

1. «Семестр» (semestr.ru).
2. «Мир математики» (matworld.ru).
3. «Высшая математика» (math-pr.com).
4. «Матзона» (mathzone.ru).
5. «Контрольная работа» (kontrolnaya-rabota.ru).

Выполнить расчёт с помощью онлайн-сервисов сможет любой. При этом вероятность ошибки в ответе стремится к нулю. Тем более что для решения задачи даже необязательно знать принцип симплекс-метода.

Источник