183295 (Компьютерное математическое моделирование в экономике), страница 2

По условию требуется, чтобы его, по крайней мере, хватило

(7.77)

Точно то же и для остальных веществ. В целом

(I = 1, 2, …, m).

Эти условия определяют наличие минимума необходимых питательных веществ. Диета, для которой выполнены условия (7.78) - допустимая диета. Предположим, что из всех допустимых диет должна быть выбрана самая дешевая. Пусть _i - цена 1 кг продукта F_i. Полная стоимость диеты, очевидно,

(7.79)

Таким образом, мы пришли к задаче: найти неотрицательное решение ₁, ..., _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)

Неизвестные х₁, х₂, ..., х_r - базисные неизвестные, набор {х₁, х₂, ..., х_r} называется базисом, а остальные неизвестные {x_r+1, х_r+2, …, х_n} - свободные. Подставляя (7.86) в (7.81), выразим функцию f через свободные неизвестные:

(7.87)

Положим все свободные неизвестные равными нулю:

(7.88)

Найдем из системы (7.86) значения базисных неизвестных

(7.89)

Полученное таким образом допустимое решение

отвечает базису x₁, x₂, ..., х_r, т.е. является базисным решением. Допустим для определенности, что мы ищем минимум f. Теперь нужно отданного базиса перейти к другому с таким расчетом, чтобы значение линейной функции f при этом умень­шилось. Проследим идею симплекс-метода на примере.

Пример 1. Дана система ограничений

Требуется минимизировать линейную функцию f = х₂ – х₃. В качестве свободных переменных выберем х₂ и x₃. Тогда данная система ограничений преобразуется к виду

Таким образом, базисное решение (3, О, О, 1). Так как линейная функция уже запи­сана в свободных неизвестных, то ее значение для данного базисного решения f = 0. Для уменьшения этого значения можно уменьшить х₂ или увеличить х₃. Но х₂ в данном базисе равно нулю и потому его уменьшать нельзя. Попробуем увеличить x₃. Первое из уравнений имеет ограничение х₃ = 1 (из условия х₁ 0), второе - не дает ограничений. Далее, берем х₃= 1, х₂ не меняем и получаем новое допустимое решение (О, О, 1, 3), для которого f = 1 - уменьшилось. Найдем базис, которому соответствует это решение (он состоит, очевидно, из переменных x₃, х₄). От преды­дущей системы ограничений переходим к новой:

а форма в новых свободных переменных имеет вид

Теперь попробуем повторить предыдущую процедуру. Для уменьшения f надо уменьшить либо x_1, либо х₂, но это невозможно, так как в этом базисе

x₁ = О, х₂ = 0.

Таким образом, данное базисное решение является оптимальным, и min f= 1 при x₁ = О, х₂ = 0, х_з = 1, x₄ = 3.

Приведем алгоритм симплекс-метода в общем виде. Обычно все вычисления по симплекс-методу сводят в стандартные таблицы.

Запишем систему ограничений в виде

(7.90)

а функцию f

(7.91)

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

Данные о коэффициентах уравнений и линейной функции занесем в табл. 7.12.

Таблица 7.12

Симплекс-таблица

Сформулируем алгоритм симплекс-метода применительно к данным, внесенным в табл. 7.12.

1. Выяснить, имеются ли в последней строке таблицы положительные числа (γ₀ не принимается во внимание). Если все числа отрицательны, то процесс закончен; базисное решение (b₁, b₂, ..., b_r, 0, ..., 0) является оптимальным; соответствующее значение целевой функции f = γ₀. Если в последней строке имеются положительные числа, перейти к п. 2.