Чтение онлайн

В общем виде постановка задачи линейного программирования заключается в следующем.

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

где Xj –искомые величины, содержащие решение поставленной задачи;

aijи bi –известные постоянные величины, характеризующие условия задачи.

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

где сj– постоянные коэффициенты (коэффициенты стоимости).

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

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

Общая математическая формулировка задачи соответствует условиям (16.10) и (16.11).

Первая строка системы уравнений (16.10)

в данном примере означает следующее:

a11– количество единиц ресурсов вида 1 на первом предприятии;

а12 –количество единиц ресурсов вида 1 на втором предприятии и т. п.;

b1– общий ресурс ресурсов вида 1 (для всех предприятий);

x1, x2и.т. д. – искомое количество предприятий типов 1, 2 и т. д.

Вторая строка упомянутой системы уравнений содержит аналогичные величины для ресурсов вида 2 и т. д. Функция цели соответствует формуле (16.11). Требуется обратить в минимум величину

где сj –показатель, характеризующий издержки предприятий.

Пусть т –общее число различных видов ресурсов, которыми располагает собственник, а п –число типов предприятий, между которыми эти ресурсы должны быть распределены. При этом известно, какое количество однородных ресурсов различного вида (i = 1, 2,... т)может быть реализовано на каждом из предприятий данного типа ( j= 1, 2,... п),а также общее количество ресурсов данного вида (bi).Известно также относительное значение издержек на каждом из предприятий (cj).

Задача заключается в том, чтобы наилучшим (оптимальным) образом распределить имеющиеся ресурсы по предприятиям, т. е. найти неизвестные величины xj,требуемые для этого количества предприятий данного типа.

ПРИМЕР

Собственник располагает четырьмя видами ресурсов ( m= 4). Это, например, денежные средства, производственные помещения, оборудование, сырье. Ресурсы необходимо распределить между шестью предприятиями ( п= 6). Предприятия различаются по экономическим условиям деятельности: месту расположения, системе налогообложения, стоимости энергии, оплате труда и т. д., в связи с чем имеют разные издержки производства. Относительные уровни издержек заданы табл. 16.2.

Таблица 16.2

Относительные уровни издержек на предприятиях

Распределение ресурсов по предприятиям сопряжено с необходимостью учета ряда ограничений, которые могут быть описаны системой четырех уравнений с шестью неизвестными, аналогичной системе (16.10):

Рис. 16.1. График оптимального распределения ресурсов

Смысл первого уравнения в нашем примере в том, что ресурс вида 1, общий ресурс которого составляет 16 единиц, может размещаться в количестве четырех единиц на предприятии первого типа и одной единицы – на предприятии четвертого типа. Аналогично раскрывается смысл второго и последующих уравнений. Последнее условие говорит о том, что число предприятий не может быть отрицательным.

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

В соответствии с табл. 16.1 целевая функция, подлежащая оптимизации, примет вид:

Решение

Решение задачи сводится к выполнению ограничений, заданных уравнениями (16.12), с учетом условия минимизации выражения (16.13).

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

Чтобы представить ограничения и целевую функцию на графике, необходимо выразить все известные через независимые величины. Например, x1и х2,соответствующие координатным осям, относительно которых будет производиться построение (рис. 16.1).

Из уравнений (16.12) следует:

Целевая функция примет вид

Из сопоставления уравнения (16.14) и последнего из ограничений (16.10) xj0 следует: