КЛАССИЧЕСКИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

Предприятие может выпускать п видов продукции Р, Р2, ?, Рп, располагая для этого т различными ресурсами R2, ..., Rm в количествах Ь, Ът соответственно. Известно, что для выпуска единицы продукции Pj необходимо затратить единиц ресурса Rit г = 1,2, m,j = 1, 2, п. Кроме того, известен доход от продажи единицы каждого вида продукции — с*, С2,сп соответственно, где Cj — стоимость единицы продукта Pj, например штуки, тонны и т.д.

Требуется спланировать производственную программу — объемы выпуска каждого вида продукции (в штуках, тоннах и т.п.), чтобы максимизировать доход предприятия. Для удобства дальнейших выводов и рассуждений сведем исходную информацию в единую табл. 13.1, где через Xj обозначаются объемы продукции Pj, выпускаемой предприятием. Тогда набор переменных (х, Х2,..., хп) представляет собой не что иное, как производственную программу предприятия. Доход, полученный предприятием при производстве продукта Pj в количествах Xj, составит cpcj, а при реализации производственной программы (х, Х2, ..., хп) будет равен величине

которая называется целевой функцией.

Подсчитаем, какое количество ресурсов будет израсходовано, если выбрать некоторый план (х^ х2, ..., хп). Ресурса R потребуется апх{ + а2Х2 + ... + апхп, в то время как в наличии имеется Ь и т.д.

Таблица 13.1

Необходимые ресурсы

Запасы

ресурсов

Продукция

Рх

Pi

Рп

Объемы выпуска

Х

х2

х„

Ъ

а

«12

«1л

я2

Ь2

«21

«22

«2л

К,

Ьт

«ml

«m2

«тл

Доход от реализации единицы продукции

Cl

с2

Сл

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

Кроме того, понятно, что переменные плана (xh х2,..., хп) должны быть неотрицательными числами, т.е.

Объединяя полученные результаты, получаем следующую ЗЛП.

Требуется найти совокупность значений (xh хъ ..., хп), обращающих в максимум целевую функцию (13.1), при условии, что переменные (х, х2, ..., х„) удовлетворяют системам ограничений (13.2) и (13.3).

Приведем конкретный пример такой задачи.

Пример 13.1. Фирма выпускает два вида древесностружечных плит — обычные и улучшенные. При этом производятся две основные операции — прессование и отделка. По технологии производства плиты изготавливаются партиями по 100 штук в каждой. Требуется указать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на ресурсы (материал, время, затраты) (табл. 13.2).

Таблица 13.2

Ресурсы

Количество ресурсов на 1 мес.

Партия из 100 плит

обычных

улучшенных

Материал, м2

4000

20

40

Время на прессование, чел.-ч

900

4

6

Время на отделку, чел.-ч

600

4

4

Необходимые денежные затраты, ден. ед.

6000

30

50

Доход от реализации единицы продукции, ден. ед.

80

100

Построим математическую модель задачи. Введем обозначения. Пусть Х — количество партий в 100 плит обычного вида, изготавливаемых в течение месяца, а х2 — количество партий в 100 плит улучшенного вида. Тогда доход от реализации плит при производственной программе (рс^ Х2) будет равен 80xj + 100х2.

Подсчитаем расходы ресурсов, необходимые для выполнения производственной программы (jti, Х2).

Материала будет израсходовано 20х + 40х22) при запасе, равном 4000т2. Следовательно, для того чтобы реализовать программу, необходимо выполнить условие

Расход ресурса «время на прессование» составит 4xt + 6х2 (чел.-ч) при запасе, равном 900 чел.-ч. Следовательно, для того чтобы реализовать программу, необходимо выполнить условие

Расход ресурса «время на отделку» составит 4xt + 4х2 (чел.-ч) при запасе, равном 600 чел.-ч. Следовательно, для того чтобы реализовать программу, необходимо выполнить условие

Расход ресурса «денежные затраты» составит 30xt + 50х2 (ден. ед.) при запасе, равном 6000 ден. ед. Следовательно, для того чтобы реализовать программу, необходимо выполнить условие

Кроме этого, переменные Х и х2 не могут принимать отрицательных значений, т.е. хх > 0, х2 > 0.

Подводя итог, получаем следующую ЗЛП:

Методы решения ЗЛП будут даны ниже. Рассмотренную задачу можно также решить графически.

Приведем ответ: для получения максимального дохода в размере 13 000 ден. ед. необходимо изготавливать 100 партий плит обычного вида и 50 партий плит улучшенного вида.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >