Экономико-математическое моделирование /
Матрица питательности
Питательное вещество Продукт
…
…
…
… … … … …
…
Предположим, что диетолог уже выбрал диету, т.е. определил, что человек дол¬жен за месяц потреблять 1 кг продукта F1,...,n кг продукта Fn. Полное количество питательного вещества N1 будет
По условию требуется, чтобы его, по крайней мере, хватило
(7.77)
Точно то же и для остальных веществ. В целом
(7.78)
Эти условия определяют наличие минимума необходимых питательных веществ. Диета, для которой выполнены условия (7.78) - допустимая диета. Предположим, что из всех допустимых диет должна быть выбрана самая дешевая. Пусть i - цена 1 кг продукта Fi. Полная стоимость диеты, очевидно,
(7.79)
Таким образом, мы пришли к задаче: найти неотрицательное решение 1, ..., n системы неравенств (7.78), минимизирующее выражение (7.79).
В примерах, приведенных выше, имеется нечто общее. Каждый из них требует нахождения наиболее выгодного варианта в определенной экономической ситуа¬ции. С чисто математической стороны в каждой задаче требуется найти значение нескольких неизвестных так, чтобы
1) все эти значения были неотрицательны;
2) удовлетворяли системе линейных уравнений или линейных неравенств;
3) при этих значениях некоторая линейная функция имела бы минимум (или мак¬симум). Таким образом, линейное программирование - это математическая дисцип¬лина, изучающая методы нахождения экстремального значения линейной функции нескольких переменных при условии, что последние удовлетворяют конечному числу линейных уравнений и неравенств. Запишем это с помощью формул: дана система линейных уравнений и неравенств.
Запишем это с помощью формул: дана система линейных уравнений и неравенств
(7.80)
и линейная функция
(7.81)
Требуется найти такое неотрицательное решение
(7.82)
системы (7.80), чтобы функция/принимала наименьшее (или наибольшее) значение.
Условия (7.80) называют ограничениями данной задачи, а функцию f- целевой функцией (или линейной формой). В приведенных выше примерах ограничения имели вид не уравнений, а неравенств. Заметим, что ограничения в виде неравенств, всегда можно свести к системе в виде равенств (способом введения добавочных неизвестных).
Так, для неравенства
(7.83)
вводя добавочное неизвестное хn+1, получаем
(7.84)
Потребовав его неотрицательности наряду с остальными неизвестными, получим, что условие хn+1 0 превращает (7.84) в (7.83). Введя по отдельному дополнитель¬ному неизвестному для каждого из неравенств, получим систему уравнений, равно¬сильную исходной системе неравенств.
Пример. Дана система неравенств
Сведем ее к системе уравнений. Получим
После оптимизации значениями дополнительных неизвестных следует пренебречь.
СИМПЛЕКС-МЕТОД
Для решения ряда задач линейного программирования существуют специальные методы. Есть, однако, общий метод решения всех таких задач. Он носит название симплекс-метода и состоит из алгоритма отыскания какого-нибудь произвольного допустимого решения и алгоритма последовательного перехода от этого решения к новому допустимому решению, для которого функция f изменяется в нужном направлении (для получения оптимального решения).
Пусть система ограничений состоит лишь из уравнений
(7.85)
и требуется отыскать минимум линейной функции (7.81). Для отыскания произ¬вольного опорного решения приведем (7.85) к виду, в котором некоторые r неиз¬вестных выражены через остальные, а свободные члены неотрицательны (как это сделать - обсудим позднее):
(7.86)
Неизвестные х1, х2, ..., хr - базисные неизвестные, набор {х1, х2, ..., хr} называется базисом, а остальные неизвестные {xr+1, хr+2, …, хn} - свободные. Подставляя (7.86) в (7.81), выразим функцию f через свободные неизвестные:
(7.87)
Положим все свободные неизвестные равными нулю:
(7.88)
Найдем из системы (7.86) значения базисных неизвестных
(7.89)
Полученное таким образом допустимое решение
отвечает базису x1, x2, ..., хr, т.е. является базисным решением. Допустим для определенности, что мы ищем минимум f. Теперь нужно отданного базиса перейти к другому с таким расчетом, чтобы значение линейной функции f при этом умень¬шилось. Проследим идею симплекс-метода на примере.
Пример 1. Дана система ограничений
Требуется минимизировать линейную функцию f = х2 – х3. В качестве свободных переменных выберем х2 и x3. Тогда данная система ограничений преобразуется к виду
Таким образом, базисное решение (3, О, О, 1). Так как линейная функция уже запи¬сана в свободных неизвестных, то ее значение для данного базисного решения f = 0. Для уменьшения этого значения можно уменьшить х2 или увеличить х3. Но х2 в данном базисе равно нулю и потому его уменьшать нельзя. Попробуем увеличить x3. Первое из уравнений имеет ограничение х3 = 1 (из условия х1 0), второе - не дает ограничений. Далее, берем х3= 1, х2 не меняем и получаем новое допустимое решение (О, О, 1, 3), для которого f = 1 - уменьшилось. Найдем базис, которому соответствует это решение (он состоит, очевидно, из переменных x3, х4). От преды¬дущей системы ограничений переходим к новой:
а форма в новых свободных переменных имеет вид
Теперь попробуем повторить предыдущую процедуру. Для уменьшения f надо уменьшить либо x1, либо х2, но это невозможно, так как в этом базисе
x1 = О, х2 = 0.
Таким образом, данное базисное решение является оптимальным, и min f= 1 при x1 = О, х2 = 0, хз = 1, x4 = 3.
Приведем алгоритм симплекс-метода в общем виде. Обычно все вычисления по симплекс-методу сводят в стандартные таблицы.
Запишем систему ограничений в виде
(7.90)
а функцию f
(7.91)
Тогда очередной шаг симплекс-процесса будет состоять в переходе от старого базиса к новому таким образом, чтобы значение линейной функции, по крайней мере, не увеличивалось.
Данные о коэффициентах уравнений и линейной функции занесем в табл. 7.12.
Таблица 7.12
Симплекс-таблица
Базис Св.чл.
…
…
…
…
1 … 0 … 0
…
…
… … … … … … … … … … … …
0 … 1 … 0
…
…
… … … … … … … … … … … …
0 … 0 … 1
…
…
0 … 0 … 0
…
…
Сформулируем алгоритм симплекс-метода применительно к данным, внесенным в табл. 7.12.
1. Выяснить, имеются ли в последней строке таблицы положительные числа (γ0 не принимается во внимание). Если все числа отрицательны, то процесс закончен; базисное решение (b1, b2, ..., br, 0, ..., 0) является оптимальным; соответствующее значение целевой функции f = γ0. Если в последней строке имеются положительные числа, перейти к п. 2.
2. Просмотреть столбец, соответствующий положительному числу из последней строки, и выяснить, имеются ли в нем положительные числа. Если ни в одном из таких столбцов положительных чисел нет, то оптимального решения не существует. Если найден столбец, содержащий хотя бы один положительный элемент (если таких столбцов несколько, взять любой из них), пометить этот столбец и перейти к п. 3.
3. Разделить свободные члены на соответствующие положительные числа из вы¬деленного столбца и выбрать наименьшее частное. Отметить строку таблицы, соответствующую наименьшему частному. Выделить разрешающий элемент, стоящий на пересечении отмеченных строки и столбца. Перейти к п. 4.
4. Разделить элементы выделенной строки исходной таблицы на разрешающий элемент (на месте разрешающего элемента появится единица). Полученная таким образом новая строка пишется на месте прежней в новой таблице. Перейти к п. 5.
5. Каждая следующая строка новой таблицы образуется сложением соответствующей строки исходной таблицы и строки, записанной в п. 4, которая предварительно умножается на такое число, чтобы в клетках выделенного