Раздел1. Основы линейного программирования

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

Оптимизационные задачи возникают при практической реализации принципа оптимальности в управлении.

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

Примеры критериев оптимальности:

1) максимум прибыли;

2)минимум затрат (материальных ресурсов, времени, стоимости и т.д.);

3)максимальное число комплектов продукции и т.д.

Экономико-математическая модель оптимизационной задачи:

(1)

(2)

(3)

Основные элементымодели:

1. Целевая функция (1) – отражает критерий оптимальности.

2. Система функциональных ограничений(2) – составляется из условий задачи.

3. Система прямых ограничений (3) – обеспечивает допустимость искомого решения.

Любая оптимизационная задача имеет два вида решений:

1) допустимые;

2) оптимальные.

Определение 1. Допустимым решением оптимизационной задачи называется такой набор значений переменных , при котором выполняются все условия систем (2) и (3).

Определение 2. Допустимое решение будет оптимальным, если на нем целевая функция (1) достигает своего максимума или минимума.

Большой класс оптимизационных задач – задачи математического программирования, в которых необходимо найти экстремум (максимум или минимум) функции при заданных ограничениях (условиях). Если все функции в модели задачи линейного вида, то имеем задачу линейного программирования (ЗЛП) общего вида:

(1)

(2)

(3)

Если все ограничения ЗЛП – неравенства, то запись модели задачи называется стандартной. Если все ограничения ЗЛП –уравнения, то запись модели называется канонической.Правило перехода от стандартной записи модели к канонической мы рассмотрим ниже. Существуют и другие формы записи ЗПЛ (векторная, матричная, с использованием знаков суммирования), с которыми можно познакомиться в учебных изданиях [3], [4].

Примерызадач линейного программирования

1. Задача об оптимальном использовании ресурсов (задача о коврах). В распоряжении фабрики имеется определенное количество ресурсов: рабочая сила (80 чел.-дней), сырье (480 кг), оборудование (130 станко-часов).Фабрика может выпускать ковры четырех типов. Данные о количестве единиц каждого ресурса, необходимых для производства одного ковра каждого типа, и доходах, получаемых предприятием от единицы каждого типа товаров, приведены в таблице:

Ресурсы	Нормы расхода ресурсов на один ковер	Наличие ресурсов
«Лужайка»	«Силуэт»	«Детский»	«Дымка»
Труд
Сырье
Оборудование
Цена ковра, тыс. руб.

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

ЭММ задачи:

, , , – искомое оптимальное количество ковров каждого из четырех типов соответственно;

F – общая максимальная стоимость продукции (критерий оптимальности);

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

2. Задача об инвесторе. Инвестор, располагающий суммой в 300 тыс. ден. ед., может вложить свой капитал в акции автомобильного концерна А и строительного предприятия В. Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причем последних можно купить не более чем на 100 тыс. ден. ед.Дивиденды по акциям А составляют 8% в год, по акциям В — 10%. Какую максимальную прибыль можно получить в первый год?

ЭММ задачи:

, – оптимальноеколичество средств, которые необходимо вложить в акцииА и В соответственно;

F – максимальная прибыль инвестора в первый год (критерий оптимальности);

3. Задача о банке. Пусть собственные средства банка в сумме с депозитами составляют Р млн руб. Часть этих средств, но не менее Q млн руб., должна быть размещена в кредитах, а вложения в ценные бумаги должны составлять не менее r% средств, размещенных в кредитах и ценных бумагах. Если – доходность кредитов, – доходность ценных бумаг (как правило, > ), то каково должно быть размещение средств, чтобы прибыль банка была максимальной?

ЭММ задачи:

, – средства, размещенные в кредитах и вложенные в ценные бумаги соответственно;

F – максимальная прибыль банка;

4. Задача о диете (рекомендуется рассмотреть самостоятельно[4]).

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

1) графический,

2) алгебраический (симплексный).

⇐ Предыдущая 123 4 5 6 7 8 9 Следующая ⇒