Реферат: Исследование математических операций 2

Допустимое решение – это совокупность чисел (план) 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. Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные данной задачи?