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

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

Под симплексным методом понимается последовательный переход от одного базисного нахождения системы решений к другому. Эта перестановка повторяется до тех пор, пока переменная величина цели не достигнет своего наибольшего или наименьшего значения. Такой подход является универсальным, его можно использовать для решения любой задачи последовательного программирования.
Метод был разработан в 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. Если в записи используется знак «меньше или равно», переменная используется положительная, в противном случае — отрицательная.
- В зависимости от количества вводимых значений все переменные принимаются за основные. Их необходимо выразить через неосновные и перейти к базовому решению.
- Через неосновные переменные выражается функция цели.
- Если при решении отыскивается ответ с максимумом или минимумом линейной формы и все неосновные переменные получаются только положительными, то задача считается выполненной.
- Если найденный максимум (минимум) линейной формы в функции имеет одну или несколько неосновных переменных с отрицательными коэффициентами, необходимо перейти к новому базисному решению.
- Из переменных, входящих в форму с отрицательными или положительными коэффициентами, выбирается наибольшая (по модулю) и переводится в основные.
Другими словами, указывается оптимальное опорное решение, способ перехода от одного нахождения ответа к другому, варианты улучшения расчётов. После нахождения первоначального решения с «единичным базисом» вычисляется оценка разложения векторов по базису и заполняется симплексная таблица.
В тех случаях, когда затруднительно найти первоначальный опорный план исходной задачи, используют метод с искусственным базисом. Это симплекс-метод с так называемой М-задачей (ММЭ), решаемый способом добавления к левой части системы уравнений искусственных единичных векторов. При этом новая матрица должна содержать группу единичных линейно-независимых векторов.
Двухфазный способ
Двойственный метод используется при анализе задач линейного программирования, записанного в форме основной задачи. При этом среди векторов, 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 и выполнить команду «Сервис/Поиск решения». Далее указать исходные данные, а после нажать кнопку «Выполнить».
Полученное решение можно представить в форме отчёта, содержащего:
- Результаты – содержит информацию об исходных и конечных значениях целевой и влияющих ячеек, дополнительные сведения об ограничениях.
- Устойчивость — отчёт, включающий данные о чувствительности решения к малым изменениям.
- Пределы – включают исходные и конечные значения, а также верхние и нижние границы значений, которые принимают влияющие ячейки при введённых ограничениях.
Онлайн-сервис для чайников
Метод решения относится к высшей математике, поэтому в нём довольно трудно разобраться даже подготовленному человеку, не говоря уже о чайнике. Существует некоторое количество сайтов с подробным онлайн-решением методом симплекса. На таких сервисах предлагается ввести количество переменных и строк (ограничений). А далее просто заполнить симплекс-таблицу и нажать расчёт. Причём при необходимости вводимые данные можно править, тем самым видеть, как изменяется результат от изменения исходной информации.

Удобным является ещё и то, что обычно на сайтах предлагается создать шаблон решения в Excel или Maple. Решаться любая задача будет почти мгновенно. Подробно можно выполнить расчёт онлайн-калькулятор по методу симплекса на следующих сайтах:
- «Семестр» (semestr.ru).
- «Мир математики» (matworld.ru).
- «Высшая математика» (math-pr.com).
- «Матзона» (mathzone.ru).
- «Контрольная работа» (kontrolnaya-rabota.ru).
Выполнить расчёт с помощью онлайн-сервисов сможет любой. При этом вероятность ошибки в ответе стремится к нулю. Тем более что для решения задачи даже необязательно знать принцип симплекс-метода.
Еще тесты
- Анатомия
- Английский язык
- Астрономия
- Биология
- Литература
- История
- Педсовет
- Естествознание
- Финансы и кредит
- Правоведение
- Товароведение
- Экономика
- Социология
- Маркетинг
- Обществознание
- Культурология
- Математика
- Философия
- Русский язык
- Психология
- Политология
- Делопроизводство
- Бухгалтерия
- ОБЖ
- Орфография
- География
- Биографии
- Физика
- Пунктуация
- Краткие содержания
- Химия
- Менеджмент
- Тест на тему Тест по теме Дыхательная система человека 7 вопросов
- Тест на тему Строение человека - анатомия внутренних органов 7 вопросов
- Тест на тему Гормоны - определение, виды, функции, роль в организме человека 5 вопросов
- Тест на тему Лейкоциты в крови - строение, где образуются и разрушаются, норма содержания 5 вопросов
- Тест на тему Одноклеточные организмы - строение , формы и признаки представителей 8 вопросов
- Тест на тему Бесполое размножение - виды, формы и биологическое значение процесса 9 вопросов
- Тест на тему Синтез АТФ - структура, функции и пути образования аденозинтрифосфорной кислоты 7 вопросов
- Тест на тему Биогеоценоз - определение, структура и свойства 5 вопросов
- Тест на тему Символизм в литературе - основные черты и представители направления 6 вопросов
- Тест на тему "У Лукоморья дуб зеленый" - анализ стихотворения Александра Сергеевича Пушкина 8 вопросов
- Тест на тему Родион Раскольников и Соня Мармеладова - история взаимоотношений в романе Ф. М. Достоевского "Преступление и наказание" 6 вопросов
- Тест на тему Семья Мелеховых в романе М. Шолохова "Тихий дон" 7 вопросов
- Тест на тему Отечественная война 1812 года - причины, основные сражения, итоги 7 вопросов
- Тест на тему Правление Ивана Грозного - внутренняя и внешняя политика 7 вопросов
- Тест на тему Образование СССР - причины, этапы становления, состав, итоги 6 вопросов
- Тест на тему Крещение руси князем Владимиром - причины, история, значение принятия христианства 6 вопросов
- Тест на тему Пищевая цепочка в природе - звенья, схемы и примеры цепей 5 вопросов
- Тест на тему Экологические факторы - классификация, примеры, общие закономерности воздействия 5 вопросов
- Тест на тему Биосфера - определение, состав, свойства, границы 5 вопросов
- Тест на тему Возникновение жизни на земле 6 вопросов
- Тест на тему Права и свободы человека и гражданина 5 вопросов
- Тест на тему Унитарное предприятие - виды, признаки, участники, особенности 7 вопросов
- Тест на тему Формы собственности - типы и виды и их характеристика 7 вопросов
- Тест на тему Предпринимательское право - понятие, принципы, предмет и объект, функции 5 вопросов
- Тест на тему Ликвидность предприятия - определение, виды, формула расчета 7 вопросов
- Тест на тему Процентная ставка - понятие, виды, методы расчета и начисления 5 вопросов
- Тест на тему Финансы - определние, сущность, основные функции, виды 7 вопросов
- Тест на тему Коммерческая деятельность - сущность и содержание 7 вопросов
- Тест на тему Статистическое наблюдение - виды, способы, последовательность этапов 6 вопросов
- Тест на тему Социальный контроль - понятие и функции, формы и методы, значение 5 вопросов
- Тест на тему Анкетирование - правила составления и виды вопросов, оформление результатов 5 вопросов
- Тест на тему Социальная группа — понятие, типы, критерии выделения 8 вопросов
- Тест на тему Деятельность человека - основные виды и характеристики 7 вопросов
- Тест на тему Воздушно-десантные войска (ВДВ) - история создания, подразделения, оснащение 7 вопросов
- Тест на тему Субъекты РФ - количество, виды, правовой статус 7 вопросов
- Тест на тему Социальные нормы - понятие, виды и характеристка, функции, примеры 6 вопросов
- Тест на тему Что такое угол 5 вопросов
- Тест на тему Деление в столбик — подробное описание алгоритма решения задач, примеры 10 вопросов
- Тест на тему Вычитание дробей - правила и примеры с решениями 5 вопросов
- Тест на тему Модуль числа - свойства, действия, как решать уравнения и неравенства с модулем 10 вопросов
- Тест на тему Ислам - история возникновения религии, основные положения 7 вопросов
- Тест на тему Мышление - определение, виды, функции, свойства 5 вопросов
- Тест на тему Что такое мораль, ее категории и функции 6 вопросов
- Тест на тему Буддизм - кратко о религии (история возникновения, основные положения, священные книги) 6 вопросов
- Тест на тему Безличные предложения в русском языке 8 вопросов
- Тест на тему Ударение в словах в русском языке - правила и проверка постановки 5 вопросов
- Тест на тему Морфемный разбор слова - правила выполнения с примерами 5 вопросов
- Тест на тему Сложноподчиненные предложения в русском языке 6 вопросов
- Тест на тему Мотивация - определение, виды и типы в психологии, менеджменте 5 вопросов
- Тест на тему Интеллект - понятие, признаки, как развивать, оценка 5 вопросов
- Тест на тему Социализация личности - понятие и сущность, агенты, примеры 5 вопросов
- Тест на тему Типы темперамента и их психологическая характеристика 5 вопросов
- Тест на тему Органы исполнительной власти РФ - понятие и правовой статус, структура и фунции 7 вопросов
- Тест на тему Европейский союз - история создания, цели, состав 5 вопросов
- Тест на тему Тоталитаризм - определение, характерные черты, плюсы и минусы идеологии 5 вопросов
- Тест на тему Политическая идеология - определение понятия, функции, классификация, особенности 5 вопросов
- Тест на тему Оборотные средства предприятия, их структура, учет и анализ 7 вопросов
- Тест на тему Бюджетная классификация - определение, структура 7 вопросов
- Тест на тему Калькуляция - основные понятия, примеры расчетов себестоимости 7 вопросов
- Тест на тему Бухгалтерский учет материально-производственных запасов на предприятии 8 вопросов
- Тест на тему Пистолет Макарова - шпаргалка по тактико-техническим характеристикам 9 вопросов
- Тест на тему Чрезвычайная ситуация - понятие, типы ЧС, причины возникновения, стадии развития 7 вопросов
- Тест на тему Вооруженные силы Российской Федерации — организационная структура и предназначение 7 вопросов
- Тест на тему ВМФ (Военно-Морской флот) России - структура, история, состав 7 вопросов
- Тест на тему Перу - географическое положение, климат и достопримечательности 9 вопросов
- Тест на тему Климатические пояса Земли - характеристика и особенности 8 вопросов
- Тест на тему Тайга - географическое положение, животный и растительный мир, особенности и характеристика природной зоны 7 вопросов
- Тест на тему Озеро - определение, классификация, признаки 6 вопросов
- Тест на тему Братья Гримм - биография, жизнь и творчество немецких писателей 10 вопросов
- Тест на тему Тамерлан (1336-1405) - биография, жизнь и завоевания великого полководца 10 вопросов
- Тест на тему Максим Горький (1868-1936) - биография, кратко самое важное, интересные факты из жизни писателя 9 вопросов
- Тест на тему Блок Александр Александрович (1880-1921) - биография, жизненный и творческий путь 11 вопросов
- Тест на тему "Ночь перед Рождеством" - краткое содержание повести Н. В. Гоголя 10 вопросов
- Тест на тему "Маленький Мук" - краткое содержание сказки Вильгельма Гауфа 10 вопросов
- Тест на тему "Дворянское гнездо" - краткое содержание романа И.С. Тургенева 8 вопросов
- Тест на тему "Бирюк" - краткое содержание рассказа И.С. Тургенева 10 вопросов
- Тест на тему Серная кислота - химические и физические свойства и реакции 8 вопросов
- Тест на тему Муравьиная кислота - формула, свойства, получение и применение 7 вопросов
- Тест на тему Сложные эфиры - характеристика, классификация и примеры соединений 8 вопросов
- Тест на тему Толуол - формула, свойства и применение химического вещества 8 вопросов
- Тест на тему Оценка персонала - виды, критерии и методы 7 вопросов
- Тест на тему Управление персоналом - задачи, функции, современные подходы 5 вопросов
- Тест на тему Менеджмент предприятий — сущность, виды, задачи и цели 7 вопросов
- Тест на тему Организационная структура предприятия — типы и предназначение 7 вопросов