Задача о диете симплекс методом пример

Решение задач линейного программирования, связанных с минимизацией целевой функции, имеет некоторые особенности, которые мы рассмотрим здесь на примере задачи об оптимальной диете. Пусть в некоторой упрощённой ситуации фермеру-животноводу необходимо спланировать закупку кормов, и при этом на рынке имеется два вида подходящих ему кормов и по цене соответственно 3 и 4 денежные единицы за единицу веса. Фермер проконсультировался со специалистом по питанию животных и получил следующие рекомендации: в сутки каждое животное должно получать не менее 5 единиц углеводов, 3 единиц белков и 4 единиц витаминов (в некоторых соответствующих единицах). После этого фермер изучил состав питательных веществ кормов и , и выписал результат в виде таблицы (в тех же единицах):

Перед фермером возникла задача: в каком объёме закупать корма и , чтобы реализовать рекомендации специалиста и при этом потратить минимум денег?

Экономическое описание задачи у нас имеется, составим математическую модель. Обозначим ( , ) – объёмы закупок кормов и в сутки на каждое животное. Аналогично предыдущему разделу мы получаем задачу линейного программирования: найти пару чисел ( , ), удовлетворяющую ограничениям

(5.1)

и минимизирующую целевую функцию

. (5.2)

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

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

Итак, вначале мы заменяем все неравенства равенствами (теперь нам надо вычитать переменные, т.к. знак неравенств – другой):

(5.3)

, ,

Тем самым, от задачи (5.1)-(5.2) мы переходим к равносильной ей задаче (5.3)-(5.2).

Начинаем аналогичные шаги нашей игры. Выражение базисных переменных , , первого шага через свободные , будет следующим:

(5.4)

Значит, базисное решение на первом шаге имеет вид (0, 0, -5, -3, -4) и не является допустимым!Не имеет никакого смысла вычислять значение целевой функции на нём и рассуждать, можно ли его улучшить (как мы это делали раньше). Для начала нам нужно добиться, чтобы базисное решение стало допустимым, т.е. чтобы все его компоненты стали неотрицательными. Из рассмотрения правых частей (5.4) ясно, что для этого можно увеличивать или (или оба одновременно, но мы опять будем изменять лишь одну переменную). В данном случае имеет смысл увеличивать , т.к. коэффициент при в целевой функции (5.2) меньше (не будем забывать, что в нынешнем примере мы минимизируем целевую функцию). Итак, пусть и . Тогда условия допустимости примут вид . Естественно, мы возьмём самое наименьшее из возможных значений = . Далее становится новой базисной переменной, а на замену ей выходит переменная (значение 4 возникло из уравнения для в (5.4)). Итак, базисные переменные второго шага – , , ; а свободные переменные – , . Выражаем базисные переменные через свободные (сначала − из последнего равенства в (5.4), а затем подставляем в остальные равенства этой системы):

(5.5)

И вот уже базисное решение второго шага получается допустимым – (4, 0, 7, 1, 0), и мы можем изучать его на оптимальность. Для этого выразим целевую функцию через свободные переменные второго шага (подставив в (5.2) выражение для из первого уравнения системы (5.5)):

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

У нас сейчас имеется коэффициент (-2) при , поэтому положим и =0. Аналогично изложенному выше, мы, с одной стороны, стремимся как можно сильнее увеличить (тем самым, как можно сильнее уменьшить Z ), но, с другой, нас ограничивают условия допустимости . Значит, берём .

Опуская детали, укажем, что на следующем шаге имеем следующее выражение базисных переменных этого шага , , через свободные переменные , :

При этом выражение для целевой функции будет таким: . Теперь очевидно, что базисное решение (2, 1, 2, 0, 0) даёт самое наименьшее возможное значение целевой функции . (В самом деле, для данного базисного решения и любое его изменение означает изменение , в сторону увеличения (т.к. они неотрицательны!) и увеличение целевой функции .) Окончательно, в исходной формулировке решение даёт пара чисел ; таким образом, нашему фермеру целесообразно закупать ежесуточно для каждого животного две единицы веса корма и одну единицу веса корма . Задача решена.

Раздел 6

Двойственная задача линейного программирования на примере задачи торга

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

Представим себе, что на календаре – 90-е годы, экономический кризис; и представим некоторую фирму, оптом скупающую у предприятий сырье с целью выгодной перепродажи за границу. И вот её представители начинают переговоры с рассматриваемым нами заводом. Их цель: скупить (по возможности дёшево) всё наше сырьё. Мы также отстаиваем свою выгоду. Начинается торг. Пусть − обсуждаемые цены за единицу сырья , , . Пусть на наших складах хранится запас сырья на месяц, и переговоры ведутся именно об этих объёмах. Тогда, с учётом запаса сырья в расчёте на одни сутки, мы получаем, что цель фирмы-перекупщика в ходе торга – это

(6.1)

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

Отсюда видно, что если мы используем 1 ед. сырья , 1 ед. сырья и 2 ед. сырья в производстве (одной единицы продукции , разумеется), то получим прибыль в 2 денежные единицы (по условию). Значит, перекупщик должен предложить нам не меньше за всё это сырьё, т.е. мы потребуем, чтобы выполнялось неравенство . Аналогично, рассматривая выгодность сделки по отношению к второму виду продукции, получаем неравенство . (Очевидно, что равенства нас устраивают, т.к. мы получаем ту же самую прибыль безо всяких усилий!). Итак, в совокупности наши условия на переговорах имеют вид:

(6.2)

Задача линейного программирования (6.1)-(6.2) называется, по определению, двойственной по отношению к исходной задаче (2.1)-(2.2) из раздела 2.

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

(6.3)

Сравнивая данную таблицу с формулировками задач (2.1)-(2.2) и (6.1)-(6.2), мы видим, что в исходной задаче ограничения и целевая функция записываются «по строкам», а в двойственной – «по столбцам». При этом в исходной задаче все ограничения – неравенства « » и целевая функция максимизируется, а в двойственной задаче все ограничения – « » и целевая функция минимизируется. Ясно, что исходная задача однозначно восстанавливается по двойственной. Таким образом, имеются естественные пары взаимно-двойственных задач.

Раздел 7

Пролог

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

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

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

Определение:

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

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

§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$s_i$inline$ по номеру неравенства, в которое мы его добавили.

Замечание:

$inline$s_i$inline$ ≥0.

§3. Угловые точки. Базисные/свободные переменные. Базисные решения

Определение:

Точка $inline$Х ∈ D$inline$ называется угловой точкой, если представление$inline$ Х= αХ^1+ (1-α) Х^2,где Х^1,Х^2 ∈D;0< α<1 $inline$ возможно только при $inline$Х^1=Х^2 $inline$.

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

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

Определение:

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

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

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

Необходимые условия для применения симплекс-метода:

1. Задача должна иметь каноническую форму.
2. У задачи должен быть явно выделенный базис.

Определение:

Явно выделенным базисом будем называть вектора вида:$inline$(..0100..)^T, (..010..)^T,(..0010..)^T…$inline$, т.е. только одна координата вектора ненулевая и равна 1.

Замечание:

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

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

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

Замечание:

Базис – переменные, коэффициенты в матрице ограничений при которых образуют базисные вектора.

Замечание:

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

Замечание:

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

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

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

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

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

Замечание:

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

Определение:

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

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

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

Определение:

Такая строка называется ведущей строкой и отвечает переменной, которую нужно вывести из базиса.

Замечание:

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

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

Определение:

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

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

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

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

Замечание:

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

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

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

1. Оптимальность

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

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

2. Неограниченность функционала

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

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

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

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

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

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

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

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

Эпилог

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

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

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

P.S.

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