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

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

Общая задача линейной оптимизации заключается в нахождении максимума (минимума) линейной целевой функции

(5)

при заданных ограничениях

(6)

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

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

Основной (или канонической) задачей линейного программирования называется задача, которая состоит в определении оптимального значения целевой функции, при условии, что система ограничений представлена в виде системы уравнений

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

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

· Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные задачи?

· Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?

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

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

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

Пример 1.

Предприятие выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты приносит предприятию прибыль в размере 30 ден.ед., выпуск одной тонны серной кислоты – 35 ден.ед. Для выполнения поступившего заказа предприятию необходимо выпустить не менее 250 т соляной и не менее 170 т серной кислоты. Выпуск кислот связан с образованием токсичных отходов, общее количество которых не должно превышать 600 т. При выпуске одной тонны соляной кислоты образуется 0,4 т токсичных отходов, а при выпуске одной тонны серной кислоты – 1,2 т. Необходимо определить, сколько соляной и серной кислоты должно выпустить предприятие, чтобы получить максимальную прибыль.

Составим математическую модель задачи.

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

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

Прибыль, получаемая от производства кислот равна .

Целевая функция будет иметь вид: .

Таким образом, математическая модель задачи следующая:

составить план , удовлетворяющий системе ограничений

,

при которой функция принимает минимальное значение.

Сформулируем данную задачу в общем виде.

Обозначим через x_j (j = 1, 2,…, n) – количество единиц j-го продукта в дневном рационе. В рационе используется n видов продуктов. Каждый продукт содержит m питательных веществ в количестве не менее b_i (i = 1,2,…,m) единиц, a_ij – число единиц питательного вещества s_i в единице продукта j-го вида. Известна стоимость c_j единицы j-го продукта. Необходимо составить рацион нужной питательности при минимальных затратах на него.

Экономико-математическая модель примет вид: