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

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

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

1. Задача об оптимальном использовании ресурсов при производственном планировании.

Общий смысл задач этого класса сводится к следующему.

Предприятие выпускает n различных изделий. Для их производства требуется m различных видов ресурсов (сырья, материалов, рабочего времени и т.п.). Ресурсы ограничены, их запасы в планируемый период составляют, соответственно, b₁, b₂. b_m условных единиц.

Известны также технологические коэффициенты a_ij, которые показывают, сколько единиц i-го ресурса требуется для производства единицы изделия j-го вида ().

Прибыль, получаемая предприятием при реализации изделия j-го вида, равна c_j.

В планируемом периоде значения величин a_ij, b_i и c_j остаются постоянными.

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

Далее приведем простой пример задачи такого класса.

Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере $2, а каждый шахматный набор — в размере $4. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В — 72 н-часа и участка С — 10 н-часов.

Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

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

Таблица 1. Исходные данные задачи об использовании производственных ресурсов

Производственные участки

Затраты времени на единицу продукции, н-час

Доступный фонд времени, н-час

Источник

«Решение задач линейного программирования (лп)»

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

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

Свойство пропорциональностьозначает то, что вклад каждой переменной в целевую функцию ЦФ и общий объем потребления соответствующих ресурсов прямо пропорционален уровню (величине) этой переменной.

Аддитивностьзаключается в том, что целевая функция ЦФ представляет собой сумму вкладов от различных переменных. Аналогично левая часть каждого ограничения должна представлять собой сумму расходов, каждое слагаемое которой пропорционально величине соответствующей переменной. Если, например, фирма, производит два конкурирующих вида продукции, увеличение сбыта одного из которых отрицательно сказывается на объеме реализации другого, то такая модель не обладает свойством аддитивности.

Математическая модель задачи линейного программирования (ЛП) в достаточно общем случае формулируется следующим образом:

при следующих ограничениях на вектор искомых переменных x=i>:

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

В среде Mathcad решение задачи ЛП находится в рамках так называемых вычислительных блоков (начинаются с ключевого словаGiven) с использованием встроенных функцийMminimizeилиMaximizeдля минимизации или минимизации целевой функции. В прилагаемых примерах приведены решения нескольких типовых задач, в которых показано, что и как должно быть введено для получения решения. Целевую функцию и ограничения можно записывать в виде отдельных выражений, а также и в векторно-матричной форме, которая является лишь более удобной и компактной формой записи условий задачи ЛП.

В пакете Excel задачи ЛП решают с помощью встроенной функции «Поиск решения».

А. Одноиндексные задачи ЛП

Пример А.1. Решение одноиндексной задачи ЛП в Mathcad

Пример А.2. Решение одноиндексной задачи ЛП в Mathcad

Пример А.3. Задача планирования объемов производства

Задача №1. Фирма производит изделия двух видов A1 и A2 с помощью последовательной обработки каждой из них в трех цехах. Исходные данные задачи приведены в таблице:

Нормы затрат времени на 1 изделие, час/сут

Определить количества x_j, j = 1,2 , изделий Aj , которые необходимо изготовить для достижения максимальной прибыли

т.е. найти оптимальный план суточного выпуска изделий А1 и А2. Это типичная задача производственного планирования.

Отметим, что значения x₁и x₂не могут быть выбраны произвольно, так как существуют ограничения на суточное время работы в цехах. Эти ограничения записываются в виде:

Кроме того значения x₁и x₂не могут быть отрицательными:

Требуется найти такое неотрицательное решение x₁, x₂системы линейных неравенств (3.2), при котором целевая функция (3.1) принимает максимальное значение.

Решение одноиндексной Задачи №1 в системе Mathcad

Описание ограничений в матричном виде:

— матрица Мсодержит коэффициенты при неизвестных в левой части ограничений, а векторv— правые части исходных неравенств:

M:=v:=(3.2)

Решим задачу с помощью вычислительного блока

Для формирования нулевого приближения полагаем значение х₂равным нулю (инициализация решения)

x₂ := 0

M*x ≤ v x ≥ 0

Таким образом, точка максимума целевой функции F имеет координаты x₁ = 20, x₂ = 50, а значение ее значение в точке максимума:

.

Решение одноиндексной Задачи 1 в пакете Excel

Для решения оптимизационных задач в табличном процессоре Excelиспользуется пункт «Поиск решения» (Solver – Решатель) в меню «Сервис» на панели инструментов. Если этого пункта нет, то необходимо установить соответствующую надстройку. Для этого в менюСервиснужно выбрать пунктНадстройкии в диалоговом окне установить флажок слева от надписи «Поиск решения». В меню «Сервис» появится пункт «Поиск решения».

Решение.В соответствии сисходнымиданнымиЗадачи 1составим и заполним вExcel следующую таблицу

Числа в ячейках столбца «Ограничения»подсчитаны с помощью формул. Формула=СУММПРОИЗВ(В3:С3;$B$7:$C$7)-D3введена в ячейкуF3и продолжена в ячейкиF4:F5таблицы.

Эта формула также скопирована в F6, но без вычитаемогоD6. Выделим ячейкуF6 с целевой функцией и вызовем Решатель «Сервис/ Поиск решения». В диалоговом окне укажем: «Установить целевую ячейку:»$F$6, «максимальное значение», «Изменяя ячейки:»$B$7:$C$7, «Ограничения:»$F$3:$F$5

Так как все ограничения имеют одинаковые знаки «», тоздесьони введены блоком. Заметим, что количества x_j , j = 1, 2 изделий являютсяцелымичислами. Поэтому необходимо наложить еще одно ограничение:$B$7:$C$7=целое(целочисленная оптимизация).

В окне «Параметры» установим флажки «Линейная модель» и «Неотрицательные значения». Запустим «Выполнить».

Поиск решениявернет результат: х₁= 20; х₂= 50. Целевая функция равна Fmax = 5300. Этот результат поиска максимума функции F совпадает с результатами, полученными ранее с помощью пакета Mathcad.

Пример А.4. Задача о сплавах

Задача №2. Для изготовления сплава из меди, олова и цинка в качестве сырья используют два сплава тех же металлов, отличающихся составом и стоимостью. Данные об этих сплавах приведены в таблице:

Источник

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

Задача планирования производства (или задача об использовании ресурсов) является одной из разновидностей задачи линейного программирования.

Рассмотрим пример подобной задачи.

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

Число единиц ресурсов, затрачиваемых на изготовление единицы продукции

Прибыль, получаемая от единицы продукции и, – соответственно 2 и 3 руб.

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

Решение. Составим экономико-математическую модель задачи.

Обозначим ,– число единиц продукции соответственнои, запланированных к производству. Для их изготовления потребуетсяединиц ресурса,единиц ресурса,единиц ресурсаиединиц ресурса. Так как потребление ресурсов,,ине должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

(1.8)

По смыслу задачи переменные

(1.9)

Суммарная прибыль составитруб. от реализации продукцииируб.– от реализации продукции, т.е.

. (1.10)

Итак, экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий системе (1.8) и условию (1.9), при котором функция (1.10) принимает максимальное значение.

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

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

Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план выпуска продукции, удовлетворяющий системе

(1.11)

(1.12)

(1.13)

принимает максимальное значение.

Решение типового примера

Предприятию ООО «ТИТАН», одним из видов деятельности которого является выполнение токарных, фрезерных и сверлильных работ, поступил заказ на производство гаек стремянки, гаек штанги, гаек МОД и колец шкворня в количестве соответственно шт. Производство заказанной токарной продукции в полном объеме ограничено запасами имеющихся ресурсов (трудозатратами –чел.-час., запасом стали –кг, а также выделенными денежными средствами на оплату труда рабочих и последующую обработку токарной продукции –руб.). Кроме того, известно, что для производства единицы продукции каждого вида требуется соответственнокг стали, трудозатраты при этом составляют соответственночел.-час. За каждую изготовленную деталь рабочий предприятия получаетруб., последующая обработка единицы изделия каждого вида требует затрат денежных средств в размереруб. соответственно.

Задача оптимизации производства для ООО «ТИТАН» ставится в форме максимизации дополнительной прибыли предприятия при заданных ассортименте выпускаемой продукции и ограничениях на имеющиеся запасы ресурсов, при условии, что прибыль от реализации единицы продукции каждого вида составляет соответственно руб.

Исходные данные задачи представлены в таблице:

Ассортимент выпускаемой продукции

Источник

Читайте также:  Пандора сигнализация программирование брелков