Раздел 2. Детерминированные задачи Тема 2.1 Линейное программирование

Линейное программирование – это раздел математики, ориентированный на нахождение экстремума в задачах, которые описываются линейными уравнениями, причем линейными уравнениями описывается как сама целевая функция, так и входные параметры (ограничения). Другими словами термин «линейное программирование» характеризует определение программы (плана) работы конкретного экономического объекта на основе выявления линейных связей между его элементами. Задачей линейного программирования является нахождение оптимального, т. е. наилучшего, плана при заданной системе налагаемых на решение ограничений.

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

1. нахождение оптимального плана выпуска продукции (оптимальное распределение ресурсов);

2. оптимизация межотраслевых потоков (планирование производства различных видов продукции по отраслям);

3. определение оптимального рациона (оптимизация состава химической смеси);

4. транспортная задача (оптимальное распределение потоков товарных поставок по транспортной сети);

5. задача о размещении производства (планирование с учётом затрат на производство и транспортировку продукции);

6. задача о назначениях (оптимальное распределение различных видов транспортных средств) и др.

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

(1)

при наличии линейных ограничений

(2)

,

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

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

Чтобы составить математическую модель задачи ЛПР, не­обходимо:

• ввести обозначения переменных;

• исходя из цели экономических исследований, составить целевую функцию;

• учитывая ограничения в использовании экономических показателей задачи и их количественные закономернос­ти, записать систему ограничений.

Задача об оптимальном составе смеси (задача составления рациона, задача о диете)

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

Пример. Для откорма животных на ферме в их ежедневный рацион необходимо включить не менее 33-х единиц питательного вещества , 23-х единиц веществаи 12-ти единиц вещества. Для откорма используется 3 вида кормов. Данные о содержании питательных веществ и стоимости весовой единицы каждого корма даны в таблице.

	(усл. ед.)	(усл. ед.)	(усл. ед.)	Стоимость (руб.)
Весовая единица корма I	4	3	1	20
Весовая единица корма II	3	2	1	20
Весовая единица корма III	2	1	2	10

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

Математическая постановка задачи 1. Пусть ,,— количества кормовI, II, III видов, включаемые в ежедневный рацион (,). Тогда должно быть:

При этом линейная функция (стоимость рациона)

Задача об оптимальном распределении ресурсов при выпуске продукции на предприятии (об ассортименте)

К группе задач о распределении ресурсов относят задачи, цель которых состоит в том, чтобы организовать доставку материалов от некоторого числа источников к некоторому числу потребителей так, чтобы оказались минимальными либо расходы по этой доставке, либо время, затрачиваемое на неё и др., либо некоторая комбинация вышеперечисленного. В простейшем виде это задача о перевозках (транспортная задача).

Пример. На товарных станциях иимеется по 30 комплектов мебели. Известно, что перевозка одного комплекта со станциив магазины,,стоит 1 руб., 3 руб., 5 руб. соответственно, а стоимость перевозки со станциив те же магазины — 2 руб., 5 руб., 4 руб. необходимо доставить в каждый магазин по 20 комплектов мебели. Составить план перевозок так, чтобы затраты на транспортировку мебели были наименьшими.

Математическая постановка задачи. Количество комплектов мебели, перевозимых со станции в магазины,,через ,, а со станции – через ,,. Тогда схема перевозок буде выглядеть следующим образом:

	В	В	В	Всего отправлено
Из				30
Из				30
Всего получено	20	20	20	60

В соответствии с условием задачи (,— целые,). Задача сводится к тому, чтобы найти такое неотрицательное целочисленное решение системы

при котором линейная функция (стоимость перевозок)

имеет наименьшее значение.

Задача производства

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

Пример. Предприятие по производству мебели производит мебель трёх типов: наборы пристенной мебели (далее «стенки»), шкафы для одежды (далее «шкафы») и кухонные гарнитуры (далее «гарнитуры»). Для их производства в основном используются три типа сырья: древесина, стекло, зеркала. Удельные коэффициенты расхода сырья, а также трудозатраты на единицу каждого типа мебели приведены в таблице.

	Древесина,	Стекло,	Зеркала,	Трудозатраты, чел.-дней
«Стенка»	4	4	3	10
«Шкаф»	2	0	2	7
«Гарнитур»	2	5	1	8

Запасы сырья на складе обновляются ежемесячно и составляют 70  древесины, 90  стекла и 45  зеркал. Трудозатраты в месяц не должны превышать 200 человеко-дней. Чистая прибыль от продажи одной «стенки», «шкафа» и «гарнитура» составляет соответственно 2000 руб., 1250 руб. и 1500 руб. Найти оптимальный ассортимент продукции, максимизирующий общую прибыль за месяц.

Математическая постановка задачи. Пусть ,,— месячный выпуск продукции соответственно:«стенок», «шкафов» и «гарнитуров» (,— целые,). Тогда должно быть:

При этом линейная функция