Линейная оптимизация (поиск решения)

7.1 Оптимизация как задача линейного программирования

Всегда полезно, что и почему вычислятся в той или иной задаче. Поэтому сначала рассмотрим некотрые теоретические основы регрессионного анализа.

Пусть имеется функция, называемая целевой, линейно зависящая от некоторых переменных (факторов).

$$f(X)=c_1 \cdot x_1 + c_2 \cdot x_2 +...+ c_n \cdot x_n$$

В данном случае $$X$$ – вектор неизвестных (значений факторов).

$$X=(x_1, x_2,...,x_n)$$

Значения неизвестных находятся из системы m линейных ограничений, которая может содержать как уравнения, так и неравенства.

$$\begin{cases} a_{11}x_1+a_{12}x_2+...+a_{1n}x_n \le b_1 \\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n \ge b_2 \\ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n = b_m \\ \end{cases}$$

При этом вводится дополнительное условие неотрицательности значений переменных.

$$x_1 \ge 0,x_2 \ge 0,...,x_n \ge 0$$

Неотрицательное решение системы (7.3), то есть вектор $$X$$ при соблюдении условий (7.3) и (7.4), называется "планом задачи".

Таблица исходных данных для задачи.

Продукция Сырье	Продукт 1	Продукт 2	Запасы сырья
1	5	9	45
2	3	9	19
3	2	1	10
ПРИБЫЛЬ	5	6

План X' называется оптимальным планом задачи максимизации (минимизации), если для любого плана X выполняется условие

$$f(X') \ge f(X)(f(X') \le f(X))$$

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

В современных офисных электронных таблицах для решения подобных задач имеется модуль "Solver" ("Поиск решения"). Далее рассмотри пример решения задачи линейной оптимизации в Gnumeric.

7.2 Пример задачи линейной оптимизации

Для разбора предлагается задача, взятая из учебного пособия "Математическое программирование", авторы Э.Ф.Брыжина и Э.А.Худобина, издательство СПбГИЭА, 1997 год.

Задача: Имеется три вида сырья в количествах 45 ед., 19 ед. и 10 ед. Из этого сырья нужно изготовить продукцию двух видов. Задан расход сырья каждого вида на производство единицы каждого вида продукции и прибыть от единицы продукции (см. таблицу). Требуется найти такой вариант выпуска каждого вида продукции, при котором прибыль будет наибольшей.

Обозначим через $$x_1$$ количество единиц продукции первого вида, через $$x_2$$ – второго вида. Тогда на выпуск этой продукции будет израсходовано $$5x_1 +9x_2$$ ед. сырья первого вида, $$3x_1 +3x_2$$ ед сырья второго вида и $$2x_1 +x_2$$ – третьего. Суммарная прибыль составит $$5x_1 +6x_2$$ денежных единиц. Т.к. нельзя израсходовать сырья больше, чем имеется, а суммарная прибыль зависит от количества выпущенной продукции, то получим следующую математическую модель данной задачи.

(рис 7.1) Исходные данные для поиска решения $$\begin{cases} 5 \cdot x_1 + 9 \cdot x_2 \le 45, \\ 3 \cdot x_1 + 3 \cdot x_2 \le 19, \\ 2 \cdot x_1 + x_2 \le 10, \\ \end{cases} \\ x_1 \ge 0x_2 \ge 0 \\ f(x)=5 \cdot x_1 + 6 \cdot x_2 \to max$$

7.3 Решение в Gnumeric

Для решения задачи в ЭТ прежде всего нужно определиться с расположением исходных данных и составить необходимые формулы. Пусть таблица будет скомпонована в соответствии с рис. 7.1.

Количества продукции 1-го и 2-го вида (которые предстоит вычислить) располагаются в ячейках A3 и B3 соответственно. В ячейку C3 записывается формула для вычисления прибыли, в ячейки B6:B8 – формулы для левых частей ограничений (см. математическую модель). Когда решение будет найдено, нули будут заменены какими-то другими значениями.

Далее вызываем модуль поиска решения (в главном меню "Сервис/Поиск решения...", рис. 7.2).

В диалоге поиска решения несколько вкладок, и в них потребуется устанавливать значения элементов ввода. На вкладке "Параметры" (рис. 7.2) требуется указать ячейку, содержащую формулу для целевой функции f(x), а также ячейки, в которых должны вычисляться параметры (в нашем случае $$x_1$$ и $$x_2$$ ). Заполним эту вкладку в соответствии с расположением исходных данных. Поскольку требуется найти максимум прибыли, установим переключатель "Равняется:" в позицию "Макс".

(рис 7.2) Диалог поиска решения в Gnumeric (Solver)

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

На следующей вкладке ("Модель") устанавливаем значения в соответствии с рис. 7.3. Ключ "Предполагать неотрицательность" как раз и означает, что искать нужно только положительные решения. В самом деле, количество продукции не может быть отрицательным.

Выбор алгоритма и вида модели влияет на результат и саму возможность существования решения, так что для задач линейного программирования нужно использовать установки, показанные на рис. 7.3.

Следующая вкладка ("Ограничения") позволяет задать ограничения для параметров модели. Здесь важно, что левая и правая часть ограничений задаются как адреса ячеек, содержащих формулы и значения. После того, как определены ячейка для левой части и значение для правой части ограничения и выбран знак отношения ("Тип"), нажатием на кнопку "Добавить" условие добавляется (рис. 7.4).

Для правой части ограничений можно использовать как конкретные значения, так и адреса ячеек, содержащих эти значения.

Остальные вкладки не играют существенной роли в решений задачи, поэтому после ввода всех ограничений нажимаем на кнопку "Решить" и получаем сообщение о результате решения (рис. 7.5). Если чего-то не хватает или выбраны неверная модель или алгоритм, выводится соответствующее сообщение об ошибке.

Значение "Objective value" соответствует полученному в результате решения значению целевой функции, а вычисленные значения переменных и результирующие значения ограничений появляются вместо исходных данных на листе таблицы, как показано на рис. 7.6.

(рис 7.3) Определение вида модели (рис 7.4) Определение ограничений (рис 7.5) Результат решения (рис 7.6) Найденное решение

Нужно отметить, что результаты полностью соответствуют приведенным в первоисточнике значениям 3 и 10/3.

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