Формы записи задами линейного программирования и ее экономическая интерпретация

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

В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции f():

(2.9)

при ограничениях (условиях):

(2.10)

………………………………

(2.11)

где - заданные постоянные величины. Так записывается общая задача линейного программирования в развернутой форме. Знак {≤,=,≥} означает, что в конкретной ЗЛП возможно ограничение типа равенства или неравенства (в ту или иную сторону).

Систему ограничений (2.10) называют функциональными ограничениями ЗЛП, а ограничения (2.11) - прямыми.

Вектор , компоненты которого х_j удовлетворяют системе ограничений (2.10) и (2.11), называется допустимым решением или планом ЗЛП, т.е. ограничения (2.10), (2.11) определяют область допустимых решений или планов задачи линейного программирования (область определения ЗЛП).

План (допустимое решение), который доставляет максимум или минимум целевой функции (2.9), называется оптимальным планом (оптимальным решением) ЗЛП.

Канонической формой записи задачи линейного программирования (КЗЛП) называют задачу вида (запись с использованием знаков суммирования):

(2.12)

(2.13)

(2.14)

Векторная форма записи КЗЛП имеет вид

где СХ - скалярное произведение векторов , ; А: и В - вектор-столбцы:

Матричная форма записи КЗЛП:

Здесь - вектор-строка; - матрица размерности т x п, столбцами которой являются вектор-столбцы Аj; X и В - вектор-столбцы:

Иногда используется стандартная форма записи ЗЛП:

Имеет место утверждение, что любую ЗЛП можно привести к каноническому виду.

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (2.10) k-й дополнительной (вспомогательной) переменной со знаком "-" в случае ограничения типа "³" и знаком "+" в случае ограничения типа "≤".

y

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

Переход в случае необходимости к задаче на максимум достигается изменением знака у целевой функции.

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

Пример 2.1 (задача о смесях). Стандартом предусмотрено, что октановое число автомобильного бензина Л-76 должно быть не ниже 76, а ОГЛАВЛЕНИЕ серы в нем - не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице:

Характеристика	Компонент автомобильного бензина
	№ 1	№2	№3	№ 4
Октановое число	68	72	80	90
ОГЛАВЛЕНИЕ серы, %	0,35	0,35	0,3	0,2
Ресурсы, т	700	600	500	300
Себестоимость, дев. ед./т	40	45	60	90

Требуется определить, сколько тонн каждого компонента следует использовать для получения 1000 т автомобильного бензина А-76, чтобы его себестоимость была минимальной.

Решение. Для решения этой задачи сформулируем ее экономико-математическую модель, т.е. сформулируем задачу математически. Введем необходимые обозначения: пусть x_j: (j = 1, 2, 3, 4) - количество в смеси компонента с номером j. Таким образом, формально план производства смеси представляет собой вектор

С учетом введенных обозначений математическая модель рассматриваемой задачи по критерию "минимум суммарных затрат на изготовление смеси" имеет вид

(1)

(2)

(3)

Функциональное ограничение (3) отражает необходимость получения заданного количества смеси (1000 т), (1) и (2) - ограничения по октановому числу и содержанию серы в смеси, остальные - ограничения по запасам соответствующих ресурсов (компонентов). Прямые ограничения очевидны, но принципиально важны для выбора метода решения. Полученная математическая задача (модель) - задача линейного программирования. Она может быть решена симплекс-методом, который рассмотрен в данной главе ниже (для автоматизации расчетов можно использовать надстройку Поиск решения MS Excel). В результате решения ЗЛП получим оптимальное решение:

где

Подставляя найденное решение в целевую функцию (ЦФ), имеем

Таким образом, предлагаются следующие рекомендации по производству смеси:

- для производства смеси компонент № 1 берется в количестве 571,429 т;

- компонент № 3 берется в количестве 142,857 т;

- компонент № 4 берется в количестве 285,714 т.

При таком смешении ожидаются минимальные затраты на производство смеси, равные 57 143 (ден. ед.).

Пример 2.2 (задача об оптимальном использовании ограниченных ресурсов).

На участок строящейся дороги необходимо вывезти 20 000 м³ каменных материалов. В районе строительства имеются три карьера с запасами 8000 м³, 9000 м³ и 10 000 м³. Для погрузки материалов используются экскаваторы, имеющие производительность 250 м³ в смену в карьерах 1, 2 и 500 м³ в смену в карьере 3.

Эти карьеры обеспечивают каменными материалами также ряд других строящихся объектов. На погрузку материалов для рассматриваемого участка выделен для экскаваторов общий лимит 60 машино-смен с правом использования его по усмотрению строителей.

Транспортные затраты на перевозку материалов характеризуются следующими показателями: на перевозку 1000 м³ материалов из карьера 1 требуется 100 автомобиле-смен, из карьера 2 - 1350 автомобиле-смен, из карьера 3 - 1700 автомобиле-смен.

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

Решение. Сформулируем экономико-математическую модель задачи. Примем за единицу измерения количества материалов 10 000 м³. Обозначим через х₁ - объем добычи материалов в карьере 1, х₂ - в карьере 2, х₃ - в карьере 3. Таким образом, формально план перевозок представляет собой вектор

С учетом введенных обозначений математическая модель рассматриваемой задачи по критерию "минимум суммарных транспортных затрат" имеет вид

(1)

(2)

(3)

(4)

(5)

Условие (1) отражает потребность в материалах, (2) - ограничение по наличию ресурса "фонд рабочего времени экскаваторов" (мы не можем использовать больше того, что у нас в наличии). Условия (3)-(5) отражают тот факт, что добыча материалов идет в условиях ограниченности запасов материалов в соответствующих карьерах. Полученная задача - задача линейного программирования; решив ее симплекс-методом (см. ниже), найдем оптимальный план (решение):

Таким образом, из карьера 1 следует вывезти 8000 м³ каменных материалов, из карьера 2 - 2000 м³, из карьера 3- 10 000 м³. Эго управленческое решение будет связано с минимальными транспорты м и затратами: