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

 

1.1. Постановка задачи

 

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

Общая задача линейного программирования (ЗЛП) состоит в нахождении экстремального значения (максимума или минимума) линейной функции.

Примером решения задачи является разработка оптимального плана деповского ремонта грузовых вагонов. В настоящее время этот вид ремонта выполняется в ремонтных вагонных депо, входящих в департамент ОАО «РЖД» по ремонту грузового вагонного парка. Программа ремонта по количеству и типам вагонов для каждого депо в отдельности устанавливается департаментом исходя из потребностей в ремонте, производственных мощностей депо и имеющихся в наличии производственных ресурсов. С учетом того, что в настоящее время неуклонно возрастает вагонный парк других собственников, а также предстоящим акционированием департамента возникает проблема определения оптимальной производственной программы депо, обеспечивающей максимальную прибыль предприятию.

Такая задача может быть сформулирована следующим образом. Имеем:

х_j – объем ремонта вагонов j-го типа; j = 1, 2, … n;

b_i – объем, имеющихся в наличии производственных ресурсов i-го вида; i = 1, 2, … m;

a_ij – расход i-го вида ресурсов на ремонт одного вагона j-го типа;

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

Решение задачи осуществляется на основе следующей экономико-ма­тематической модели.

Найти совокупность переменных х_j, максимизирующих целевую функцию F:

 

, (1.1)

 

при наложенных ограничениях (система m линейных уравнений и неравенств с n переменными):

 

, (1.2)

 

x_j, j = 1….n, (1.3)

 

где a_ij, b_i, с_j – заданные постоянные величины

Линейную функцию (1.1), для которой ищется экстремальное значение, принято называть целевой функцией. Условия (1.2) называются функциональными, а (1.3) – прямыми ограничениями задачи.

Виды задач ЛП:

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

2) задача на максимум выпуска продукции при заданном ассортименте;

3) задача о смесях (рационе, диете);

4) транспортная задача;

5) задача о рациональном использовании имеющихся мощностей;

6) задача о назначениях.

Для решения ЗЛП необходимо построить экономико-математическую модель исследуемого экономического процесса.

1.2. Решение задач линейного программирования

с помощью надстройки MS Excel «Поиск решения»

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

Он достаточно трудоемок. Поэтому выполнение расчетов рекомендуется в среде MS Excel.

Технологию решения задач линейного программирования в среде MS Excel продемонстрируем на следующем примере.

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

 

Таблица 1.1