Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Кафедра «ЭКОНОМИКА И МЕНЕДЖМЕНТ»
КОНТРОЛЬНАЯ РАБОТА
по дисциплине
«Исследование операций в экономике»
Выполнил (а): Другалева Н.Г., ИВЭ-22
Руководитель: Глызина М.П.
Ростов-на-Дону
2013 г
Метод множителей Лагранжа является одним из методов, которые позволяют решать задачи нелинейного программирования.
Нелинейное программирование-это раздел математического программирования, изучающий методы решения экстремальных задач с нелинейной целевой функцией и областью допустимых решений, определенной нелинейными ограничениями. В экономике это соответствует тому, что результаты (эффективность) возрастают или убывают непропорционально изменению масштабов использования ресурсов (или, что то же самое, масштабов производства): напр., из-за деления издержек производства на предприятиях на переменные и условно-постоянные; из-за насыщения спроса на товары, когда каждую следующую единицу продать труднее, чем предыдущую и т. д.
Задача нелинейного программирования ставится как задача нахождения оптимума определенной целевой функции
F(x1,…xn), F (x) → max
при выполнении условий
gj(x1,…xn)≥0,, g (x) ≤ b, x ≥ 0
где x —вектор искомых переменных;
F (x) —целевая функция;
g (x) — функция ограничений (непрерывно дифференцируемая);
b — вектор констант ограничений.
Решение задачи нелинейного программирования (глобальный максимум или минимум) может принадлежать либо границе, либо внутренней части допустимого множества.
В отличие от задачи линейного программирования, в задаче программирования нелинейного оптимум не обязательно лежит на границе области, определенной ограничениями. Иначе говоря, задача состоит в выборе таких неотрицательных значений переменных, подчиненных системе ограничений в форме неравенств, при которых достигается максимум (или минимум) данной функции. При этом не оговариваются формы ни целевой функции, ни неравенств. Могут быть разные случаи: целевая функция нелинейная, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) нелинейные; и целевая функция, и ограничения нелинейные.
Задача нелинейного программирования встречается в естественных науках, технике, экономике, математике, в сфере деловых отношений и в науке управления государством.
Нелинейное программирование, например, связано с основной экономической задачей. Так в задаче о распределении ограниченных ресурсов максимизируют либо эффективность, либо, если изучается потребитель, потребление при наличии ограничений, которые выражают условия недостатка ресурсов. В такой общей постановке математическая формулировка задачи может оказаться невозможной, но в конкретных применениях количественный вид всех функций может быть определен непосредственно. Например, промышленное предприятие производит изделия из пластмассы. Эффективность производства здесь оценивается прибылью, а ограничения интерпретируются как наличная рабочая сила, производственные площади, производительность оборудования и т.д.
Нелинейные задачи сложны, часто их упрощают тем, что приводят к линейным. Для этого условно принимают, что на том или ином участке целевая функция возрастает или убывает пропорционально изменению независимых переменных. Такой подход называется методом кусочно-линейных приближений, он применим, однако, лишь к некоторым видам нелинейных задач.
Нелинейные задачи в определенных условиях решаются с помощью функции Лагранжа: найдя ее седловую точку, тем самым находят и решение задачи. Среди вычислительных алгоритмов Н. п. большое место занимают градиентные методы. Универсального же метода для нелинейных задач нет и, по-видимому, может не быть, поскольку они чрезвычайно разнообразны. Особенно трудно решаются многоэкстремальные задачи.
Одним из методов, которые позволяют свести задачу нелинейного программирования к решению системы уравнений, является метод неопределенных множителей Лагранжа.
С помощью метода множителей Лагранжа по существу устанавливаются необходимые условия, позволяющие идентифицировать точки оптимума в задачах оптимизации с ограничениями в виде ра венств. При этом задача с ограничениями преобразуется в эквива лентную задачу безусловной оптимизации, в которой фигурируют некоторые неизвестные параметры, называемые множителями Ла гранжа.
Метод множителей Лагранжа заключается в сведении задач на условный экстремум к задачам на безусловный экстремум вспомогательной функции — т. н. функции Лагранжа.
Для задачи об экстремуме функции f (х1, x2,..., xn) при условиях (уравнениях связи) φi(x1, x2, ..., xn) = 0, i = 1, 2,..., m, функция Лагранжа имеет вид
L(x1,x2…xn,λ1,λ2,…λm)=f(x1,x2…xn)+∑i-1mλiφi (x1,x2…xn)
Множители λ1, λ2, ..., λm наз. множителями Лагранжа.
Если величины x1, x2, ..., xn, λ1, λ2, ..., λm суть решения уравнений, определяющих стационарные точки функции Лагранжа, а именно, для дифференцируемых функций являются решениями системы уравнений
, i=1,…n ,
=0 , i=1,…m,
то при достаточно общих предположениях x1, x2, ..., xn доставляют экстремум функции f.
Рассмотрим задачу минимизации функции n переменных с учетом одного ограничения в виде равенства:
Минимизировать f(x1,x2…xn) (1)
при ограничениях h1(x1,x2…xn)=0 (2)
В соответствии с методом множителей Лагранжа эта задача преобразуется в следующую задачу безусловной оптимизации:
минимизировать L(x,λ)=f(x)-λ*h(x) (3)
где Функция L(х;λ) называется функцией Лагранжа,
λ — неизвестная постоянная, которая носит название множителя Лагранжа. На знак λ никаких требований не накладывается.
Пусть при заданном значении λ=λ0 безусловный минимум функции L(x,λ) по х достигается в точке x=x0 и x0 удовлетворяет уравнению h1(x0)=0. Тогда, как нетрудно видеть, x0 минимизирует (1) с учетом (2), поскольку для всех значений х, удовлетворяющих (2), h1(x)=0 и L(x,λ)=min f(x).
Разумеется, необходимо подобрать значение λ=λ0 таким образом, чтобы координата точки безусловного минимума х0 удовлетворяла равенству (2). Это можно сделать, если, рассматривая λ как переменную, найти безусловный минимум функции (3) в виде функции λ, а затем выбрать значение λ, при котором выполняется равенство (2). Проиллюстрируем это на конкретном примере.
Минимизировать f(x)=x12+x22=0
при ограничении h1(x)=2x1+x2-2=0=0
Соответствующая задача безусловной оптимизации записывается в следующем виде:
минимизировать L(x,λ)=x12+x22-λ(2x1+x2-2)
Решение. Приравняв две компоненты градиента L к нулю, получим
→ x10=λ
→ x20=λ/2
Для того чтобы проверить, соответствует ли стационарная точка х° минимуму, вычислим элементы матрицы Гессе функции L(х;u), рассматриваемой как функция х,
HL(x)=,
которая оказывается положительно определенной.
Это означает, что L(х,u) — выпуклая функция х. Следовательно, координаты x10=λ, x20=λ/2 определяют точку глобального минимума. Оптимальное значение λ находится путем подстановки значений x10и x20в уравнение2x1+x2=2, откуда 2λ+λ/2=2 или λ0=4/5. Таким образом, условный минимум достигается при x10=4/5 и x20=2/5 и равен min f(x)=4/5.
При решении задачи из примера мы рассматривали L(х;λ) как функцию двух переменных x1и x2и, кроме того, предполагали, что значение параметра λ выбрано так, чтобы выполнялось ограни чение. Если же решение системы
, j=1,2,3,…,n
в виде явных функций λ получить нельзя, то значения х и λ находятся путем решения следующей системы, состоящей из n+1 уравнений с n+1 неизвестными:
, j=1,2,3,…,n., h1(x)=0
Для нахождения всех возможных решений данной системы можно использовать численные методы поиска (например, метод Ньютона). Для каждого из решений () следует вычислить элементы матрицы Гессе функции L, рассматриваемой как функция х, и выяснить, является ли эта матрица положительно определенной (локальный минимум) или отрицательно определенной (локальный максимум).
Метод множителей Лагранжа можно распространить на случай, когда задача имеет несколько ограничений в виде равенств. Рассмотрим общую задачу, в которой требуется
Минимизировать f(x)
при ограничениях hk =0, k=1, 2, ..., К.
Функция Лагранжа принимает следующий вид:
L(x,λ)=f(x)-
Здесь λ1, λ2, ..., λk —множители Лагранжа, т.е. неизвестные параметры, значения которых необходимо определить. Приравнивая частные производные L по х к нулю, получаем следующую систему n уравнении с n неизвестными:
………..
Если найти решение приведенной выше системы в виде функций вектора λ оказывается затруднительным, то можно расширить систему путем включения в нее ограничений в виде равенств
h1(x)=0
h2(x)=0
hK(x)=0
Решение расширенной системы, состоящей из n+К уравнений с n+К неизвестными, определяет стационарную точку функции L. Затем реализуется процедура проверки на минимум или максимум, которая проводится на основе вычисления элементов матрицы Гессе функции L, рассматриваемой как функция х, подобно тому, как это было проделано в случае задачи с одним ограничением. Для некоторых задач расширенная система n+К уравнений с n+K неизвестными может не иметь решений, и метод множителей Лагранжа оказывается неприменимым. Следует, однако, отметить, что такие задачи на практике встречаются достаточно редко.
Рассмотрим частный случай общей задачи нелинейного программирования, предполагая, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности переменных и и - функции непрерывные вместе со своими частными производными
max (min) (4)
(5)
Данную задачу называют задачей на условный экстремум или классической задачей оптимизации.
Чтобы найти решение этой задачи, вводят набор переменных называемых множителями Лагранжа, составляют функцию Лагранжа
(6)
находят частные производные и рассматривают систему n+m уравнений
(7)
с n+m неизвестными Всякое решение системы уравнений (7) определяет точку в которой может иметь место экстремум функции . Следовательно решив систему уравнений (7), получают все точки, в которых функция (6) может иметь экстремальные значения.
Алгоритм метода множителей Лагранжа
1. Составляем функцию Лагранжа.
2. Находим частные производные от функции Лагранжа по переменным xJ,λi и приравниваем их нулю.
3. Решаем систему уравнений (7), находим точки, в которых целевая функция задачи может иметь экстремум.
4. Среди точек, подозрительных на экстремум, находим такие, в которых достигается экстремум, и вычисляем значения функции (6) в этих точках.
Пример .
Исходные данные: По плану производства продукции предприятию необходимо изготовить 180 изделий. Эти изделия могут быть изготовлены двумя технологическими способами. При производстве x1 изделий 1 способом затраты равны 4x1+x12 руб., а при изготовлении x2 изделий 2 способом они составляют 8x2+x22 руб. Определить сколько изделий каждым из способов следует изготовить, чтобы затраты на производство продукции были минимальными.
Решение:
Целевая функция для поставленной задачи имеет вид
min при условиях x1+x2=180, x2≥0.
1. Составляем функцию Лагранжа
.
2. Вычисляем частные производные по x1, x2, λ и приравниваем их нулю:
3. Решая полученную систему уравнений, находим x1=91,x2=89
4. Сделав замену в целевой функции x2=180-x1 , получим функцию от одной переменной, а именно f1=4x1+x12+8(180-x1)+(180-x1)2
Вычисляем или 4x1-364=0 ,
откуда имеем x1*=91, x2*=89.
Ответ: Количество изделий изготовленных первым способом равно х1=91, вторым способом х2=89 при этом значение целевой функции равно 17278 руб.
Условия задачи:
Предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов.
Известны технологическая матрица
А=
затрат ресурсов на производство единицы каждого вида продукции [элемент aij этой матрицы равен количеству ресурса i-го вида (i = 1, 2, 3), которое необходимо затратить в процессе производства единицы продукции j-го вида (j = 1, 2, 3, 4)],
вектор
Объем ресурсов и вектор
удельной прибыли на единицу продукции.
Требуется составить производственную программу, обеспечивающую предприятию наибольшую прибыль с учетом ограниченности запасов ресурсов.
Для этого необходимо обсудить экономическое содержание линейной производственной задачи и сформулировать ее математическую модель, преобразовать данную задачу к виду основной задачи линейного программирования, решить ее симплексным методом, обосновывая каждый шаг вычислительного процесса, найти оптимальную производственную программу, максимальную прибыль, остатки ресурсов различных видов и определить узкие места производства (дефицитные ресурсы). Затем требуется сформулировать задачу, двойственную линейной производственной задаче, обсудить ее экономическое содержание и записать математическую модель, после чего найти решение двойственной задачи, пользуясь второй основной теоремой двойственности, обосновав экономический смысл этой теоремы.
Указать оптимальную производственную программу и оценки технологий, максимальную прибыль и минимальную суммарную оценку всех ресурсов, остатки и двойственные оценки ресурсов и обсудить экономический смысл всех этих величин.
Решение:
Исходя из условий и исходных данных экономико-математическая модель задачи примет вид: найти такой план Х(х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) примет наибольшее значение.
Эту задачу будем решать методом последовательного улучшения плана – симплексным методом.
Воспользуемся тем, что правые части всех уравнений системы (3) неотрицательны, а сама система имеет такой вид, что дополнительные переменные являются базисными. Приравняв к нулю свободные переменные x1, x2, x3, x4, получаем базисное неотрицательное решение: х1=0, х2=0, х3=0, х4=0, х5=180, х6=160, х7=109.
Исходная симплексная таблица
|
1ё |
Базис |
H |
30 |
11 |
45 |
6 |
0 |
0 |
0 |
Пояснения |
|
с |
|
|
х1 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
|
|
|
х5 |
180 |
4 |
2 |
4 |
1 |
1 |
0 |
0 |
45 |
|
|
х6 |
160 |
4 |
0 |
2 |
2 |
0 |
1 |
0 |
40 |
|
|
х7 |
109 |
2 |
4 |
3 |
0 |
0 |
0 |
1 |
54,5 |
|
|
|
0 |
-60 |
-12 |
-44 |
-17 |
0 |
0 |
0 |
|
На данной итерации:
- признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).
- признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).
Так как найденное базисное решение не содержит отрицательных компонент, то оно является допустимым.
- найденное базисное решение не является оптимальным, так как согласно признаку оптимальности (признак 4) в строке целевой функции не должно быть отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, согласно алгоритму симплекс-метода переходим к следующему этапу- определение разрешающего элемента.
Определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х1» содержит наименьший элемент (–60) в сравнении с другими колонками. Следовательно, ее принимаем в качестве разрешенной.
Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной. В нашем случае, наименьшее положительное оценочное отношение 40 соответствует строке «х6», следовательно, она будет разрешающей.
Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент а21=4, который расположен на пересечении строки «х6» и колонки «х1».
Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х6 и х1, в новой симплекс-таблице их меняем местами
Элементы разрешающей строки исходной таблицы делим на разрешающий элемент данной симплекс-таблицы, результаты вписываются в аналогичные ячейки новой симплекс-таблицы (итерация2). Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».
В таблице мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем, а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы ), а в числителе произведение двух других неиспользованных вершин.
В результате данных преобразований получили новую симплекс- таблицу(итерация2).
Итерация2.
|
|
Базис |
H |
30 |
11 |
45 |
6 |
0 |
0 |
0 |
Пояснения |
|
|
|
|
х6 |
х2 |
х3 |
х4 |
х5 |
х6 |
х7 |
|
|
|
х5 |
20 |
0 |
2,00 |
2 |
-1 |
1,00 |
-1 |
0 |
10 |
|
60 |
х1 |
40 |
1 |
0 |
0,5 |
0,5 |
0 |
0,25 |
0 |
80 |
|
|
х7 |
29 |
0 |
4,0 |
2 |
-1 |
0,0 |
-0,5 |
1 |
14,5 |
|
|
|
2400 |
0 |
-12 |
-14 |
13 |
0 |
15 |
0 |
|
В результате проведенных симплекс-преобразований получили новое базисное решение Х(х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 |
30 |
11 |
45 |
6 |
0 |
0 |
0 |
Пояснения |
|
|
|
|
х1 |
х2 |
х5 |
х4 |
х5 |
х6 |
х7 |
|
|
45 |
х3 |
10 |
0 |
1,00 |
1 |
-0,5 |
0,50 |
-0,5 |
0 |
|
|
30 |
х1 |
35 |
1 |
-0,5 |
0 |
0,75 |
-0,25 |
0,5 |
0 |
|
|
|
х7 |
9 |
0 |
2,0 |
0 |
0 |
-1,0 |
0,5 |
1 |
|
|
|
|
2540 |
0 |
2 |
0 |
6 |
7 |
8 |
0 |
|
В результате проведенных симплекс-преобразований получили новое базисное решение Х(х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).
Задача, двойственная линейной производственной задаче, может заключаться в оценке выгоды от продажи сырья, используемого в производстве, на сторону.
Нами была рассмотрена линейная производственная задача по выпуску четырех видов продукции с использованием трех видов ресурсов по заданным технологиям.
Предположим, некий предприниматель, занимающийся производством других видов продукции с использованием трех таких же видов ресурсов, предлагает «уступить» ему все имеющиеся ресурсы и обещает платить 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 -единиц,
При этом тарифы на перевозку продукта в этот пункт потребления будут равны нулю, т. к. фактического перемещения продукта не происходит.
Исходная транспортная матрица
|
|
В1 |
В2 |
В3 |
В4 |
В5 |
||||||
|
36 |
44 |
25 |
50 |
8 |
|||||||
|
А1 |
55 |
|
4 |
|
3 |
|
4 |
|
5 |
|
0 |
|
А2 |
60 |
|
8 |
|
5 |
|
3 |
|
2 |
|
0 |
|
А3 |
48 |
|
9 |
|
8 |
|
2 |
|
5 |
|
0 |
Опорным, называется любой допустимый, как правило, не оптимальный план, который является исходным для последующего решения.
Для построения опорного плана используем метод северо-западного угла:
|
|
В1 |
В2 |
В3 |
В4 |
В5 |
||||||
|
36 |
44 |
25 |
50 |
8 |
|||||||
|
А1 |
55 |
36 |
4 |
19 |
3 |
|
4 |
|
5 |
|
0 |
|
А2 |
60 |
|
8 |
25 |
5 |
25 |
3 |
10 |
2 |
|
0 |
|
А3 |
48 |
|
9 |
|
8 |
2 |
40 |
5 |
8 |
0 |
|
|
|
163 |
|
|
|
|
|
|
|
|
|
|
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 |
||||||
|
36 |
44 |
25 |
50 |
8 |
|||||||
|
А1 |
55 |
11 |
4 |
44 |
3 |
|
4 |
|
5 |
|
0 |
|
А2 |
60 |
10 |
8 |
|
5 |
|
3 |
50 |
2 |
|
0 |
|
А3 |
48 |
15 |
9 |
|
8 |
25 |
2 |
|
5 |
8 |
0 |
|
|
163 |
F=11*4+10*8+15*9+44*3+25*2+50*2+8*0=541ткм
Проверяем матрицу на вырождение: 7=5+3-1- условие выполняется, при чем грузооборот или функционал транспортной задачи вычисленный по правилу наименьшего элемента в матрице меньше, чем вычисленный по правилу северо-западного угла. Поэтому принимаем в качестве базисного решения: решение вычисленное по правилу наименьшего элемента в матрице.
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.
Также рассчитываем потенциалы для всех строк и столбцов.
Расстановка потенциалов
|
|
В1 |
В2 |
В3 |
В4 |
В5 |
||||||||
|
36 |
44 |
25 |
50 |
8 |
|||||||||
|
А1 |
55 |
11 |
4 |
44 |
3 |
|
4 |
|
5 |
|
0 |
u1= |
5 |
|
А2 |
60 |
10 |
8 |
|
5 |
|
3 |
50 |
2 |
|
0 |
u2= |
1 |
|
А3 |
48 |
15 |
9 |
|
8 |
25 |
2 |
|
5 |
8 |
0 |
u3= |
0 |
|
|
163 |
v |
9 |
|
2 |
|
2 |
|
-1 |
|
0 |
4.2. Проверка небазисных клеток на соответствие их условию оптимальности.
Оптимальный план транспортной задачи должен отвечать критерию оптимальности, который выражается в том, соответствуют ли небазисные клетки матрицы условию, формулируемому следующим выражением: vj-ui≤cij
Если это условие для всех небазисных клеток выполняется, то план является оптимальным, а если нет, хотя бы для одной клетки, то план не оптимален. Иначе говоря, существует некоторый план с меньшим функционалом. Разность потенциалов может интерпретироваться как некоторая условная цена перевозки единицы продукции по маршруту, связывающему соответствующие станции «i» и «j». Если она ниже cij, значит, использование данного маршрута не улучшит план, а если cij ниже разности потенциалов, т. е. условие не выполняется, следовательно, существует план лучше рассчитанного, который необходимо отыскать.
Проверяем условие для нашей таблицы:
Клетка А2В2: 2 – 1 < 5, условие выполняется.
Клетка А3В2: 2 – 0 < 8, условие выполняется
Клетка А1В3: 2 – 5 < 4 условие выполняется
Клетка А2В3: 2 – 1 < 3, условие выполняется
Клетка А1В4: -1 – 5 < 5 условие выполняется
Клетка А3В4: -1 – 0 < 5 условие выполняется
Клетка А1В5: 0 – 5 < 0 условие выполняется
Клетка А2В5: 0 – 1 < 0 условие выполняется
Для всех небазисных клеток условие выполняется, поэтому рассматриваемый план будет оптимален.
Функционал F'' оптимального плана равен 541 ткм. Таким образом, получен план перевозок, обеспечивающий минимальный объем перевозочной работы для транспортировки всего груза между станциями погрузки и выгрузки.
Анализ результатов решения показывает следующее. Предприятия А1 , А2 отправляют реальным потребителям В1, В2, В3, В4 в полном объеме требуемого продукта. Иначе говоря, мощности предприятий А1 , А2 полностью вошли в оптимальный план. Следовательно, загрузка мощностей этого предприятия равна 100 %. Предприятие А3 реальным потребителям В1,В3 отправляет 15 и 25 единиц продукции соответственно. Оставшиеся мощности 8 единиц продукции, приходятся на фиктивного потребителя. Это говорит о том, что мощности А3 востребованы не полностью. Следовательно, загрузка А3 составляет 83,3 %. Предприятия, которые не полностью используют производственную мощность, необходимо переориентировать на выпуск нового вида продукции или закрыть.
Теперь найдем решение транспортной задачи в случае, если от первого поставщика ко второму потребителю должна быть доставлена ровно одна единица продукции, а поставки от второго поставщика третьему потребителю запрещены.
|
|
В1 |
В2 |
В3 |
В4 |
В5 |
|||||||
|
36 |
44 |
25 |
50 |
8 |
u |
|||||||
|
А1 |
55 |
36 |
4 |
1 |
3 |
|
4 |
18 |
5 |
|
0 |
5 |
|
А2 |
60 |
|
8 |
35 |
5 |
|
3 |
25 |
2 |
|
0 |
3 |
|
А3 |
48 |
|
9 |
8 |
8 |
25 |
2 |
7 |
5 |
8 |
0 |
0 |
|
|
163 |
v |
1 |
|
8 |
|
2 |
|
5 |
|
0 |
F=36*4+1*3+35*5+8*8+25*2+25*2+18*5+7*5+8*0=611ткм
Проверяем матрицу на вырождение: 9≠5+3-1=7- условие не выполняется.
Проверяем матрицу по критерию на оптимальность:
Клетка А2В1: 1 – 3 < 8, условие выполняется.
Клетка А3В1: 1 – 0 < 8, условие выполняется
Клетка А1В3: 2 – 5 < 4 условие выполняется
Клетка А2В3: 2 – 3 < 3, условие выполняется
Клетка А1В5: 0 – 5 < 0 условие выполняется
Клетка А2В5: 0 – 3 < 0 условие выполняется
Для всех небазисных клеток условие выполняется, поэтому рассматриваемый план будет оптимален.
Ответ: Оптимальный план перевозок, при котором запросы магазинов были бы удовлетворены в наибольшей степени за счет имеющегося на складах количества продукта, и при этом обязательно были бы удовлетворены запросы первого магазина, а общие транспортные расходы по доставке продукта были минимальны, составляет
|
|
В1 |
В2 |
В3 |
В4 |
В5 |
||||||
|
36 |
44 |
25 |
50 |
8 |
|||||||
|
А1 |
55 |
11 |
4 |
44 |
3 |
|
4 |
|
5 |
|
0 |
|
А2 |
60 |
10 |
8 |
|
5 |
|
3 |
50 |
2 |
|
0 |
|
А3 |
48 |
15 |
9 |
|
8 |
25 |
2 |
|
5 |
8 |
0 |
|
|
163 |
Функционал F'' оптимального плана равен 541 ткм.
В условиях, когда от первого поставщика ко второму потребителю должна быть доставлена ровно одна единица продукции, а поставки от второго поставщика третьему потребителю запрещены, оптимальный план перевозок составляет
|
|
В1 |
В2 |
В3 |
В4 |
В5 |
||||||
|
36 |
44 |
25 |
50 |
8 |
|||||||
|
А1 |
55 |
36 |
4 |
1 |
3 |
|
4 |
18 |
5 |
|
0 |
|
А2 |
60 |
|
8 |
35 |
5 |
|
3 |
25 |
2 |
|
0 |
|
А3 |
48 |
|
9 |
8 |
8 |
25 |
2 |
7 |
5 |
8 |
0 |
Функционал F'' оптимального плана равен 611 ткм., при этом матрица вырождаемая и функционал больше, чем при плане перевозок без ограничений.
3. Динамическая задача управления производственными запасами.
Условие задачи: Рассматривается трехэтапная система управления запасами с дискретной продукцией и динамическим детерминированным спросом.
Заявки потребителей на продукцию составляют на этапе j равен dj единиц (j = 1, 2, 3).К началу первого этапа на складе имеется только y1 единицы продукции. Затраты на хранение единицы продукции на этапе j равны hj.
Затраты на производство xj единиц продукции на j-м этапе определяются
Функцией ϕ=хj2+хj+5, j=1,2,3.
Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими.
Для этого необходимо составить математическую модель динамической задачи управления производством и запасами и решить ее методом динамического программирования, обосновывая каждый шаг вычислительного процесса. Исходные данные приведены в табл.
|
№ вар. |
Исходные данные |
|||||||||
|
d1 |
d2 |
d3 |
a |
b |
c |
h1 |
h2 |
h3 |
y1 |
|
|
17 |
2 |
2 |
2 |
1 |
1 |
5 |
1 |
2 |
4 |
2 |
Решение:
Воспользовавшись рекуррентными соотношениями, последовательно вычисляем F1(y2 ), F2 (y3 ), F3 (y4 ) и соответственно находим x1* (y2 ) , x2*(y3 ) , x3* (y4 ) .
F1(y2 )=min(ax12+bx1+c+h1*y2) (3.1)
имеем F1(y2 )=( x12+x1+5+ y2).
Учтем, что согласно условия: 0 ≤y2≤d2+d3+…+dn (3.2)
Параметр состояния у=у2 может принимать целые значения на отрезке
0≤y2≤ d2+d3, 0≤y2≤ 2+2=4, т.е. y2=0,1,2,3,4.
При этом каждому значению параметра состояния должна отвечать определенная область изменения управления х1, характеризуемая условием:
0 ≤х1≤d1+y2,
0≤х1≤2+ y2.
Однако объем производства на первом этапе х1 не может быть меньше 0, т.к. спрос d1=2, а исходный запас y1=2.
Кроме того, из балансового уравнения:
y1+x1-d1=y2 (3.3)
непосредственно следует, что объем производства связан со значением параметра состояния y=y2 соотношением:
х1=y2+d1-y1= y2+2-2= y2.
В этом и состоит особенность первого этапа. Если задан уровень запаса к началу первого этапа, то каждому значению y2 отвечает единственное значение х1 и поэтому:
F1(y2 )=W(y2,х1)
Придавая х2 различные целые значения от 0 до 4 и учитывая х1= y2 находим:
y2=0 х1=0 W(0;0)=02+0+5+0=5.
y2=1 х1=1 W(1;1)=12+1+5+1=8
y2=2 х1=2 W(2;2)=22+2+5+2=13
y2=3 х1=3 W(3;3)=32+3+5+3=20
y2=4 х1=4 W(4;4)=42+4+5+4=29
Значения функции состояния F1(y2 ) представим в таблице 1.
Таблица1.
|
y =y2 |
0 |
1 |
2 |
3 |
4 |
|
F1(y2 ) |
5 |
8 |
13 |
20 |
29 |
|
x1* (y2 ) |
0 |
1 |
2 |
3 |
4 |
Fk(y=yk+1)=min Wk(yk+1,хk),
F2(y3 )= min(ax22+bx2+c+h2y3+ F1(y2 ))=min (x22+x2+5+2y3+ F1(y2 )),
Здесь минимум берется по единственной переменной х2, которая может изменяться, согласно: 0≤хk≤dk+yk+1, 0≤х2≤d2+y3 или 0≤х2≤2+y3,
Где верхняя граница зависит от параметра состояния y=y3, который принимает значения на отрезке: 0≤y3≤d3, т.е. 0≤y3≤2,
А аргумент y2 в соотношении F2(y3 )= min (x22+x2+5+2y3+ F1(y2 )), связан с y3 и x2 балансовым уравнением: y2+х2-d2= y3, откуда y2= y3+ d2-х2= y3+ 2-х2.
Придавая параметру состояния y=y3 различные состояния от 0 до 2, будем последовательно вычислять W2(y.x2), а затем определять F2(y3 ) и х2*(y).
Положим что y= y3=2, тогда 0≤х2≤2+2=4,
Т.е. х2 может принимать значения от 0 до 4 и каждому значению х2 отвечает определенное значение y2, вычисляемое по формуле:
y2 = y3 +d2-х2, y2 = y3 +2-х2=2+2-х2=4-х2.
Последовательно вычисляем:
Если х2=0, то y2=4-0=4 W2(2,0)=02+0+5+2*2+F1(4)=5+4+29=38
х2=1, то y2=4-1=3 W2(2,1)=12+1+5+2*2+F1(3)=2+5+4+20=31
х2=2, то y2=4-2=2 W2(2,2)=22+2+5+2*2+F1(2)=15+13=28
х2=3, то y2=4-3=1 W2(2,3)=32+3+5+2*2+F1(1)=21+8=29
х2=4, то y2=4-4=0 W2(2,4)=42+4+5+2*2+F1(0)=29+5=34
Наименьшее значение из полученных W2- это F2(y3=2)=28, при чем минимум достигается при значении х2*(y3=2)=2.
Аналогично делаем вычисления для значения параметра y=y3=0 и y=y3=1 и находим F2(y3=0) х2*(y3=0), F2(y3=1) х2*(y3=1).
Если y=y3=0, 0≤х2≤2+0=2
х2 может принимать значения от 0 до 2 и каждому значению х2 отвечает определенное значение y2, вычисляемое по формуле:
y2 = y3 +d2-х2, y2 = y3 +2-х2=0+2-х2=2-х2.
Если х2=0, то y2=2-0=2 W2(0,0)=02+0+5+2*0+F1(2)=5+ 13=18
х2=1, то y2=2-1=1 W2(0,1)=12+1+5+2*0+F1(1)=2+5+8=15
х2=2, то y2=2-2=0 W2(0,2)=22+2+5+2*0+F1(0)=6+5+0+5=16
Наименьшее значение из полученных W2- это F2(y3=0)=15, при чем минимум достигается при значении х2*(y3=0)=1.
Если y=y3=1, 0≤х2≤2+1=3
х2 может принимать значения от 0 до 3 и каждому значению х2 отвечает определенное значение y2, вычисляемое по формуле:
y2 = y3 +d2-х2, y2 = y3 +2-х2=1+2-х2=3-х2.
Если х2=0, то y2=3-0=3 W2(1,0)=02+0+5+2*1+F1(3)=5+2+ 20=27
х2=1, то y2=3-1=2 W2(1,1)=12+1+5+2*1+F1(2)=2+5+2+13=22
х2=2, то y2=3-2=1 W2(1,2)=22+2+5+2*1+F1(1)=6+5+2+8=21
х2=3, то y2=3-3=0 W2(1,3)=32+3+5+2*1+F1(0)=12+5+2+5=24
Наименьшее значение из полученных W2- это F2(y3=1)=21, при чем минимум достигается при значении х2*(y3=1)=2.
Внесем вычисленные данные в таблицу 2.
Таблица2.
|
0≤yk+1≤∑dj |
y=yk+1 |
0≤xk≤dk+xk+1 |
xk |
yk=yk+1+dk-xk |
W(yk+1,xk) |
|
0≤y3≤d3 |
y=y3 |
0≤x2≤d2+y3 |
х2 |
y2=y3+d2-x2 |
W(y3,x2)=x22+x2+5+2y3+ F1(y2 ) |
|
0≤y3≤2 |
y=y3 |
0≤x2≤2+y3 |
х2 |
y2=y3+2-x2 |
W(y3,x2)=x22+x2+5+2y3+ F1(y2 ) |
|
|
y=y3=0 |
0≤x2≤2 |
х2=0 |
y2=0+2-0=2 |
W2(0,0)=02+0+5+2*0+F1(2)=5+ 13=18 |
|
|
х2=1 |
y2=0+2-1=1 |
W2(0,1)=12+1+5+2*0+F1(1)=2+5+8=15 |
||
|
|
х2=2 |
y2=0+2-2=0 |
W2(0,2)=22+2+5+2*0+F1(0)=6+5+0+5=16 |
||
|
|
y=y3=1 |
0≤x2≤3 |
х2=0 |
y2=1+2-0=3 |
W2(1,0)=02+0+5+2*1+F1(3)=5+2+ 20=27 |
|
|
х2=1 |
y2=1+2-1=2 |
W2(1,1)=12+1+5+2*1+F1(2)=2+5+2+13=22 |
||
|
|
х2=2 |
y2=1+2-2=1 |
W2(1,2)=22+2+5+2*1+F1(1)=6+5+2+8=21 |
||
|
|
х2=3 |
y2=1+2-3=0 |
W2(1,3)=32+3+5+2*1+F1(0)=12+5+2+5=24 |
||
|
|
y=y3=2 |
0≤x2≤4 |
х2=0 |
y2=2+2-0=4 |
W2(2,0)=02+0+5+2*2+F1(4)=5+4+29=38 |
|
|
х2=1 |
y2=2+2-1=3 |
W2(2,1)=12+1+5+2*2+F1(3)=2+5+4+20=31 |
||
|
|
х2=2 |
y2=2+2-2=2 |
W2(2,2)=22+2+5+2*2+F1(2)=15+13=28 |
||
|
|
х2=3 |
y2=2+2-3=1 |
W2(2,3)=32+3+5+2*2+F1(1)=21+8=29 |
||
|
|
х2=4 |
y2=2+2-4=0 |
W2(2,4)=42+4+5+2*2+F1(0)=29+5=34 |
Результаты внесем в таблицу 3.
Таблица3.
|
y = y3 |
0 |
1 |
2 |
|
F2 (y= y3 ) |
15 |
21 |
28 |
|
x2* (y= y3 ) |
1 |
2 |
2 |
3. Полагаем k=3 и табулируем функцию F3(y4 )
F3(y4 )= min(ax22+bx2+c+h3y4+ F2(y3 ))=min (x22+x2+5+4y3+ F2(y3 )).
Вычисляем значение функции состояния только для одного значения аргумента y=y4, т.к. не хотим оставлять продукцию в запас в конце исследуемого периода.
F3(y4 )= min (x22+x2+5+4y3+ F2(y3 ))
0≤x3≤d3+y4, 0≤x3≤2+y4,
y3=y4+d3-x3=0+2- x3=2- x3
Придавая параметру состояния y=y4=0, вычисляем W3(y;x3) и определяем F3(y4) и x3*(y).
y=y4=0, 0≤х3≤2,
т.е. х3 может принимать значения 0,1,2 и каждому значению х3 отвечает определенное значение y3=2-х3.
Вычисления приведены в таблице 4.
Таблица 4
|
y4=0 |
y=y4 |
0≤x3≤2+y4 |
х3 |
y3=y4+2-x3 |
W(y4,x3)=x32+x3+5+4y4+ F2(y3 ) |
|
|
y=y4=0 |
0≤x3≤2 |
х3=0 |
y3=0+2-0=2 |
W2(0,0)=02+0+5+4*0+F2(2)=5+ 28=33 |
|
|
х3=1 |
y3=0+2-1=1 |
W2(0,1)=12+1+5+4*0+F2(1)=2+5+21=28 |
||
|
|
х3=2 |
y3=0+2-2=0 |
W2(0,2)=22+2+5+4*0+F2(0)=6+5+0+15=26 |
Таким образом, получили наименьшие минимальные общие затраты на производство и хранение продукции W3- это F3(y4=0)=26, и последнюю компоненту оптимального плана х3=2.
4. Для нахождения остальных компонент оптимального решения, необходимо воспользоваться обычными правилами динамического программирования.
Т.к. х3+y3-d3= y4, то 2+ y3-2=0, откуда y3=0, следовательно, из таблицы 3 - х2*=1.
Т.к. х2+y2-d2= y3, то 1+ y2-2=0, откуда y2=1, следовательно, из таблицы 1 - х1*=1.
Следовательно, получен оптимальный план производства, который имеет значения: х1=1, х2=1, х3=2
при этом оптимальный план производства обеспечивает минимальные общие затраты на производство и хранение продукции в размере 26 денежных единиц.
Проверяем выполняются ли заявки потребителей на каждом этапе :
y1+х1≥d1 2+1>2
y2+х2≥d2 1+1=2
y3+х3≥d3 0+2=2
заявки выполняются.
Суммарный объем производства и имевшегося к началу первого этапа запаса продукции равен суммарной потребности:
y1+х1+х2+х3=d1+d2+d3,
2+1+1+2=2+2+2
6=6,
причем это достигается при наименьших возможных затратах на производство и хранение продукции:
ϕ(х1)+ ϕ(х2)+ ϕ(х3)+h1y2+h2y3=F3(y4=0),
ϕ(х1)=х12+х1+5=1+1+5=7
ϕ(х2)=х22+х2+5=1+1+5=7
ϕ(х3)=х32+х1+5=22+2+5=11
7+7+11+1*1+2*0=26, 26=26
|
этап |
1 |
2 |
3 |
итого за 3 этапа |
|
имеем продукции к началу месяца, шт |
2 |
1 |
0 |
y1=2 |
|
производим в течение месяца, шт
|
1 |
1 |
2 |
x1+x2+x3=4 |
|
отпускаем заказчикам, шт |
2 |
2 |
2 |
d1+d2+d3=6 |
|
остаток к концу месяца (храним в течение текущего месяца,шт |
1 |
0 |
0 |
|
|
затраты на производство, ден. Ед. |
7 |
7 |
11 |
25 |
|
затраты на хранение, ден. Ед. |
1 |
0 |
0 |
1 |
Ответ: Следовательно, получен оптимальный план производства, который имеет значения: х1=1, х2=1, х3=2 при этом оптимальный план производства обеспечивает минимальные общие затраты на производство и хранение продукции в размере 26 денежных единиц.
Литература