2017-11-30
1695
Круг задач, решаемых при помощи методов линейного программирования достаточно широк:
· задача об оптимальном использовании ресурсов при производственном планировании;
· задача о смесях (планирование состава продукции);
· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
· транспортные задачи (анализ размещения предприятия, перемещение грузов).
1.Задача об оптимальном использовании ресурсов при производственном планировании. Общий смысл задач этого класса сводится к следующему. Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b1, b2,..., bm условных единиц. Известны также технологические коэффициенты aij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида (). Прибыль, получаемая предприятием при реализации изделия j-го вида, равна cj. В планируемом периоде значения величин aij, bi и cj остаются постоянными. Требуется составить такой план выпуска продукции, при реализации которого прибыль предприятия была бы наибольшей.
2. Задача о смесях (планирование состава продукции). К группе задач о смесях относят задачи по отысканию наиболее дешевого набора из определенных исходных материалов, обеспечивающих получение смеси с заданными свойствами. Иными словами, получаемые смеси должны иметь в своем составе m различных компонентов в определенных количествах, а сами компоненты являются составными частями n исходных материалов.
3. Транспортная задача. Под транспортной задачей понимают целый ряд задач, имеющих определенную специфическую структуру. Наиболее простыми транспортными задачами являются задачи о перевозках некоторого продукта из пунктов отправления в пункты назначения при минимальных затратах на перевозку. Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно. Обычно начальные условия транспортной задачи записывают в так называемую транспортную таблицу. В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки xij (т.е. xij - количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю). Необходимо определить наиболее дешевый вариант перевозок, при этом каждый поставщик должен отправить столько груза, сколько имеется у него в запасе, а каждый потребитель должен получить нужное ему количество продукции.
Задача (модель) линейного программирования, как и любая задача исследования операций, включает три основных элемента:
1. Переменные, которые следует определить.
2. Целевая функция, подлежащая оптимизации.
3. Ограничения, которым должны удовлетворять переменные.
В общем виде модель записывается следующим образом.
Целевая функция:
| c1x1 + c2x2 +... + cnxn → max(min) | (1.1) |
Ограничения:
| a11x1 + a12x2 +... + a1nxn {≤ = ≥} b1, a21x1 + a22x2 +... + a2nxn {≤ = ≥} b2, ... am1x1 + am2x2 +... + amnxn {≤ = ≥} bm | (1.2) |
Требование неотрицательности:
| xj ≥ 0 | (1.3) |
При этом aij, bi, cj() - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (1.1) при соблюдении ограничений (1.2) и (1.3). Систему ограничений (1.2) называют функциональными ограничениями задачи, а ограничения (1.3) - прямыми. Вектор, удовлетворяющий ограничениям (1.2) и (1.3), называется допустимым решением (планом) задачи линейного программирования. План, при котором функция (1.1) достигает своего максимального (минимального) значения, называется оптимальным.
