Решения задачи планирования производства симплекс методом

Разности прямые - используется в большинстве задач, где скорость изменения ограничений относительно невысока. Увеличивает скорость работы средства Поиск решения.

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

е удается.

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

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

В результате исследования основных алгоритмов решения задач ЛП, было принято решение поставленную задачу планирования производства решать симплекс методом. Это обусловлено тем, что симплекс метод является эффективным алгоритмом и наиболее универсальным методом, которым можно решить любую задачу линейного программирования. В качестве вспомогательного средства, для составления конкретной задачи планирования производства (подбора таких значений, чтобы задача имела решение) было использовано средство «Поиск решения» в MS Excel.

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

Задача планирования производства относится к категории экономических проектов, к которым предъявлены определенные требования. Проект - это ограниченное по времени целенаправленное изменение отдельной системы с установленными требованиями к качеству результатов, возможными рамками расхода средств и ресурсов и специфической организацией.

3.1 Постановка задачи планирования производства в общем случае

Некоторое предприятие производит n типов продукции, затрачивая при этом m типов ресурсов. Известны следующие параметры: aij – количество i-го ресурса, необходимое для производства единичного количества j-й продукции; aij0 (i=1,…,m; j=1,…,n);

bi-запас i-го ресурса на предприятии, bi>0;

cj-цена единичного количества j-й продукции, cj>0.

Предполагается, что затраты ресурсов растут прямо пропорционально объему производства. Пусть xj – планируемый объем производства j-й продукции. Тогда допустимым является только такой набор производимой продукции x=(x1,x2,…,xn), при котором суммарные затраты каждого вида i-го ресурса не превосходят его запаса:

(1)

Кроме того, имеем следующее ограничение: xj0; j=1,…,n. (2)

Стоимость набора продукции x выражается величиной: (3)

Задача планирования производства ставится следующим образом: среди всех векторов x, удовлетворяющим ограничениям (1), (2), найти такой, при котором величина (3) принимает наибольшее значение.

3.2 Математическое описание поставленной задачи планирования симплекс методом

Пусть некоторое предприятие производит 5 видов продукции A, B, C, D и E, затрачивая при этом 5 типов ресурсов. На производство продукции типа A требуется следующее количество имеющихся на предприятии ресурсов (дается количество каждого ресурса, необходимого для производства единицы продукции типа A): 1 – количество ресурса 1, 4 – количество ресурса 2, 2 – количество ресурса 3, 1 – количество ресурса 4, 3 – количество ресурса 5. На производство единицы продукции типа B требуется (в условных единицах): 2 – количество ресурса 1, 2 – количество ресурса 2, 1 – количество ресурса 3, 4 – количество ресурса 4, 2 – количество ресурса 5. На производство единицы продукции типа C требуется (в условных единицах): 4 – количество ресурса 1, 1 – количество ресурса 2, 3 – количество ресурса 3, 1 – количество ресурса 4, 2 – количество ресурса 5. На производство единицы продукции типа D требуется (в условных единицах): 3 – количество ресурса 1, 2 – количество ресурса 2, 4 – количество ресурса 3, 2 – количество ресурса 4, 1 – количество ресурса 5. На производство единицы продукции типа E требуется (в условных единицах): 1 – количество ресурса 1, 2 – количество ресурса 2, 1 – количество ресурса 3, 4 – количество ресурса 4, 4 – количество ресурса 5.

Допустим, что запас ресурса 1 на предприятии составляет 600 условных единиц, запас ресурса 2 – 590 условных единиц, запас ресурса 3 – 750 условных единиц, запас ресурса 4 – 670 условных единиц и запас ресурса 5 – 495 условных единиц.

Цена единицы продукции типа A равна 60 рублям, цена единицы продукции типа B равна 50 рублям, цена единицы продукции типа C равна 37 рублям, цена единицы продукции типа D равна 45 рублям, а единица продукции типа E – 56 рублям.

Нужно спланировать такой набор производимой продукции x=(x1, x2, x3, x4, x5), при котором суммарные затраты каждого вида ресурса не превосходят его запаса, т.е.

x1+4x2+2x3+1x4+3x5600;

2x1+2x2+x3+4x4+2x5590;

4x1+x2+3x3+x4+2x5750;

3x1+2x2+4x3+2x4+x5670;

x1+2x2+x3+4x4+4x5495;

и при этом должны выполняться следующие ограничения: x1, x2, x3, x4, x5 0. Спланированный набор производимой продукции x=(x1, x2, x3, x4, x5) должен обеспечить максимум стоимости данного набора

{60x1+50x2+37x3+45x4+56x5}max.

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

f(x)=60x1+50x2+37x3+45x4+56x5

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

x1+4x2+2x3+1x4+3x5600;

2x1+2x2+x3+4x4+2x5590;

4x1+x2+3x3+x4+2x5750;

3x1+2x2+4x3+2x4+x5670;

x1+2x2+x3+4x4+4x5495;

x1, x2, x3, x4, x5 0.

3.3 Решение поставленной задачи планирования производства

 Скачать реферат