Метод линейного программирования, используемый для оптимизации экономических решений, относится к экономико-математическим методам, целью которых является построение определенной математической модели и экономический анализ полученного решения.
Под моделью понимают условный образ какого-либо объекта. Экономико-математическая модель есть математическое описание исследуемого экономического процесса или объекта.
Выделяют три основных этапа проведения экономико-математического моделирования:
1. Постановка цели и задач исследования, качественное описание объекта.
2. Формирование математической модели изучаемого объекта, выбор методов исследования, подготовка исходной информации.
3. Анализ математической модели, обработка и анализ результатов.
При использовании экономико-математических методов производят сравнение многочисленных вариантов экономических и управленческих решений. В результате отбирают оптимальный вариант.
Для осуществления общей постановки задачи линейного программирования рассмотрим наиболее типичные частные задачи.
Задача об использовании ресурсов
Условие: Для изготовления двух видов продукции А и В используют четыре видов ресурсов – а, в, с, d. Прибыль, получаемая от реализации единицы продукции А – 2 рубля, продукции В – 3 рубля. Размеры запасов и нормы расхода каждого вида ресурсов приведены в таблице.
Вид ресурса | Запас ресурса | Норма расходов ресурсов на единицу продукции | |
A | B | ||
a | |||
b | |||
c | - | ||
d | - |
Цель задачи: построить оптимальный план производства продукции А и В, при котором прибыль была бы максимальной.
Решение:
Пусть x1 и x2 - объем выпуска продукции А и В соответственно. Тогда для производства заданного объема продукции потребуется затратить следующее количество различных ресурсов:
единиц,
единиц,
единиц,
единиц.
Потребление ресурсов не может превышать их запасов, тогда составим систему неравенств по ограничениям ресурсов:
Объемы производства продукции А и В должны быть больше или равны 0, значит x1 ≥ 0 и x2 ≥ 0.
Суммарная прибыль составит:
F=2x1+3x2 → max
Задачу легко обобщить на случай выпуска n-видов продукции с использованием m-видов ресурсов (ресурсы могут быть, как материальными, так и стоимостными).
Пусть:
хj , где j = 1, 2,.…, n – число единиц продукции, запланированной к производству;
bi где i=1,2…m – запас ресурса Si;
aij - число единиц ресурса Si в ед.продукции Pj;
cj - прибыль от реализации единицы продукции Pj,
Тогда задача оптимизации плана производства примет следующий вид:
при условии, что x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,..., xn ≥ 0 , при котором функция F примет максимальное значение:
F=c1x1+c2x2+…+cnxn → max
Задача о составлении рациона
Условие: Имеется два вида продукта питания, содержащих витамины (питательные вещества) S1, S2, S3. Стоимость 1 кг продуктов соответственно 4 и 6 руб.
Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором количество питательных веществ было бы не ниже нормы.
Питательное вещество | Норма пит. вещества | Число единиц питательных веществ в 1кг продукта | |
A | B | ||
S1 | |||
S2 | |||
S3 |
Решение:
Пусть x1 и x2 – соответственно объем потребления продуктов А и В в дневном рационе. Тогда дневной рацион будет составлять из следующего количества питательных веществ:
Составим систему ограничений дневного рациона с точки зрения нормы потребления питательных веществ:
при x1 ≥ 0, x2 ≥ 0
Общая стоимость рациона составит
F=4x1+6x2 → min
Для общей постановки задачи (например, для определения потребительской корзины) построим следующую модель, где:
xj (j=1, 2…n) - число единиц продукции j - вида;
bi (i=1, 2…m) – минимум содержания в рационе питательного вещества Si;
aij – число единиц питательного вещества Si в единице продукции j –того вида;
сj – стоимость единицы j – того вида продукции.
Тогда
При условии x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,..., xn ≥ 0
Функция принимает минимальное значение:
F=c1x1+c2x2+…+cnxn → min
Задача об использовании производственной мощности,
или о загрузке оборудования
Условие: фирме необходимо за время Т выпустить n единиц продукции Р1, Р2, Р3..Рn. Задействовано оборудование S1,S2,...,Sm. Производительность единицы оборудования aij, затраты на изготовление единицы продукции Рj в единицу времени на станке Si составит bij.
Цель: определить оптимальный план загрузки оборудования так, чтобы денежные затраты на производство продукции были бы минимальными.
Решение:
Пусть xij – время изготовления продукции Рj на станке Si. Время работы каждого вида оборудования не должно превышать Т, тогда
План выпуска по видам продукции составит
при, где i = 1, 2…k
Тогда затраты на производство всей продукции составят:
F=b11x11+b12x12+…+bmkxmk → min
Задача об оптимальном раскрое (использовании) материалов
Условие: На раскрой поступает материал в количестве a единиц. Требуется изготовить L разных деталей, пропорциональных числам b1, b2,...,bi (условие комплектности). Каждая деталь может быть раскроена n-различными способами, причем при каждом i-том способе (i=1, 2…n) может быть получено aik единиц k-той детали (k=1, 2 … L). Найти план раскроя, обеспечивающий максимальное число комплектов.
Решение:
Пусть xi – число единиц материала, раскраиваемых i - тым способом, x - число раскраиваемых деталей. Весь материал a раскраивается i -тым способом, тогда
Тогда требуемое количество деталей выразится:
при xi ≥ 0 (i=1, 2 … n)
По условию нужно найти решение X = (x1, x2,...,xn), удовлетворяющее системе уравнений
при условии, что xi ≥ 0, при котором функция F=X примет максимальное значение.
Если раскраивается m - различных материалов, тогда каждый j -тый вид материала (j=1, 2 … m) может быть раскроен n-способами, где каждый i -тый способ (i=1, 2 … n) дает aik единиц k -того изделия (k=1, 2…l), а запас j -того материала равен aj единиц и xij - число единиц j -того материала, раскраиваемого i -тым способом.
Тогда экономико-математическая модель примет следующий вид:
при xij ≥ 0 функция F = X примет максимальное значение.
Рассмотренные выше традиционные примеры позволяют сформулировать общую задачу линейного программирования: дана система m -линейных уравнений и неравенств с n -переменными.
Найти такое решение системы X = (x1, x2,...,xj ,...,xn ), где xi ≥ 0, при котором функция
F = c1x1+c2x2+…+cnxn → max(min)
или
Если система ограничений состоит из неравенств, то задача линейного программированияназывается стандартной. Если система ограничений состоит из уравнений, то задача называется канонической. В совместном случае задачу называютобщей.
Для решения задачи линейного программирования применяют вспомогательную теорему, позволяющую привести стандартную задачу к канонической.
ТЕОРЕМА Всякому решению (a1, a2,…,an) неравенства ai1x1+ai2x2+…+ainxn ≤ bi coответствует решение (a1, a2,…, an, an+1) уравнения ai1x1+ai2x2+…+ainxn +xn+1=bi , в котором xn+1 ≥ 0. И наоборот, каждому решению уравнения соответствует определенное решение неравенства. |
Тогда, если в системе ограничений имеется знак «≤», то дополнительная переменная вводится со знаком « + », если в ограничении знак «≥0 », то дополнительная переменная вводится со знаком « - ».
Тогда в общей постановке задачи линейного программирования система ограничений примет следующий вид:
где xj ≥ 0 (j=1, 2 … n) и функция
F=c1x1+c2x2+…+cnxn → max(min).