Исследование математических операций 2 (стр. 4 из 28)

При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевой функции и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если, продавая j-й товар в общем случае по цене 100 рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной x_j . Т.е. в разных ситуациях одна единица j-го товара будет приносить разный доход. Аддитивность означает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных.

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

Допустимое решение – это совокупность чисел (план) X = (x₁, x₂ , ... , x_n), удовлетворяющих ограничениям задачи.

Оптимальное решение – это план, при котором целевая функция принимает свое максимальное (минимальное) значение.

Если математическая модель задачи линейного программирования имеет вид:

; (2.6)

,

, (2.7)

, , (2.8)

то говорят, что задача представлена в канонической форме.

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот.

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

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

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

, где

- свободный индекс, .

Пример 2.1. Приведение к канонической форме задачи линейного программирования:

Введем в каждое уравнение системы ограничений выравнивающие переменные x₄, x₅, x₆. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x₄, x₆ вводятся в левую часть со знаком "+", а во второе уравнение вводится x₅ со знаком "-".

.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

.

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

, где

,

.

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

.

Назад | Содержание | Далее

2.2. Построение экономико-математических моделей задач линейного программирования

Рассмотрим процесс построения математических моделей задач линейного программирования на примерах.

Пример 2.2. Определение оптимального ассортимента продукции.

Предприятие изготавливает два вида продукции - П₁ и П₂, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья - А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П₁ и вида П₂ дан в табл. 2.1.

Таблица 2.1.

Расход сырья продукции

Сырье	Расход сырья на 1 ед. продукции		Запас сырья, ед.
	П1	П2
А	2	3	9
В	3	2	13

Опыт работы показал, что суточный спрос на продукцию П₁ никогда не превышает спроса на продукцию П₂ более чем на 1 ед. Кроме того, известно, что спрос на продукцию П₂ никогда не превышает 2 ед. в сутки.

Оптовые цены единицы продукции равны: 3 д. е. - для П₁ и 4 д.е. для П₂.

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

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

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

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

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

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

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

Предположим, что предприятие изготовит х₁ единиц продукции П₁ и х₂ единиц продукции П₂. Поскольку производство продукции П₁ и П₂ ограничено имеющимися в распоряжении предприятия сырьем каждого вида и спросом на данную продукцию, а также учитывая, что количество изготовляемых изделий не может быть отрицательным, должны выполняться следующие неравенства:

Доход от реализациих₁ единиц продукции П₁ и х₂ единиц продукции П₂ составит F = 3 х₁ + 4х₂ .

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

Рассмотренная задача относится к разряду типовых задач оптимизации производственной программы предприятия. В качестве критериев оптимальности в этих задачах могут быть также использованы: прибыль, себестоимость, номенклатура производимой продукции и затраты станочного времени.

Пример 2.3. Использование мощностей оборудования.

Предприятие имеет m моделей машин различных мощностей. Задан план по времени и номенклатуре: Т - время работы каждой машины; продукции j-го вида должно быть выпущено не менее N_j единиц.

Необходимо составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство, если известны производительность каждой i-й машины по выпуску j-го вида продукции b_ij и стоимость единицы времени, затрачиваемого i-й машиной на выпуска j-го вида продукции c_ij .

Другими словами, задача для предприятия состоит в следующем: требуется определить время работы i-й машины по выпуску j-го вида продукции x_ij , обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин Т и заданному количеству продукции N_j .

По условию задачи машины работают заданное время Т, поэтому данное ограничение можно представить в следующем виде: