Полная версия

Главная arrow Математика, химия, физика arrow Математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Большое число экономических задач сводится к линейным математическим моделям. Традиционно оптимизационные линейные математические модели называются моделями линейного программирования. Этот термин появился в конце 30-х годов прошлого столетия, когда программирование на компьютере еще не было развито, и соответствует не очень удачному переводу английского “programmation”. Под линейным программированием понимается линейное планирование, т.е. получение оптимального плана-решения в задачах с линейной структурой.

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

Мы постараемся на доступном для понимания уровне изложить некоторые методы решения задач линейного программирования.

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

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

при выполнении условий:

где/ — целевая функция, или критерий эффективности (оптимальности) задачи; х., j = 1, п — управляющие переменные, или решения задачи (3.1)—(3.4); b., a.., i = ,m — параметры.

Функция (3.1) — линейная, ограничения (3.2)-(3.4) — линейные. Задача содержит п переменных и т ограничений.

Решить задачу линейного программирования — это значит найти значения управляющих переменных х., j = 1, п, удовлетворяющих ограничениям (3.2)-(3.4), при которых целевая функция

(3.1) принимает минимальное или максимальное значение.

В зависимости от вида целевой функции (3.1) и ограничений

(3.2) -(3.4) можно выделить несколько типов задач линейного программирования, или линейных моделей: общая линейная задача, транспортная задача, и др.

В качестве примера общей линейной задачи рассмотрим задачу составления плана реализации товара.

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

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

Построим математическую модель данной задачи.

  • 1. Цель — максимизация прибыли.
  • 2. Параметры:

п — число различных видов реализуемых товаров;

т — число разных видов средств;

b. — запас средств /-го вида, / = 1, т;

а.. — число средств /-го вида, используемых для реализации единицы товара у-го вида, / = 1, т, у = 1, п;

р.—прибыль от реализации единицы товарау-го вида, у = 1, п.

  • 3. Управляющие переменные х., у = 1, п — количество реализуемого товара у-го вида.
  • 4. Область допустимых решений формируют ограничения по запасам средств и условия неотрицательности управляющих переменных:

5. Критерий эффективности определяется по формуле где Р — суммарная прибыль.

В результате расчета линейной математической модели (3.5), (3.6) определяется количество реализуемых товаров каждого вида, обес- печивающее фирме максимальную прибыль.

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

Предприятие производит изделия трех видов, поставляет их заказчикам и реализует на рынке. Заказчикам требуется 1000 изделий первого вида, 2000 изделий второго вида и 2500 изделий третьего вида.

Условия спроса на рынке ограничивают число изделий первого вида 2000 единиц, второго — 3000 и третьего — 5000 единиц.

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

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

Таблица 3.1

Тип ресурсов

Вид изделий

Всего ресурсов

1

2

3

1

500

300

1000

25 000 000

2

1000

200

100

30 000 000

3

150

300

200

20 000 000

4

100

200

400

40 000 000

Прибыль

20

40

50

Выполним последовательно этапы построения математической модели.

  • 1. Цель — получение максимальной прибыли.
  • 2. Параметрами являются все числовые данные, приведенные в условии задачи.
  • 3. Управляющие переменные:

х, — число изделий первого вида;

х2 — число изделий второго вида;

х3 — число изделий третьего вида.

4. Ограничения: обеспечить заказчиков, не превысить запас ресурсов, не допустить затоваривания рынка.

В соответствии с этими ограничениями выпишем область допустимых решений задачи:

Первые три неравенства в системе (3.7) соответствуют спросу заказчиков. Неравенства с четвертого по шестое формализуют спрос на рынке. Последние четыре неравенства соответствуют ограничениям по ресурсам.

5. Целевая функция, или критерий эффективности задачи, имеет вид

В формуле (3.8) буквой Р обозначена прибыль. Ее надо максимизировать. Каждое слагаемое определяет прибыль от производства изделий каждого вида соответственно в количествах ху, х2, ху

Формулы (3.7), (3.8) — математическая модель поставленной задачи. Ограничения и целевая функция линейны по управляющим переменным, следовательно, данная модель является линейной. (При составлении модели предполагалось, что прибыль линейно зависит от числа реализуемых изделий.)

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>