Компьютерное математическое моделирование в экономике (стр. 2 из 4)

(7.74)

Второе условие примет вид

(7.75)

Раз стоимость перевозки одной тонны из Р_i, в Q_J равна с_i_j, то общая стоимость S всех перевозок равна

(7.76)

Таким образом, мы приходим к следующей чисто математической задаче: дана система m+k линейных алгебраических уравнений (7.74) и (7.75) с m·k неизвестными (обычно m·k » m+k) и линейная функция S. Требуется среди всех неотрицательных решений данной системы найти такое, при котором функция S достигает наименьшего значения (минимизируется).

Практическое значение этой задачи огромно, ее умелое решение в масштабах нашей страны могло бы экономить ежегодно огромные средства.

Пример 3. Задача о диете. Пусть у врача-диетолога имеется n различных продуктов F₁, F₂, ..., F_n, из которых надо составить диету с учетом их питательности. Пусть для нормального питания человеку необходимо m

веществ N₁, N₂, …, N_m. Предположим, что за месяц каждому человеку необходимо g₁ кг вещества N₁, g₂ кг вещества N₂, ..., g_m кг вещества N_m. Для составления диеты необходимо знать содержание питательных веществ в каждом продукте. Обозначим через a_ij количество i-го питательного вещества, содержащегося в одном килограмме j-го продукта. Всю эту информацию представляют в виде, так называемой, матрицы питательности (табл. 7.11).

Таблица 7.11

Матрица питательности

Питательное вещество	Продукт
Питательное вещество			…
			…
			…
…	…	…	…	…
			…

Предположим, что диетолог уже выбрал диету, т.е. определил, что человек должен за месяц потреблять h₁ кг продукта F₁,...,h_n кг продукта F_n. Полное количество питательного вещества N₁ будет

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

(7.77)

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

(7.78)

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

(7.79)

Таким образом, мы пришли к задаче: найти неотрицательное решение h₁, ..., h_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₊₁, х_r+2, …, х_n} - свободные. Подставляя (7.86) в (7.81), выразим функцию f через свободные неизвестные:

(7.87)

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

(7.88)