Мегаобучалка Главная | О нас | Обратная связь


Линейная производственная задача





Условия задачи:

Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов.

Известны технологическая матрица

А=

затрат ресурсов на производство единицы каждого вида продукции [элемент aij этой матрицы равен количеству ресурса i-го вида (i = 1, 2, 3), которое необходимо затратить в процессе производства единицы продукции j-го вида (j = 1, 2, 3, 4)],

вектор

Объем ресурсов и вектор

удельной прибыли на единицу продукции.

Требуется составить производственную программу, обеспечивающую предприятию наибольшую прибыль с учетом ограниченности запасов ресурсов.

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

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

Решение:

1. Формулирование экономико-математическая модели:

Исходя из условий и исходных данных экономико-математическая модель задачи примет вид: найти такой план Х(х1,х2,х3,х4) выпуска продукции удовлетворяющей системе по ограничению ресурсов:

и условию х1≥0,х2≥0,х3≥0,х4≥0,

при котором функция z=60x1+12x2+44x3+17x4 (2)

принимает максимальное значение.

Или другими словами, найти производственную программу Х(х1,х2,х3,х4) выпуска продукции максимизирующую прибыль:z=60x1+12x2+44x3+17x4 при ограничениях по ресурсам:



Для решения задачи приведем систему (1) к каноническому виду, для этого введем в систему уравнений дополнительные неотрицательные неизвестные: х5≥0, х6≥0, х7≥0– остаток ресурса определенного вида (неиспользуемое количество каждого ресурса).

Тогда вместо системы неравенств (1), получим систему линейных алгебраических уравнений:

где среди всех решений, удовлетворяющих условию неотрицательности: х1≥0, х2≥0, х3≥0, х4≥0, х5≥0, х6≥0, х7≥0.

Надо найти решение, при котором функция (2) примет наибольшее значение.

Эту задачу будем решать методом последовательного улучшения плана – симплексным методом.

2. Решение задачи симплексным методом.

2.1. Находим первое базисное решение

Воспользуемся тем, что правые части всех уравнений системы (3) неотрицательны, а сама система имеет такой вид, что дополнительные переменные являются базисными. Приравняв к нулю свободные переменные x1, x2, x3, x4, получаем базисное неотрицательное решение: х1=0, х2=0, х3=0, х4=0, х5=180, х6=160, х7=109.

Исходная симплексная таблица

Базис H Пояснения  
 
с     х1 х2 х3 х4 х5 х6 х7    
  х5  
  х6  
  х7 54,5  
    -60 -12 -44 -17    

На данной итерации:

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

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

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

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

2.2. Определение разрешающего элемента.

2.2.1. Определение разрешающей колонки.

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

2.2.2 определение разрешающей строки

Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной. В нашем случае, наименьшее положительное оценочное отношение 40 соответствует строке «х6», следовательно, она будет разрешающей.

2.2.3. определение разрешающего элемента

Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент а21=4, который расположен на пересечении строки «х6» и колонки «х1».

Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х6 и х1, в новой симплекс-таблице их меняем местами

2.3. Преобразование исходной симплексной таблицы

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

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

В результате данных преобразований получили новую симплекс- таблицу(итерация2).

Итерация2.

  Базис H Пояснения  
 
      х6 х2 х3 х4 х5 х6 х7    
  х5 2,00 -1 1,00 -1  
х1 0,5 0,5 0,25  
  х7 4,0 -1 0,0 -0,5 14,5  
    -12 -14    

В результате проведенных симплекс-преобразований получили новое базисное решение Х(х1,х2,х3,х4,х5,х6,х7)=(40,0,0,0,20,0,29). При данном базисном решении значение целевой функции z=2400, что больше чем при предыдущем базисном решении.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.

Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.

Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы содержится отрицательные элементы. (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к преобразованию симплекс таблицы итерации2 аналогично предыдущим действиям. В результате получаем симплекс таблицу итерации3.

 

Итерация3.

  Базис H Пояснения  
 
      х1 х2 х5 х4 х5 х6 х7    
х3 1,00 -0,5 0,50 -0,5    
х1 -0,5 0,75 -0,25 0,5    
  х7 2,0 -1,0 0,5    
       

В результате проведенных симплекс-преобразований получили новое базисное решение Х(х1,х2,х3,х4,х5,х6,х7)=(35,0,10,0,0,0,9). При данном базисном решении значение целевой функции z=2540, что больше чем при предыдущем базисном решении.

Не совместность системы ограничений в соответствии с признаком 1 в таблице не выявлена.

Неограниченность целевой функции в соответствии с признаком 2 в таблице не выявлена.

Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.

Найденное базисное решение в соответствии с признаком 4 оптимальное, так как в строке целевой функции симплекс-таблицы нет отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается).

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

Таким образом, получили производственную программу: х1=35, х2=0, х3=10, х4=0, которая является оптимальной и обеспечивает предприятию наибольшую возможную прибыль: z=60x1+12x2+44x3+17x4=60*35+12*0+44*10+17*0=2100+0+440+0=2540.

При этом первый и второй ресурсы будут использованы полностью, т. е. первый и второй ресурсы образуют «узкие места производства»: х5=0,х6=0, а третий ресурс будет иметь остаток: х7=9.

Оптимальное значение целевой функции (максимальная прибыль предприятия) рассматриваемой задачи z=2540, которое достигается при производственной программе Х(35,0,10,0,0,0,9).

3. Решение двойственной задачи

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

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

Предположим, некий предприниматель, занимающийся производством других видов продукции с использованием трех таких же видов ресурсов, предлагает «уступить» ему все имеющиеся ресурсы и обещает платить y1 денежных единиц за каждую единицу первого ресурса, y2 денежных единиц за каждую единицу второго ресурса и y3 денежных единиц за каждую единицу третьего ресурса. Возникает вопрос, при каких значениях y1, y2, y3 можно согласиться с предложением этого предпринимателя.

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

А=

 

Значит, для производства, например, первого вида продукции, предприятие должно затратить 4 единицы ресурса первого вида, 4 единицы ресурса второго вида и 2 единицы ресурса третьего вида, за что оно получит прибыль 60 денежных единиц. Следовательно, согласиться с предложением предпринимателя можно, если он заплатит не меньше, т. е. в ценах y1, y2, y3 это условие будет иметь вид:

4у1+4у2+2у3≥60

Аналогично и с продукцией второго, третьего и четвертого вида, при этом, за все имеющиеся ресурсы, предприниматель должен заплатить не меньше:

180у1+160у2+109у3 денежных единиц.

Следовательно, предприниматель будет искать такие значения y1, y2, y3, при которых эта сумма была бы как можно меньше. При этом речь идет о ценах, которые зависят не от цен, по которым эти ресурсы были когда-то приобретены, а о ценах зависящих от применяемых в производстве технологий, объемов ресурсов и прибыли, которую возможно получить за произведенную продукцию.

Таким образом, задача определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок y(y1,y2,y3), минимизирующий общую оценку всех ресурсов f=180y1+160y2+109y3.

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

Причем оценки ресурсов не могут быть отрицательными, т. е.:y1≥0 , y2≥0,y3≥0, .

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

Т. е. для оптимальных решений x(x1, x2,… xn)и y(y1,y2,y3) пары двойственных задач необходимо и достаточно выполнение условий:

 

 

Ранее в предыдущем пункте было определено, что x1>0, x2>0,x3>0, a x4=0 и x2=0, тогда

Но т. к. третий ресурс был избыточным, то по второй теореме двойственности, его двойственная оценка равна нулю, т. е.y3=0 . Тогда переходим к новой системе уравнений:

4у1+4у2-60=0 28+35-60=0

4у1+2у2-44=0 4*7+2*8-44=0

Откуда получаем y1=7, у2=8

Таким образом, получили двойственные оценки ресурсов: у1=7, у2=8, у3=0

Тогда общая оценка всех ресурсов равна:

F=180y1+160y2+109y3=180*7+160*8+0=1260+1280=2540

То же самое решение значений двойственных оценок содержится в последней строке симплексной таблицы и имеет определенный экономический смысл:

y1=7– показывает, что добавление одной единицы первого ресурса обеспечит прирост прибыли в 7 денежных единиц; y2=8– показывает, что добавление одной единицы второго ресурса обеспечит прирост прибыли в 8 денежные единицы.

Одновременно технологические оценки из той же строки симплексной таблицы:

2=2– показывает, что если произвести одну единицу продукции второго вида (не входящую в оптимальную производственную программу), то это уменьшит прибыль на 7 денежных единиц;∆4=6– показывает, что если увеличить выпуск продукции четвертого вида на одну единицу, то это уменьшит прибыль на 9 денежных единиц.

Ответ:

1.Максимальная прибыль предприятия рассматриваемой задачи составляет z=2540, которое достигается при производственной программе Х(35,0,10,0,0,0,9). При этом первый и второй ресурсы будут использованы полностью, т. е. первый и второй ресурсы образуют «узкие места производства»: х5=0,х6=0, а третий ресурс будет иметь остаток: х7=9.

2. двойственные оценки ресурсов составляют: у1=7, у2=8, у3=0, что говорит о том, что добавление одной единицы первого ресурса обеспечит прирост прибыли в 7 денежных единиц, а добавление одной единицы второго ресурса обеспечит прирост прибыли в 8 денежные единицы.

 

Транспортная задача

Условие задачи:

Однородный продукт, сосредоточенный на трех складах фирмы в количествах a1, a2, a3 (55, 60, 48) единиц, необходимо распределить между четырьмя магазинами, которым необходимо соответственно b1, b2, b3, b4 единиц продукта. Стоимость перевозки единицы продукта из i-го пункта отправления (i = 1, 2, 3) в j-й пункт назначения (j = 1, 2, 3, 4) равна cij и известна для всех маршрутов.

Вектор запаса продуктов на складах

вектор запаса продукта магазинами

=(36 44 25 50)

и матрица транспортных тарифов известны

c=

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

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

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

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

Решение:

1. Исходя из условий задачи, каждый поставщик должен дать ровно столько продукции, столько у него есть, а каждый потребитель должен получить ровно столько продукции, сколько ему требуется, т.е. ∑аi=∑bi. В случае ∑аi≠∑bi, то транспортная задача линейного программирования называется открытой.

Общий объем продукта в нашей задаче в пунктах производства равен:

∑аi=55+60+48=163,

всем потребителям требуется продукта:

∑bi=36+44+25+50=155

Т. е. имеем открытую модель транспортной задачи. ∑аi=163>∑bi=155.

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

∑аi-∑bi=163-155=8 -единиц,

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

2. Экономико-мате­ма­тическая модель транспортной задачи представляется обычно в виде транспортной таблицы или матрицы.

Исходная транспортная матрица

  В1 В2 В3 В4 В5
А1   4   3   4   5   0
А2   8   5   3   2   0
А3   9   8   2   5   0

3. Построение опорного плана

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

Для построения опорного плана используем метод северо-западного угла:

 

  В1 В2 В3 В4 В5
А1 4 3   4   5   0
А2   8 5 3 2   0
А3   9   8   2 5 0
                     

F=36*4+19*3+25*5+25*3+0*2+10*2+40*5+8*0=621

После расстановки корреспонденции матрица проверяется на вырождение, т. е. должно выполняться условие m+n-1=N баз,

 

где m – количество строк, n – количество столбцов, Nбаз – количество базисных клеток.

Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно сумме строк и столбцов без единицы. В нашем случае это условие соблюдается: 7 = 5 + 3 – 1. План транспортной задачи, отвечающий условию (n + m – 1) называют базисным. Базисными также называются клетки матрицы, содержащие поставки. Клетки, в которых поставки отсутствуют, называются небазисными.

Построим первое базисное допустимое решение по правилу наименьшего элемента в матрице:

  В1 В2 В3 В4 В5
А1 4 3   4   5   0
А2 8   5   3 2   0
А3 9   8 2   5 0
           

F=11*4+10*8+15*9+44*3+25*2+50*2+8*0=541ткм

Проверяем матрицу на вырождение: 7=5+3-1- условие выполняется, при чем грузооборот или функционал транспортной задачи вычисленный по правилу наименьшего элемента в матрице меньше, чем вычисленный по правилу северо-западного угла. Поэтому принимаем в качестве базисного решения: решение вычисленное по правилу наименьшего элемента в матрице.

4. Проверка плана на оптимальность.

4.1. Расчет потенциалов.

Потенциалы – это такие числа, которые по определенным правилам назначаются каждой строке и каждому столбцу. Потенциалы строк обозначим ui, потенциалы столбцовvj. Они могут принимать любые значения.

Выбираем базисную клетку с максимальным расстоянием. В нашей матрице это клетка А3В1. Присвоим строке, в которой находится эта клетка, потенциал, равный 0 (u3 = 0). Далее можно рассчитать потенциалы столбцов по базисным клеткам строки 3 по формуле: vj=ui+cij

Потенциал первого столбца v1 = u3 + c31 = 0 + 9 = 9;

третьего: v3 = u2 + c23 = 0 + 2 = 2;

пятого: v5 = u2 + c25 = 0 + 0 =0.

Рассчитанные потенциалы записываем напротив соответствующих столбцов ниже матрицы. Поскольку по всем базисным клеткам строки 3 потенциалы столбов найдены, переходим к расчету потенциалов строк.

Потенциал строки 1 рассчитываем по найденному потенциалу столбца 1 и базисной клетке А1В1 по формуле ui = vj -cij,

Где u1 = v1 – c11 = 9 –4 = 5.

Для строки 2 потенциал будет равен:

u2 = v1 – c21 = 9 – 8 = 1.

Также рассчитываем потенциалы для всех строк и столбцов.





Читайте также:


Рекомендуемые страницы:


Читайте также:
Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной...
Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (2329)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.023 сек.)