Решение ассортиментной задачи

РЕШЕНИЕ АССОРТИМЕНТНОЙ ЗАДАЧИ 

 
 

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

     Условие задачи отражает систему показателей, описывающую производство четырех  видов продукции P1, P2, P3, P4. Данное условие  накладывает ассортиментные ограничения  на производство двух видов продукции P1 (≥ 1000) и P2 (≤ 1100).

    В производстве этих изделий задействованы 4 вида ресурсов R1, R2, R3, R4. Каждый из ресурсов имеет ограничения, представленные в соответствующих ячейках таблицы условия. Продажа единицы каждого вида продукции приносит прибыль, равную Cj.

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

Решение 

Математическая  модель задачи 

    Пусть переменные x1, x2, x3, x4 - есть количество каждого вида продукции.

    Тогда целевая функция F(x) = 16x1 + 17,5x2 + 18,5x3 + 21x4 -> max будет описывать поставленную задачу при условии, что переменные удовлетворяют системе ограничений:

    В представленной системе неравенств, первые четыре являются функциями расходования 4-х  видов ресурсов на производство продукции. А два последних описывают ограничения, накладываемые на выпуск продуктов 1 и 4 типа.  

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

    С этой целью введем во все неравенства  кроме 3-го уравновешивающие переменные: x5, x6, x7,x8, x9.

     Экономический смысл этих переменных заключается  в том, что в систему вводится дополнительный остаток ресурсов (в случае ≤) или удаляется их излишек (≥).

    Данный  прием позволяет избавиться от знаков > и < в системе уравнений и привести математическую модель к каноническому виду

 

При этом каждая неизвестная  должна быть неотрицательным числом: x1, x2, x3, ……, x9 ≥ 0 

    Тогда целевая функция примет вид: F(x) = 16x1 + 17,5x2 + 18,5x3 + 21x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 -> max.  

    Уравновешивающие  переменные (x5 – x9) в целевой функции имеют нулевые коэффициенты, чтобы их значение не оказывало влияние на её конечный результат.

          Для дальнейшего решения  мы должны прибегнуть к симплексному методу математического программирования. Но для реализации такого решения, необходимо чтобы, математическая модель задачи содержала подматрицу единичных векторов. Такая подматрица формируется уникальными неизвестными, содержащимися в каждом из уравнений системы с коэффициентом = 1. В нашем же случае в двух из 6-ти уравнений такие неизвестные имеют коэффициент = -1, а одно уравнение вообще не содержит такой переменной.

    Чтобы привести модель к приемлемому виду мы должны воспользоваться методом искусственного базиса. Данный метод, подразумевает  введение в систему дополнительных искусственных неизвестных, формирующих  подматрицу единичных векторов. В нашем случае неизвестные искусственного базиса требуется ввести в 1, 3 и 5 уравнения. Пусть это будут переменные с именами y1, y2, y3. Тогда система уравнений примет вид:

    

 
 

    После преобразования модели задачи мы получили подматрицу единичных векторов, образованную неизвестными y1, x6, y2, x7, y3, x9.

    Алгоритм  симплексного метода подразумевает  итеративный перебор образовавшейся таблицы со значениями неизвестных. Основную роль в этом переборе играет выбор ключевого столбца, который осуществляется (в случае стремления к максимуму) путем выделения столбца, в котором сумма произведений коэффициентов при неизвестных в уравнениях на соответствующие коэффициенты в целевой функции, является наименьшим отрицательным числом. Следовательно, для того, чтобы искусственные неизвестные не повлияли на процесс перебора симплекс таблиц, в целевой функции им присваиваются коэффициенты (-M) - бесконечно малые значения < 0.

    F(x) = 16x1 + 17,5x2 + 18,5x3 + 21x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 – My1 – My2 – My3-> max.

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

    Таким образом, при дальнейшем переборе таблиц, для  выбора ключевого столбца, мы будем  учитывать только значения, зависимые  от коэффициента М, до тех пор, пока все неизвестные Y не будут выведены из базиса. После этого, мы будем действовать в соответствии со стандартным алгоритмом симплексного метода: