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

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

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

Постановка практической задачи ЛП включает следующие основные этапы: определение показателя эффективности, переменных задачи, задание линейной целевой функции W(x), подлежащей минимизации или максимизации, функциональных h_k(x), g_j(x) и областных x_li <x_i <x_ui ограничений.

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

2. В качестве управляемых переменных задачи следует взять:

3. Целевая функция:

где

4. Ограничения:

4.1. По использованию земли, га:

4.3. По трудовым ресурсам, ч:

4.4. Обязательства по контракту, шт.:

4.5. Областные ограничения:

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

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

Таблица 2.1.

1. В качестве показателя эффективности целесообразно взять годовой выход деловой древесины.

2. В качестве управляемых переменных задачи следует взять площади каждого из трех типов древостоя, которые могут быть вырублены в каждый из трех периодов, т.е. 9 переменных x_ij, где i - тип древостоя, j - период вырубки:

x₁₁ - площадь древостоя типа 1 вырубаемого в период 1, га;

x₁₂ - площадь древостоя типа 1 вырубаемого в период 2, га;

x₁₃ - площадь древостоя типа 1 вырубаемого в период 3, га;

x₂₁ - площадь древостоя типа 2 вырубаемого в период 1, га;

x₂₂ - площадь древостоя типа 2 вырубаемого в период 2, га;

x₂₃ - площадь древостоя типа 2 вырубаемого в период 3, га;

x₃₁ - площадь древостоя типа 3 вырубаемого в период 1, га;

x₃₂ - площадь древостоя типа 3 вырубаемого в период 2, га;

x₃₃ - площадь древостоя типа 3 вырубаемого в период 3, га.

3. Целевая функция:

4. Ограничения:

4.1. По общей вырубаемой площади, га. Общая вырубаемая площадь в каждом типе древостоя за 3 периода не может превышать площадь типа древостоя. Это очевидное ограничение может быть формализовано следующим образом:

4.2. По равномерности выхода вырубаемой древесины, м³. То же самое требование налагается на объем древесины, который вырубается каждый период. С повторяющимися циклами, проблема решается получением самым возможным высоким уровнем рубки:

3 x₁₁ + 12 x₂₁ + 25 x₃₁ = 2000,

10 x₁₂ + 17 x₂₂ + 20 x₃₂ = 2000,

30 x₁₃ + 20 x₂₃ + 18 x₃₃ = 2000.

4.3. По расчетной лесосеке, га. Равный периодическая вырубаемая лесосека принятая во внимание для целей сохранения первозданной природы и лесозаготовок. Предполагая что 360/3 или 120 га за период желателен. Это также говорит, что весь лес должен быть вырублен в 60 лет. Для трех периодов это условие формулируется следующим образом:

x₁₁ + x₂₁ + x₃₁ = 120,

x₁₂ + x₂₂ + x₃₂ = 120,

x₁₃ + x₂₃ + x₃₃ = 120.

4.4. По ограничению в сохранении окружающей среды, га. Условие принимает во внимание ограничения биологов, вырубаемая лесосека для каждого типа древостоя в каждый период обеспечивает вегетационную структуру для обитателей. Это требование обеспечивает каждый вырубаемый период меньше, чем вся площадь в типе древостоя и помогает обеспечить сбалансированность распределения возрастного состава на земле. Максимальная вырубаемая площадь по каждому типу древостоя за каждый период: для древостоя 1 типа - 40 га, 2 типа - 90 га, 3 типа - 25 га:

4.5. Областные ограничения:

Таблица 2.2.

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

1. В качестве показателя эффективности целесообразно взять транспортные издержки (ежедневные в рублях).

2. В качестве управляемых переменных задачи следует взять число отгружаемых лесовозов в день из трех лесосек на три лесозавода, т.е. 9 переменных x_ij, где i - номер лесосеки, j - номер лесозавода.

x₁₁ - площадь древостоя типа 1 вырубаемого в период 1,

3. Целевая функция:

4. Ограничения:

4.1. По вырубаемой древесине на лесосеках, лесовозы:

4.2. По потребности лесозаводов, лесовозы:

На первом шаге следует определить все возможные неотрицательные значения переменных x₁ и x₂, которые удовлетворяют ограничениям. С этой целью в декартовой системе координат (рис.2.1) наносим линии, соответствующие уравнениям прямым

4 x₁ + 1,5 x₂ = 24;

1200 x₁ + 150 x₂ = 6000;

20 x₁ + 20 x₂ = 200;

x₁ = 2; x₂ = 0,

Максимальный доход в размере 34 тыс. руб. лесничество может извлечь придерживаясь следующей стратегии - выращивая 3,6 бычка и 6,4 партии новогодних елей. Однако окончательное решение должно быть представлено в целочисленной форме. Как правило, в на практике полученные результаты округляют до ближайших целых, что может привести к достаточно грубым ошибкам. В разбираемом примере округление даст x₁=3 и x₂=6, что приводит к доходу в 30 тыс. руб. Однако достаточно удаленная от оптимального решения стратегия x₁=4 и x₂=5 приводит к более оптимистичному результату в 32,5 тыс. руб. Более того, как будет показано далее, еще более далекая точка x₁=3 и x₂=7 приводит к аналогичному результату. Поэтому расчеты необходимо продолжить с использованием методов целочисленного программирования, которые нами будут обсуждаться ниже.

Рис.2.1. Решение задачи ЛП графическим способом

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

при ограничениях

...

В матричной форме

при ограничениях

где

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

Ограничения в виде неравенств можно преобразовать в равенства при помощи введения так называемых остаточных или избыточных переменных.

Уравнение из примера 1

можно преобразовать в равенство при помощи остаточной переменной

4 x₁ + 1,5 x₂ + x₃ = 24.

Переменная x₃ неотрицательна и соответствует разности правой и левой частей неравенства.

Аналогично

можно преобразовать путем введения избыточной переменной x₄:

x₁ - x₄ = 2 .

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

3 x₁ - x₂ - 2 x₃ = -17;

где x₃ - переменная, неограниченная по знаку.

Последовательность действий следующая:

После преобразований имеем стандартную форму задачи ЛП:

x₁ + x₂ + x₄ - x₅ + x₆ = 8;

x₁ - x₂ + x₄ - x₅ - x₇ = 9;

-3 x₁ + x₂ + 2 x₄ - 2 x₅ = 17;

...

...

Переменные x₁, x₂,...,x_m, входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми - в остальные, называются базисными. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Остальные n-m переменных (x_m+1, ...,x_n) называются небазисными переменными.

Для приведения системы к каноническому виду можно использовать два типа элементарных операций над строками:

1. Умножение любого уравнения системы на положительное или отрицательное число.
1. Прибавление к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число.

Алгоритм симплекс - метода:

Таблица 2.3

2. Вычисляем вектор относительных оценок c при помощи правила скалярного произведения

где

Дополняем первоначальную таблицу c - строкой.

Таблица 2.4

Таблица 2.5

Таблица 2.6

В качестве примера решим задачу ЛП примера 2.1 "Оптимизация размещения побочного производства лесничества":

Приведем задачу к стандартной форме:

4 x₁ + 1,5 x₂ + x₃ = 24;

1200 x₁ + 150 x₂ +x₄ = 6000;

20 x₁ + 20 x₂ + x₅ = 200;

x₁ - x₆ = 2;

Приведем систему равенств к каноническому виду. Первые три уравнения имеют соответственно по базисной переменной x₃, x₄, x₅, однако в четвертом она отсутствует ввиду того, что при переменной x₆ стоит отрицательный единичный коэффициент. Для приведения системы к каноническому виду используем метод искусственных переменных. Идея метода заключается в следующем. Введем искусственную переменную x₇ в последнее уравнение

4 x₁ + 1,5 x₂ + x₃ = 24;

1200 x₁ + 150 x₂ +x₄ = 6000;

20 x₁ + 20 x₂ + x₅ = 200;

x₁ - x₆ + x₇ = 2;

Вспомогательная система имеет следующее допустимое базовое решение:

x₁ = x₂ = 0, x₃ =24, x₄= 6000, x₅ = 200, x₇ = 2.

Полученное решение не допустимо для первоначальной задачи, поскольку x₇ положительно. С другой стороны, любое базисное решение вспомогательной системы, в котором x₇ обращается в ноль, допустимо для исходной задачи. Этого можно добиться при помощи двухэтапного симплекс - метода:

1. Вводится искусственная целевая функция, равная сумме искусственных переменных (в нашем случае она одна), которая минимизируется при помощи симплекс - метода. Если минимальное значение вспомогательной задачи равно 0, то все искусственные переменные (x₇ в частности) обращаются в ноль и получается допустимое базисное решение начальной задачи.
1. На втором этапе допустимое базовое решение, полученное на первом этапе, улучшается в соответствии с целевой функции исходной задачи ЛП.

4 x₁ + 1,5 x₂ + x₃ = 24;

1200 x₁ + 150 x₂ +x₄ = 6000;

20 x₁ + 20 x₂ + x₅ = 200;

x₁ - x₆ + x₇ = 2;

Строим первоначальную таблицу

Таблица 2.7

Таблица 2.8

В табл.2.8 все коэффициенты в строке c положительны или равны нулю, поэтому текущее базисное решение оптимальное (минимальное), которое используем на втором этапе двухэтапного симплекс - алгоритма. С этой целью возвращаемся к первоначальной целевой функции W = 5000 x₁ + 2500 x₂ и продолжаем вычисления в симплекс - таблицах:

Таблица 2.9

Таблица 2.10

Таблица 2.11

• Этап 1. Рассматривается искусственная целевая функция, равная сумме искусственных переменных, которая минимизируется при помощи симплекс-метода. Другими словами, производится исключение искусственных переменных. Если минимальное значение вспомогательной задачи равно нулю, то все искусственные переменные обращаются в нуль и получается допустимое базисное решение начальной задачи. Далее реализуется этап 2. Если минимальное значение вспомогательной задачи положительное, то по крайней мере одна из искусственных переменных также положительная, что свидетельствует о противоречивости начальной задачи, и вычисления прекращаются.
• Этап 2. Допустимое базисное решение, найденное на первом этапе, улучшается в соответствии с целевой функцией исходной задачи ЛП на основе симплекс-метода, т.е. оптимальная таблица 1 этапа превращается в начальную таблицу этапа 2 и изменяется целевая функция.

Решение практической задачи нельзя считать законченным, если найдено оптимальное решение. Дело в том, что некоторые параметры задачи ЛП (финансы, запасы сырья, производственные мощности) можно регулировать, что, в свою очередь, может изменить найденное оптимальное решение. Эта информация получается в результате выполнения анализа чувствительности. Анализ чувствительности позволяет оценить влияние этих параметров на оптимальное решение. Если обнаруживается, что оптимальное решение можно значительно улучшить за счет небольших изменений заданных параметров, то целесообразно реализовать эти изменения. Кроме того, во многих случаях оценки параметров получаются путем статистической обработки ретроспективных данных (например, ожидаемый сбыт, прогнозы цен и затрат). Оценки, как правило, не могут быть точными. Если удается определить, какие параметры в наибольшей степени влияют на значение целевой функции, то целесообразно увеличить точность оценок именно этих параметров, что позволяет повысить надежность рассматриваемой модели и получаемого решения.

• Приведите математическую формулировку основной задачи линейного программирования.
• Какие неизвестные ограничения системы называются базисными?
• В чем заключается основная идея симплекс-метода?
• В чем состоит различие между симплекс-методом и методом полного перебора допустимых вершин области, задаваемой ограничениями?
• Каковы содержание и последовательность шагов симплекс -алгоритма, реализуемого на симплекс-таблицах?
• Как при помощи симплекс-метода определить, что задача линейного программирования имеет неограниченный оптимум?
• Что такое искусственные переменные и для чего они служат? В чем их отличие от остаточных (избыточных) переменных?
• Что такое анализ чувствительности и для чего он применяется?

Фирма выпускает три продукта: A, B, C. На производство единицы продукта A требуется затратить 1 ч. труда ИТР, 10 ч. физического труда и 3 кг сырья. Для единицы продукта B соответствующие показатели равны 2 ч., 4 ч и 2 кг, для продукта C - 1 ч, 5 ч. и 1 кг. Ресурсы составляют 100 ч. труда ИТР, 700 ч. физического труда и 400 кг сырья. При оптовых закупках покупателю предоставляются скидки, так что прибыли от продажи продукции изменяются как показано в табл. 2.12. Например, если продается 120 ед. продукта A, то первые 40 ед. приносят по 10 долл. прибыли; следующие 60 - по 9 долл., а остальные 20 - по 8 долл. Сформулируйте задачу линейного программирования, решение которой определяет наиболее доходный производственный план.

Таблица 2.12.

Леспромхоз, имеющий лесопильный и фанерный цеха, столкнулся с проблемой наиболее рационального использования выделенной лесосеки. Чтобы получить 2,5 м³ коммерчески реализуемых комплектов пиломатериалов, необходимо израсходовать 2,5 м³ еловых и 7,5 м³ пихтовой древесины. Для изготовления 100 м² фанеры требуется 5 м³ еловых и 10 м³ пихтовой древесины. Выделенная лесосека содержит 80 м³ еловых и 180 м³ пихтовой древесины. Согласно условиям поставок, в течении планируемого периода необходимо произвести по крайней мере 10 м³ пиломатериалов и 1200 м² фанеры. Доход с 1 м³ пиломатериалов составляет 80 000 руб., а со 100 м² фанеры - 300 000 руб. Оптимизировать использование лесосеки.

Таблица 2.13.

Таблица 2.14

В леспромхозе производится раскряжевка хлыстов на сортименты. Требуется получить сортименты трех видов - длиной 6, 2,2 и 1,5 м. Длина среднего хлыста 31 м, средний диаметр 0,3 м. План поставки сортиментов, соответственно, 30000 м³, 86000 м³ и 40000 м³. Используя карту раскроя хлыстов без учета толщины пропила (табл.2.15) определить оптимальный план раскроя.

Таблица 2.15

Нижний склад производит два вида продукции: обрезную доску и брус. Для изготовления 1 м³ бруса требуется 2,5 м³ сосны или 3 м³ ели. Для изготовления 1 м³ доски требуется 3 м³ сосны или 3,5 м³ ели. Максимальные суточные запасы сосны - 200 м³, ели - 300 м³. Суточный спрос на брус - 100 м³, на доску - 150 м³ при оптовых ценах за 1 м³ бруса - 200 000 руб., за 1 м³ доски - 300 000 руб. Определить оптимальные объемы выпуска бруса и доски.

Лесхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц вещества A и 12 единиц B. Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальны (по данным табл. 2.16).

Таблица 2.16

Леспромхоз имеет древесину трех видов в количествах: 1 - 1000 м³, 2 - 500 м³, 3 - 700 м³ , для изготовления изделий A, B, C и D. Нормы расхода древесины в м³ на изготовление единицы каждого изделия и прибыль от реализации единицы изделия даны в табл. 2.17. Определить, сколько изделий каждого вида должно произвести предприятие, чтобы общая прибыль от реализации всех изделий была максимальной?

Производство двух видов лесопродукции должно пройти три операции. Затраты времени на каждой операции на одно изделие, прибыль от реализации одного изделия в табл. 2.18. Сколько изделий каждого вида должно произвести предприятие, чтобы получить максимум прибыли, причем число изделий A должно быть не менее 10, а B - не более 70 единиц.

Предприятие должно выпустить по плану продукции A - 500 единиц, B - 300 единиц, C - 450 единиц на двух машинах. Каждая из двух машин может выполнить операции по производству всех трех видов продукции. Затраты времени на производстве единицы изделия каждой из двух машин приведены в табл. 2.19. Как распределить работу машин, чтобы затраты времени на выполнение плана были минимальны?

Таблица 2.19

Предприятию задана месячная программа по изготовлению четырех видов изделий в количествах: вида A - 5000, B - 2000, C - 3000, D - 1600. На предприятии имеется три группы станков с различной производительностью. Задается суммарное допустимое время работы за этот период для каждой группы станков: первой - 800 ч., второй - 1000 ч., третьей - 1500 ч. Нормы времени (в часах) на изготовление одного изделия на каждом станке и данные об издержках (в рублях) на изготовление каждого изделия на станках различных групп приводятся в табл. 2.19. Требуется так распределить изготовление изделий по группам станков, чтобы была обеспечена заданная программа по изготовлению изделий и чтобы общие издержки были минимальны?

Таблица 2.20