Основным алгоритмом решения ЗЛП является симплекс-метод. Его можно применять в случае, если задача оптимизации записана в специальном каноническом виде. При этом все ограничения имеют вид равенств и каждая базисная переменная встречается с коэффициентом 1 только в одном уравнении, а в других коэффициент при базисной переменной равен 0. Аналитическое выражение для целевой функции не должно содержать базисных переменных, а выражаться только через свободные переменные. Если при этом b i ≥ 0, то говорят о допустимом каноническом виде.
Суть симплекс-метода заключается в направленном переборе вершин ОДР с целью определения координат такой вершины, в которой целевая функция достигает экстремума. Введем несколько определений.
Опорным решением системы ограничений называется такое решение, когда для системы ограничений в допустимом каноническом виде все свободные переменные равны нулю.
Вырожденное опорное решение опорное решение, в котором одна или несколько базисных переменных равны нулю.
Допустимое опорное решение опорное решение, в котором все базисные переменные ≥ 0.
Оптимальное решение ЗЛП будет соответствовать одному из допустимых опорных решений. В симплекс-методе, начиная с допустимого опорного решения, расположенного в вершине многогранника ОДР, переходят к соседней вершине, сохраняя допустимость решения.
Для удобства формулировки правил метода запишем допустимую каноническую форму ЗЛП в ином виде, называемом стандартной формой. Например:
Для упрощения реализации симплекс-метода на ЭВМ его представляют в табличной форме. В этом случае каждое опорное решение соответствует новой симплекс-таблице. Каждая строка таблицы соответствует либо строке целевой функции, либо строке одного из ограничений. Пример таблицы для случая семи переменных для стандартной формы записи приведен ниже.
|
В симплекс-таблице вводится понятие разрешающего элемента элемента, лежащего на пересечении разрешающего столбца (соответствующего новой базисной переменной) и разрешающей строки (соответствующей новой свободной переменной) при процедуре замены базиса. Замена базиса необходима для перехода к следующему опорному решению. |
В симплекс-методе требуется иметь исходное допустимое опорное решение. Иногда такое решение получить легко. Например, если существует ограничение вида с положительной правой частью, то дополнительные переменные, используемые при записи ограничений в виде равенств, образуют допустимое опорное решение, в котором все переменные проектирования равны нулю, а дополнительные переменные являются базисными. Однако во многих задачах существуют ограничения вида0 и = 0, для которых начальное опорное решение может быть недопустимым. Поэтому применению симплекс-метода в общем случае должен предшествовать этап поиска допустимого решения. Рассмотрим один из вариантов алгоритма симплекс-метода с учетом этапа поиска допустимого решения.
Алгоритм симплекс-метода
1-й этап: нахождение допустимого опорного решения.
Шаг 1. Ограничения неравенства приводятся к виду ограничений ра-венств. Задача записывается в стандартной форме.
Шаг 2. Для каждого ограничения, имеющего отрицательный свободный член, просматриваются знаки коэффициентов при свободных переменных. Если отсутствует хотя бы один отрицательный коэффициент, то ограничения несовместны. Если во всех ограничениях свободные члены неотрицательны, то опорное решение является допустимым и необходимо переходить ко второму этапу (этапу нахождения оптимального решения).
Шаг 3. Для ограничения, имеющего отрицательный свободный член, выбирается свободная переменная с отрицательным коэффициентом. Эта переменная будет новой базисной переменной. Если отрицательных коэффициентов более одного, то в качестве новой базисной переменной можно выбрать любую, имеющую отрицательный коэффициент (выбор переменной в этом случае скажется на числе замен базиса, но не на конечном результате). Пусть это будет переменнаяx l . Если ограничений с отрицательным свободным членом более одного, то можно для анализа коэффициентов выбрать любое.
Шаг 4. Для выбора новой свободной переменной рассматривается отношениеb j /a jl для всех ограничений, причемb j иa jl должны иметь одинаковый знак. Находится минимальное отношение. Новой свободной переменной будет та базисная переменная, для ограничения которой отношениеb j /a jl оказалось минимальным. В этом случае разрешающий элемент таблицы будет находиться на пересечении столбца, соответствующего переменнойx l и строки, соответствующей ограничению, для которого получено минимальное отношение.
Шаг 5. Делается замена базиса. Для пересчета значений элементов симплекс-таблицы после смены базиса введем в таблицу следующие обозначения:
|
С учетом введенных обозначений после смены базиса все элементы таблицы могут быть пересчитаны по следующим выражениям с учетом того, что rp разрешающий элемент (r, q строка,p, s столбец). |
при q=r; s=p,
номер итерации(смены базиса);
при q=r
;sp
, s=
;
при q
r;s=p
;q=
;
для остальных
элементов.
Шаг 6. Возвращаемся на шаг 2.
2-й этап: нахождение оптимального решения.
Шаг 1. Проверяется признак оптимальности решения.
Признаки оптимального решения:
а) целевая функция будет иметь максимальное значение в том случае, когда в строке (выражении) целевой функции в стандартной форме записи все коэффициенты при свободных переменных положительны (свободный член не рассматривается);
б) целевая функция будет иметь минимальное значение в том случае, если в строке целевой функции в стандартной форме все коэффициенты при свободных переменных отрицательны;
в) если в выражении целевой функции в стандартной форме все коэффициенты при переменных одного знака и при этом есть хотя бы один нулевой коэффициент, то полученное решение является альтернативным, т. е. будет другой набор переменных, доставляющих целевой функции такое же значение.
Если признак оптимальности выполняется, то решение найдено. Значения свободных переменных равны нулю, значения базисных переменных равны свободным членам соответствующих ограничений, значение целевой функции равно свободному члену целевой функции. Если признак оптимальности не выполняется, то переходим к шагу 2.
Шаг 2. В соответствии с правилом выбора новой базисной переменной одну из свободных переменных переводим в базисные.
Правило выбора свободной переменной, переводимой в базис
При поиске максимума (минимума) функции, записанной в стандартной форме, в базис должна переводиться переменная, имеющая отрицательный (положительный) коэффициент в выражении целевой функции в стандартной форме. Если имеется более одного отрицательного (положительного) коэффициента c j , то выбирают переменную, имеющую больший по абсолютной величине отрицательный (положительный) коэффициентc j .
Шаг 3. В соответствии с правилом выбора переменной, переводимой из базисной в свободные, определяем новую свободную переменную.
Сформулируем правило выбора переменной, переводимой из базисных в свободные.
Для выбора новой
свободной переменной x
i
необходимо рассмотреть отношениеb
j
/a
ij
для всех ограничений
(
),
(
),
из этих отношений выбрать минимальное,
а в качестве новой свободной переменной
выбирать базисную переменную, для
ограничения которой получено минимальное
отношениеb
j
/a
ij
.
Отношениеb
j
/a
ij
необходимо рассматривать только для
положительныхa
ij
. Если
минимум достигается более чем для одного
индексаj
, то из базиса исключается
любая из переменных, соответствующих
j
-м ограничениям.
Если ни один из a ij не является положительным, то получение нового допустимого решения невозможно, т.е. при поиске минимума целевая функция не ограничена снизу, а при поиске максимумане ограничена сверху (признак неограниченности целевой функции ).
Шаг 4. Осуществляется замена базиса аналогично шагу 5 первого этапа.
Шаг 5. Переходим к шагу 1.
Пример 2. Найтипри ограничениях
|
|
Введем дополнительные переменные и перейдем в ограничениях к знакам “=”. |
|
;
;
,
.Запишем задачу в стандартной форме и представим ее в виде симплекс-таблицы:
|
|
|
Признак несовместности ограничений не выполняется. Допустимое решение не найдено, так как свободный член для ограничения x 5 равен5. Для получения допустимого решения произведем смену базиса. В качестве разрешающего столбца выберемx 1 ; разрешающей строки –x 6 (так как 2/1 <5/2). Разрешающий элемент подчеркнут. Строим новую симплекс-таблицу.
| |||||||||||||||||||||||||||
Понравилось? Добавьте в закладки
Решение задач симплекс-методом: примеры онлайн
Задача 1. Компания производит полки для ванных комнат двух размеров - А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В - 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В - 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В - 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?
Задача 2.
Решить задачу линейного программирования симплекс-методом.
Задача 3. Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.
- Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
- Определить статус каждого вида сырья и его удельную ценность.
- Определить максимальный интервал изменения запасов каждого вида сырья, в пределах которого структура оптимального плана, т.е. номенклатура выпуска, не изменится.
- Определить количество выпускаемой продукции и прибыль от выпуска при увеличении запаса одного из дефицитных видов сырья до максимально возможной (в пределах данной номенклатуры выпуска) величины.
- Определить интервалы изменения прибыли от единицы продукции каждого вида, при которых полученный оптимальный план не изменится.
Задача 4.
Решить задачу линейного программирования симплексным методом:
Задача 5.
Решить задачу линейного программирования симплекс-методом:
Задача 6.
Решить задачу симплекс-методом, рассматривая в качестве начального опорного плана, план, приведенный в условии:
Задача 7.
Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.
Задача 8.
Найти оптимальное решение двойственным симплекс-методом
Один из методов решения оптимизационных задач (как правило связанных с нахождением минимума или максимума ) линейного программирования называется . Симплекс-метод включает в себя целую группу алгоритмов и способов решения задач линейного программирования. Один из таких способов, предусматривающий запись исходных данных и их пересчет в специальной таблице, носит наименование табличного симплекс-метода .
Рассмотрим алгоритм табличного симплекс-метода на примере решения производственной задачи , которая сводится к нахождению производственного плана обеспечивающего максимальную прибыль.
Исходные данные задачи на симплекс-метод
Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.
Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:
Фонд времени работы станков (мин.) задан в матрице B:
Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:
Цель производственной задачи
Составить такой план производства, при котором прибыль предприятия будет максимальной.
Решение задачи табличным симплекс-методом
(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )
(2) Запишем ограничения плана в виде системы уравнений:
(3) Тогда целевая прибыль:
То есть прибыль от выполнения производственного плана должна быть максимальной.
(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).
(5) Примем следующий опорный план :
X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80
(6) Занесем данные в симплекс-таблицу :
В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;
(7) Выбираем в последней строке наибольшее (по модулю ) отрицательное число.
Вычислим b = Н / Элементы_выбранного_столбца
Среди вычисленных значений b выбираем наименьшее .
Пересечение выбранных столбца и строки даст нам разрешающий элемент. Меняем базис на переменную соответствующую разрешающему элементу (X5 на X1 ).
- Сам разрешающий элемент обращается в 1.
- Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
- Для элементов разрешающего столбца – они просто обнуляются.
- Остальные элементы таблицы пересчитываем по правилу прямоугольника.
a ij (*) = a ij – (A * B / РЭ)
Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .
(9) Вновь проверяем последнюю строку (c ) на наличие отрицательных чисел . Если их нет – оптимальный план найден, переходим к последнему этапу решения задачи. Если есть – план еще не оптимален, и симплекс-таблицу вновь нужно пересчитать.
Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.
(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.
ОТВЕТ:
X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.
P = 48 * 32 + 33 * 20 = 2 196 руб.
Галяутдинов Р.Р.
© Копирование материала допустимо только при указании прямой гиперссылки на
Краткая теория
Для решения задач линейного программирования предложено немало различных методов. Однако наиболее эффективным и универсальным среди них оказался симплекс-метод. При этом следует отметить, что при решении некоторых задач могут оказаться более эффективными другие методы. Например, при ЗЛП с двумя переменными оптимальным является , а при решении - метод потенциалов. Симплекс-метод является основным и применимым к любой ЗПЛ в канонической форме.
В связи с основной теоремой линейного программирования естественно возникает мысль о следующем пути решения ЗЛП с любым числом переменных. Найти каким-нибудь способом все крайние точки многогранника планов (их не больше, чем ) и сравнить в них значения целевой функции. Такой путь решения даже с относительно небольшим числом переменных и ограничений практически неосуществим, так как процесс отыскания крайних точек сравним по трудности с решением исходной задачи, к тому же число крайних точек многогранника планов может оказаться весьма большим. В связи с этими трудностями возникла задача рационального перебора крайних точек.
Суть симплексного метода в следующем. Если известны какая-нибудь крайняя точка и значение в ней целевой функции, то все крайние точки, в которых целевая функция принимает худшее значение, заведомо не нужны. Отсюда естественно стремление найти способ перехода от данной крайней точки к смежной по ребру лучшей, от нее к еще лучшей (не худшей) и т. д. Для этого нужно иметь признак того, что лучших крайних точек, чем данная крайняя точка, вообще нет. В этом и состоит общая идея наиболее широко применяемого в настоящее время симплексного метода (метода последовательного улучшения плана) для решения ЗЛП. Итак, в алгебраических терминах симплексный метод предполагает:
- умение находить начальный опорный план;
- наличие признака оптимальности опорного плана;
- умение переходить к нехудшему опорному плану.
Пример решения задачи
Условие задачи
Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве , , , единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве единиц, ресурса второго вида в количестве единиц, ресурса третьего вида в количестве единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве , единиц, ресурсов второго вида в количестве , единиц, ресурсов третьего вида в количестве , единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно , , тыс. руб.
- Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
- К прямой задаче планирования товарооборота, решаемой симплексным методом, составить двойственную задачу линейного программирования.
- Установить сопряженные пары переменных прямой и двойственной задач.
- Согласно сопряженным парам переменных из решения прямой задачи получить решение двойственной задачи, в которой производится оценка ресурсов, затраченных на продажу товаров.
Если ваш допуск к сессии зависит от решения блока задач, а у вас нет ни времени, ни желания садиться за расчёты – используйте возможности сайта сайт. Заказ задач – дело нескольких минут. Подробно (как оставить заявку, цены, сроки, способы оплаты) можно почитать на странице Купить решение задач по линейному программированию...
Решение задачи
Построение модели
Через обозначим товарооборот 1-го, 2-го и третьего вида товаров соответственно.
Тогда целевая функция, выражающая получаемую прибыль:
Ограничения по материально-денежным ресурсам:
Кроме того, по смыслу задачи
Получаем следующую задачу линейного программирования:
Приведение к каноническому виду ЗЛП
Приведем задачу к каноническому виду. Для преобразования неравенств в равенства введем дополнительные переменные . Переменные входят в ограничения с коэффициентом 1. В целевую функцию все дополнительные переменные введем с коэффициентом, равным нулю.
Ограничение имеет предпочтительный вид, если при неотрицательности правой части левая часть имеет переменную, входящую с коэффициентом, равным единице, а остальные ограничения-равенства - с коэффициентом, равным нулю. В нашем случае 1-е, 2-е, 3-е ограничения имеют предпочтительный вид с соответствующими базисными переменными .
Решение симплекс-методом
Заполняем симплексную таблицу 0-й итерации.
| БП |
Симплексные отношения |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.
Переход к следующей итерации осуществляем следующим образом:
Ведущий столбец соответствует .
Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е.7.
Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .
В новой таблице на месте разрешающего элемента пишем 1, все остальные элементы ключевого столбца –нули. Элементы ключевой строки делятся на разрешающий элемент. Все остальные элементы таблицы вычисляются по правилу прямоугольника.
Получаем таблицу 1-й итерации:
| БП |
Симплексные отношения |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
Ключевой столбец для 1-й итерации соответствует .
Находим ключевую строку, для этого определяем:
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 31/7.
Вектор выводим из базиса и вводим вектор .
Получаем таблицу 2-й итерации:
| БП |
Симплексные отношения |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
Таким образом, необходимо продавать 7,1 тыс.р. товара 1-го вида и 45,2 тыс.р. товара 3-го вида. Товар 2-го вида продавать невыгодно. При этом прибыль будет максимальна и составит 237,4 тыс.р. При реализации оптимального плана остаток ресурса 3-го вида составит 701 ед.
Двойственная задача ЛП
Запишем модель двойственной задачи.
Для построения двойственной задачи необходимо пользоваться следующими правилами:
1) если прямая задача решается на максимум, то двойственная - на минимум, и наоборот;
2) в задаче на максимум ограничения-неравенства имеют смысл ≤, а в задаче минимизации - смысл ≥;
3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;
4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;
5) свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот;
6) если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство;
7) если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.
Транспонируем матрицу исходной задачи:
Приведем задачу к каноническому виду. Введем дополнительные переменные. В целевую функцию все дополнительные переменные введем с коэффициентом, равным нулю. Дополнительные переменные прибавим к левым частям ограничений, не имеющих предпочтительного вида, и получим равенства.
Решение двойственной задачи ЛП
Соответствие между переменными исходной и двойственной задачи:
На основании симплексной таблицы получено следующее решение двойственной задачи линейного программирования (выписываем из нижней строки):
Таким образом, наиболее дефицитным
является ресурс первого вида. Его оценка максимальна и равна
. Ресурс третьего вида является избыточным -его
двойственная оценка равна нулю
. Каждая дополнительно проданная единица товара 2-й
группы будет снижать оптимальную прибыль на
Рассмотрен графический метод решения задачи линейного программирования (ЗЛП) с двумя переменными. На примере задачи приведено подробное описание построения чертежа и нахождения решения.
Решение транспортной задачи
Подробно рассмотрена транспортная задача, ее математическая модель и методы решения - нахождение опорного плана методом минимального элемента и поиск оптимального решения методом потенциалов.
Принятие решений в условиях неопределенности
Рассмотрено решение статистической матричной игры в условиях неопределенности с помощью критериев Вальда, Сэвиджа, Гурвица, Лапласа, Байеса. На примере задачи подробно показано построение платежной матрицы и матрицы рисков.
