Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Разработка моделей линейного программирования






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

Термин “разработка” означает построение моделей ЛП практических задач. Построение моделей не следует рассматривать только как науку, скорее это искусство, которое постигается с опытом. Разработка модели ЛП включает следующие основные этапы: определение переменных задачи, представление ее ограничений в виде линейных уравнений или неравенств; задание линейной целевой функции, подлежащей минимизации или максимизации. В качестве примера, иллюстрирующего основные этапы разработки модели ЛП, рассмотрим одну классическую экономико-математическую модель.

Простейшая задача производственного планирования. Пусть имеется некоторыйэкономический объект (предприятие, цех, артель и т. п.), который может производить некоторую продукцию п видов. В процессе производства допустимо использование т видов ресурсов (сырья, рабочего времени и пр.). Применяемые технологии характеризуются нормами затрат единиц сырья на единицу производимого продукта. Обозначим через ai, j количество i -го ресурса (i = 1, …, m), которое тратится на производство единицы j -го продукта (j = 1, …, n).

Если j -й продукт производится в количестве xj, то в рамках описанных выше технологий мы должны потратить a 1, j xj первого ресурса, a 2, j xj - второго, и так далее, am, j xj - m -го. Сводный план производства по всем продуктам может быть представлен в виде п -мерного вектора-строки х = (x 1, x 2, …, xj, …, xn). Тогда общие затраты i -го ресурса на производство всех продуктов можно выразить в виде суммы

Очевидно, что всякая реальная производственная система имеет ограничения на ресурсы, которые она тратит в процессе производства. В рамках излагаемой модели эти ограничения порождаются т -мерным вектором b = (b 1, b 2, …, bm), где bi - максимальное количество i- го продукта, которое можно потратить в производственном процессе. В математической форме данные ограничения представляются в виде системы т неравенств:

a 1, 1 x 1 + a 1, 2 x 2 + … + a 1, n xn £ b 1,

a 2, 1 x 1 + a 2, 2 x 2 + … + a 2, n xn £ b 2,

... (3.23)

am , 1 x 1 + am , 2 x 2 + … + am , n xn £ bm.

Следует иметь в виду, что к ресурсам относятся также производственные мощности. В этом случае соответствующие ограничения в системе (3.23) могут иметь вид, например,

xi £ bi.

К системе (3.23) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства:

х 1 ³ 0, …, хj ³ 0, …, xn ³ 0. (3.24)

Обозначив через cj цену единицы j -го продукта, получим выражение суммарного дохода от выполнения плана производства, задаваемого вектором х:

f (x) = c 1 x 1 + c 2 x 2 + … + cn xn. (3.25)

Формулы (3.23)-(3.25) являются не чем иным, как простейшей математической моделью, описывающей отдельные стороны функционирования некоторого экономического объекта, поведением которого мы хотим управлять. В рамках данной модели, вообще говоря, можно поставить различные задачи, но, скорее всего, самой естественной будет задача поиска такого плана производства х, который дает наибольшее значение суммарного дохода, т. е. функции (3.25), и одновременно удовлетворяет системе ограничений (3.23)-(3.24). Кратко такую задачу можно записать в следующем виде:

f (x) ® max, x Î X, (3.26)

где допустимое множество Х определяется ограничениями (3.23)-(3.24).

К модели (3.23)-(3.25) сводятся и другие задачи планирования. Например, если сj означает общие расходы на производство единицы j -го продукта, то суммарные затраты на выполнение всего плана х выражаются также функцией (3.25). Однако в этом случае наиболее естественной задачей для (3.23)-(3.25) будет задача поиска такого плана производства х, удовлетворяющего ограничениям (3.23)-(3.24), при котором значение суммарных затрат, т. е. функции f (x), будет наименьшим:

f (x) ® min, x Î X. (3.27)

Несмотря на явную условность рассматриваемой ситуации и кажущуюся простоту задач (3.26), (3.27), их решение является далеко не тривиальным и во многом стало практически возможным только после разработки соответствующего математического аппарата. К модели (3.26) или (3.27) могут быть сведены очень многие проблемы различного характера.

Пример 3.3. Задача технического контроля.

В отделе технического контроля (ОТК) некоторого предприятия работают контролеры разрядов 1 и 2. Норма выработки ОТК за восьмичасовой рабочий день составляет не менее 1800 изделий. Контролер разряда 1 проверяет 25 изделий в час, а контролер разряда 2 проверяет 15 изделий в час.

Расходы предприятия составляют 10 руб. в час на одного контролера разряда 1 и 9 руб. в час на одного контролера разряда 2. Предприятие может использовать не более 8 контролеров разряда 1 и 10 контролеров разряда 2. Руководство предприятия хочет определить оптимальный состав ОТК, при котором ежедневные затраты на контроль будут минимальными.

Разработка модели. Пусть х 1 и х 2 обозначают количество контролеров разряда 1 и 2 соответственно. Число контролеров каждого разряда ограничено, т. е. имеются следующие ограничения:

х 1 £ 8 (разряд 1),

х 2 £ 10 (разряд 2).

Ежедневно необходимо проверять не менее 1800 изделий. Поэтому должно выполняться неравенство

8× 25 х 1 + 8× 15 х 2 = 200 х 1 + 120 х 2 ³ 1800,

или 5 х 1 + 3 х 2 ³ 45.

Минимизируемая целевая функция, выражающая ежедневные расходы на контроль, имеет вид

f = 8(10 x 1 + 9 x 2) = 80 x 1 + 72 x 2.

Теперь можно сформулировать следующую задачу ЛП:

¦ = 80 х 1 + 72 х 2 ® min х Î Х,

Х: х 1 £ 8, х 2 £ 10, 5 х 1 + 3 х 2 ³ 45, х 1 ³ 0, х 2 ³ 0.

Поскольку любая научная модель содержит упрощающие предпосылки, для корректного применения полученных с ее помощью результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее “сильным” упрощением в рассмотренной модели является предположение о прямо пропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат ai , j. Очевидно, что это допущение далеко не всегда выполняется. Так, объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно в зависимости от изменения компонентов объема производства х. К другим упрощающим предпосылкам относятся предположения о независимости цен сj от объемов хj, что справедливо лишь для определенных пределов их изменения, пренебрежение эффектом кооперации в технологиях и т. п. Данные “уязвимые” места важно знать еще и потому, что они указывают принципиальные направления совершенствования модели.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.