Методы оптимальных решений
Экономический анализ задач с использованием теории двойственности. Математическая модель оптимального использования ресурсов. Сущность симплексного метода и решение задач линейного программирования. Определение значения функции максимальной прибыли.
Рубрика | Экономико-математическое моделирование |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 23.11.2016 |
Размер файла | 83,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное государственное образовательное учреждение высшего профессионального образования
"Пермская государственная сельскохозяйственная академия имени академика Д.Н. Прянишникова"
Контрольная работа
Методы оптимальных решений
1. Экономический анализ задач с использованием теории двойственности
Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель
при ограничениях:
Двойственная задача имеет вид
при ограничениях:
Теорема 3. Значения переменных уi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений исходной задачи на оптимальное значение ее целевой функции, т.е.
Примем Li ? ДLi, bi ? Дbi, тогда
ДLi ? yi * Дbi.
Для задачи оптимального использования сырья это уравнение показывает, что при изменении i-го ресурса оптимальный доход является линейной функцией от его приращения, причем коэффициентом служит уi -- i-я компонента оптимального решения двойственной задачи. Если yi мало, то значительному увеличению i-го ресурса будет соответствовать небольшое увеличение оптимального дохода и ценность ресурса невелика.
Если yi = 0, то при увеличении i-го ресурса оптимальный доход остается неизменным и ценность этого ресурса равна нулю. В самом деле, сырье, запасы которого превышают потребности в нем, не представляет ценности для производства и его оценку можно принять за нуль. Если уi велико, то незначительному увеличению i-го ресурса будет соответствовать существенное увеличение оптимального дохода и ценность ресурса высока. Уменьшение ресурса ведет к существенному сокращению выпуска продукции. Переменную уi считают некоторой характеристикой ценности i-го ресурса. В частности, при увеличении i-го ресурса на единицу (Дbi = 1) оптимальный доход возрастает на yi, что позволяет рассматривать yi как "условную цену", оценку единицы i-го ресурса, объективно обусловленную оценку.
Так как уi представляет частную производную от оптимального дохода по i-му ресурсу, то уi характеризует скорость изменения оптимального дохода при изменении i-го ресурса. С помощью yi можно определить степень влияния ограничений на значение целевой функции. Предельные значения (нижняя и верхняя границы) ограничений ресурсов, для которых yi остаются неизменными, определяются по формулам:
где xj -- значение переменной в оптимальном решении; dij -- элементы матрицы (dij) = А-1, обратной к матрице базиса оптимального решения, для которой А = (aij)mxn. Если в план включаются новые виды продукции, то их оценка находится по формуле
Если Дj < 0, то новый вид продукции улучшает план. При Дj > 0 нецелесообразно включать новый вид продукции.
2. Решение задачи симплексным методом
Симплекс-метод. Решим прямую задачу линейного программирования симплексным методом. Определим максимальное значение целевой функции (максимум прибыли, руб.)
F(X) = 60x1+125x2+30x3 при следующих условиях-ограничений. x1+x2+x3?2000 4x1+2.5x2+4.5x3?20000 0.8x1+x2+1.2x3?3000
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных. В 1-м неравенстве смысла (?) вводим базисную переменную x4. В 2-м неравенстве смысла (?) вводим базисную переменную x5. В 3-м неравенстве смысла (?) вводим базисную переменную x6. 1x1 + 1x2 + 1x3 + 1x4 + 0x5 + 0x6 = 2000 4x1 + 2.5x2 + 4.5x3 + 0x4 + 1x5 + 0x6 = 20000 0.8x1 + 1x2 + 1.2x3 + 0x4 + 0x5 + 1x6 = 3000 Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
1 |
1 |
1 |
1 |
0 |
0 |
|
4 |
2,5 |
4,5 |
0 |
1 |
0 |
|
0,8 |
1 |
1,2 |
0 |
0 |
1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Экономический смысл дополнительных переменных: дополнительные переменные задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,2000,20000,3000) Базисное решение называется допустимым, если оно неотрицательно.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x4 |
2000 |
1 |
1 |
1 |
1 |
0 |
0 |
|
x5 |
20000 |
4 |
2.5 |
4.5 |
0 |
1 |
0 |
|
x6 |
3000 |
0.8 |
1 |
1.2 |
0 |
0 |
1 |
|
F(X0) |
0 |
-60 |
-125 |
-30 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 2. Определение новой базисной переменной. В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю. 3.
2. Определение новой свободной переменной
Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
x4 |
2000 |
1 |
1 |
1 |
1 |
0 |
0 |
2000 |
|
x5 |
20000 |
4 |
2.5 |
4.5 |
0 |
1 |
0 |
8000 |
|
x6 |
3000 |
0.8 |
1 |
1.2 |
0 |
0 |
1 |
3000 |
|
F(X1) |
0 |
-60 |
-125 |
-30 |
0 |
0 |
0 |
0 |
Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4плана 0 на разрешающий элемент РЭ=1. На месте разрешающего элемента в плане получаем 1. В остальных клетках столбца x2 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x2 |
2000 |
1 |
1 |
1 |
1 |
0 |
0 |
|
x5 |
15000 |
1.5 |
0 |
2 |
-2.5 |
1 |
0 |
|
x6 |
1000 |
-0.2 |
0 |
0.2 |
-1 |
0 |
1 |
|
F(X1) |
250000 |
65 |
0 |
95 |
125 |
0 |
0 |
1. Проверка критерия оптимальности. Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x2 |
2000 |
1 |
1 |
1 |
1 |
0 |
0 |
|
x5 |
15000 |
1.5 |
0 |
2 |
-2.5 |
1 |
0 |
|
x6 |
1000 |
-0.2 |
0 |
0.2 |
-1 |
0 |
1 |
|
F(X2) |
250000 |
65 |
0 |
95 |
125 |
0 |
0 |
Оптимальный план можно записать так: x1 = 0, x2 = 2000, x3 = 0 F(X) = 60*0 + 125*2000 + 30*0 = 250000
3. Транспортная задача
Стоимость доставки единицы продукции от поставщика к потребителю располагается в правом нижнем углу ячейки.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
6 |
3 |
7 |
10 |
45 |
|
A 2 |
10 |
4 |
12 |
10 |
100 |
|
A 3 |
5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
2 |
4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Требуется составить план перевозок, при котором общая стоимость доставки продукции будет наименьшей.
Для решения задачи необходимо выполнение следующего условия: cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей. Запасы поставщиков: 45 + 100 + 20 + 75 = 240 единиц продукции. Потребность потребителей: 30 + 80 + 95 + 35 = 240 единиц продукции.
Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей, значит система закрытая.
Для решения задачи необходимо выполнение следующего условия: количество задействованных маршрутов = количество поставщиков + количество потребителей - 1.
В первую очередь, будем задействовать маршруты с наименьшей стоимостью доставки. Искомый элемент равен 2.
Для этого элемента запасы равны 75, потребности 80. Минимальным является 75, то вычитаем его.
Х42 = min (75,80) =75
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
6 |
3 |
7 |
10 |
45 |
|
A 2 |
10 |
4 |
12 |
10 |
100 |
|
A 3 |
5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75-75=0 |
|
Потребность |
30 |
80-75 5 |
95 |
35 |
Х12=min (45,5)=5
Для этого элемента запасы равны 20, потребности 30. Поскольку минимальным является 20, то вычитаем его.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
6 |
5 3 |
7 |
10 |
45 40 |
|
A 2 |
10 |
4 |
12 |
10 |
100 |
|
A 3 |
5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 0 |
|
Потребность |
30 |
5 0 |
95 |
35 |
Х31=min (20,30)=20
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
6 |
5 3 |
7 |
10 |
45 40 |
|
A 2 |
10 |
4 |
12 |
10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20-20=0 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 0 |
|
Потребность |
30 10 |
5 0 |
95 |
35 |
Искомый элемент равен 6. Для него запасы равны 40, потребности 10. Минимальным является 10, то вычитаем его.
Х11=min(40,10)=10
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
5 3 |
7 |
10 |
40-10= 30 |
|
A 2 |
10 |
4 |
12 |
10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 0 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 0 |
|
Потребность |
10 0 |
5 0 |
95 |
35 |
Искомый элемент равен 7. Для него запасы равны 30, потребности 95. Вычитаем минимальное 30.
Х13=min (30,95)=30
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
5 3 |
30 7 |
10 |
30-30=0 |
|
A 2 |
10 |
4 |
12 |
10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 0 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 0 |
|
Потребность |
30 10 0 |
80 5 0 |
95 65 |
35 |
Искомый элемент равен 10. Для него запасы равны 100, потребности 35. Вычитаем минимальное.
Х24=mi(100,35)=35
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
5 3 |
30 7 |
10 |
45 40 30 0 |
|
A 2 |
10 |
4 |
12 |
35 10 |
100 65 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 0 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 0 |
|
Потребность |
30 10 0 |
80 5 0 |
95 65 |
35 0 |
Х23=min (65,65)=65
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
5 3 |
30 7 |
10 |
45 40 30 0 |
|
A 2 |
10 |
4 |
65 12 |
35 10 |
65-65 0 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 0 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 0 |
|
Потребность |
30 10 0 |
80 5 0 |
65-65 0 |
35 0 |
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m+n-1=7. Следовательно опорный план является невырожденным.
10*6 + 5*3 + 30*7 + 65*12 + 35*10 + 20*5 + 75*2 = 1665 ден. ед.
Проверим является ли полученное решение оптимальным.
Каждому поставщику A i ставим в соответствие число u i, называемое потенциалом поставщика. Каждому потребителю B j ставим в соответствие число v j, называемое потенциалом потребителя. Значение одного потенциала необходимо задать. Пусть u1 = 0. Последовательно найдем значения потенциалов.
Поставщик |
Потребитель |
U |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
5 3 |
30 7 |
10 |
u1 = 0 |
|
A 2 |
10 |
4 |
65 12 |
35 10 |
u2 = 5 |
|
A 3 |
20 5 |
9 |
8 |
11 |
u3 = -1 |
|
A 4 |
4 |
75 2 |
4 |
8 |
u4 = -1 |
|
V |
v1 = 6 |
v2 = 3 |
v3 = 7 |
v4 = 5 |
A1B1: |
v1 + u1 = 6 |
v1 = 6 - 0 = 6 |
|
A1B2: |
v2 + u1 = 3 |
v2 = 3 - 0 = 3 |
|
A1B3: |
v3 + u1 = 7 |
v3 = 7 - 0 = 7 |
|
A2B3: |
v3 + u2 = 12 |
u2 = 12 - 7 = 5 |
|
A2B4: |
v4 + u2 = 10 |
v4 = 10 - 5 = 5 |
|
A3B1: |
v1 + u3 = 5 |
u3 = 5 - 6 = -1 |
|
A4B2: |
v2 + u4 = 2 |
u4 = 2 - 3 = -1 |
Найдем оценки незадействованных маршрутов.
A1B4: |
Д14 = c14 - ( u1 + v4 ) = 10 - ( 0 + 5 ) = 5 |
|
A2B1: |
Д21 = c21 - ( u2 + v1 ) = 10 - ( 5 + 6 ) = -1 |
|
A2B2: |
Д22 = c22 - ( u2 + v2 ) = 4 - ( 5 + 3 ) = -4 |
|
A3B2: |
Д32 = c32 - ( u3 + v2 ) = 9 - ( -1 + 3 ) = 7 |
|
A3B3: |
Д33 = c33 - ( u3 + v3 ) = 8 - ( -1 + 7 ) = 2 |
|
A3B4: |
Д34 = c34 - ( u3 + v4 ) = 11 - ( -1 + 5 ) = 7 |
|
A4B1: |
Д41 = c41 - ( u4 + v1 ) = 4 - ( -1 + 6 ) = -1 |
|
A4B3: |
Д43 = c43 - ( u4 + v3 ) = 4 - ( -1 + 7 ) = -2 |
|
A4B4: |
Д44 = c44 - ( u4 + v4 ) = 8 - ( -1 + 5 ) = 4 |
Есть отрицательные оценки, следовательно, опорный план не является оптимальным.
Выберем ячейку A2B2, ее оценка отрицательная. Поставим в эту ячейку знак "+", а в остальных вершинах чередующиеся знаки "-", "+", "-".
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
5(-) 3 |
30(+) 7 |
10 |
45 |
|
A 2 |
10 |
-4(+) 4 |
65(-) 12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Из грузов стоящих в минусовых клетках, выбираем наименьшее. Прибавляем 5 к объемам грузов, стоящих в плюсовых клетках и вычитаем 5 из стоящих в минусовых клетках. Получаем новый опорный план.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
5 3 |
30 7 |
10 |
45 |
|
A 2 |
10 |
-4 4 |
65 12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Данное преобразование не изменит баланса.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
5 - 5 3 |
30 + 5 7 |
10 |
45 |
|
A 2 |
10 |
+5 -4 4 |
65 - 5 12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Получили новое решение.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
3 |
35 7 |
10 |
45 |
|
A 2 |
10 |
5 4 |
60 12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75 2 |
4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Общая сумма доставки продукции, для данного решения
S = 1665 + Д22 * 5 = 1665 -4 * 5 = 1645 ден. ед.
A2B2: |
v2 + u2 = 4 |
v2 = 4 - 0 = 4 |
|
A2B3: |
v3 + u2 = 12 |
v3 = 12 - 0 = 12 |
|
A2B4: |
v4 + u2 = 10 |
v4 = 10 - 0 = 10 |
|
A4B2: |
v2 + u4 = 2 |
u4 = 2 - 4 = -2 |
|
A1B3: |
v3 + u1 = 7 |
u1 = 7 - 12 = -5 |
|
A1B1: |
v1 + u1 = 6 |
v1 = 6 - (-5) = 11 |
|
A3B1: |
v1 + u3 = 5 |
u3 = 5 - 11 = -6 |
A1B2: |
Д12 = c12 - ( u1 + v2 ) = 3 - ( -5 + 4 ) = 4 |
|
A1B4: |
Д14 = c14 - ( u1 + v4 ) = 10 - ( -5 + 10 ) = 5 |
|
A2B1: |
Д21 = c21 - ( u2 + v1 ) = 10 - ( 0 + 11 ) = -1 |
|
A3B2: |
Д32 = c32 - ( u3 + v2 ) = 9 - ( -6 + 4 ) = 11 |
|
A3B3: |
Д33 = c33 - ( u3 + v3 ) = 8 - ( -6 + 12 ) = 2 |
|
A3B4: |
Д34 = c34 - ( u3 + v4 ) = 11 - ( -6 + 10 ) = 7 |
|
A4B1: |
Д41 = c41 - ( u4 + v1 ) = 4 - ( -2 + 11 ) = -5 |
|
A4B3: |
Д43 = c43 - ( u4 + v3 ) = 4 - ( -2 + 12 ) = -6 |
Поставщик |
Потребитель |
U |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
3 |
35 7 |
10 |
u1 = -5 |
|
A 2 |
10 |
5 4 |
60 12 |
35 10 |
u2 = 0 |
|
A 3 |
20 5 |
9 |
8 |
11 |
u3 = -6 |
|
A 4 |
4 |
75 2 |
4 |
8 |
u4 = -2 |
|
V |
v1 = 11 |
v2 = 4 |
v3 = 12 |
v4 = 10 |
Есть отрицательные оценки, значит можно получить новое решение.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
3 |
35 7 |
10 |
45 |
|
A 2 |
10 |
5(+) 4 |
60(-) 12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75(-) 2 |
-6(+) 4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Из грузов стоящих в минусовых клетках, выбираем наименьшее.
60 = min ( 75, 60 ) Прибавляем 60 к объемам грузов, стоящих в плюсовых клетках и вычитаем 60 из стоящих в минусовых клетках. Получим новый опорный план.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
3 |
35 7 |
10 |
45 |
|
A 2 |
10 |
5 4 |
60 12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75 2 |
-6 4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Данное преобразование не изменит баланса. А вот общая стоимость доставки продукции изменится на величину:
4 * 60 - 2 * 60 + 4 * 60 - 12 * 60 = ( 4 - 2 + 4 - 12 ) * 60 = -6 * 60 ден. ед. -6 * 60 = Д43 * 60
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
3 |
35 7 |
10 |
45 |
|
A 2 |
10 |
5 + 60 4 |
60 - 60 12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
75 - 60 2 |
+60 -6 4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Получили новое решение.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
3 |
35 7 |
10 |
45 |
|
A 2 |
10 |
65 4 |
12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
15 2 |
60 4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Считаем общую сумму доставки продукции, для данного решения
S = 1645 + Д43 * 60 = 1645 -6 * 60 = 1285 ден. ед.
Проверяем полученное решение на оптимальность. Значение одного потенциала необходимо задать. Пусть u1 = 0. Последовательно найдем значения потенциалов.
Поставщик |
Потребитель |
U |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
3 |
35 7 |
10 |
u1 = 0 |
|
A 2 |
10 |
65 4 |
12 |
35 10 |
u2 = -1 |
|
A 3 |
20 5 |
9 |
8 |
11 |
u3 = -1 |
|
A 4 |
4 |
15 2 |
60 4 |
8 |
u4 = -3 |
|
V |
v1 = 6 |
v2 = 5 |
v3 = 7 |
v4 = 11 |
A1B1: |
v1 + u1 = 6 |
v1 = 6 - 0 = 6 |
|
A1B3: |
v3 + u1 = 7 |
v3 = 7 - 0 = 7 |
|
A3B1: |
v1 + u3 = 5 |
u3 = 5 - 6 = -1 |
|
A4B3: |
v3 + u4 = 4 |
u4 = 4 - 7 = -3 |
|
A4B2: |
v2 + u4 = 2 |
v2 = 2 - (-3) = 5 |
|
A2B2: |
v2 + u2 = 4 |
u2 = 4 - 5 = -1 |
|
A2B4: |
v4 + u2 = 10 |
v4 = 10 - (-1) = 11 |
A1B2: |
Д12 = c12 - ( u1 + v2 ) = 3 - ( 0 + 5 ) = -2 |
|
A1B4: |
Д14 = c14 - ( u1 + v4 ) = 10 - ( 0 + 11 ) = -1 |
|
A2B1: |
Д21 = c21 - ( u2 + v1 ) = 10 - ( -1 + 6 ) = 5 |
|
A2B3: |
Д23 = c23 - ( u2 + v3 ) = 12 - ( -1 + 7 ) = 6 |
|
A3B2: |
Д32 = c32 - ( u3 + v2 ) = 9 - ( -1 + 5 ) = 5 |
|
A3B3: |
Д33 = c33 - ( u3 + v3 ) = 8 - ( -1 + 7 ) = 2 |
|
A3B4: |
Д34 = c34 - ( u3 + v4 ) = 11 - ( -1 + 11 ) = 1 |
|
A4B1: |
Д41 = c41 - ( u4 + v1 ) = 4 - ( -3 + 6 ) = 1 |
|
A4B4: |
Д44 = c44 - ( u4 + v4 ) = 8 - ( -3 + 11 ) = 0 |
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
-2 3 |
35 7 |
10 |
45 |
|
A 2 |
10 |
65 4 |
12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
15 2 |
60 4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Есть отрицательные оценки, следовательно, возможно получить новое решение.
Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. ячейку A1B2, ее оценка отрицательная.
Общая стоимость доставки продукции изменится на величину:
3 * 15 - 7 * 15 + 4 * 15 - 2 * 15 = ( 3 - 7 + 4 - 2 ) * 15 = -2 * 15 ден. ед. -2 * 15 = Д12 * 15
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
+15 -2 3 |
35 - 15 7 |
10 |
45 |
|
A 2 |
10 |
65 4 |
12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
15 - 15 2 |
60 + 15 4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Получили новое решение.
Поставщик |
Потребитель |
Запас |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
15 3 |
20 7 |
10 |
45 |
|
A 2 |
10 |
65 4 |
12 |
35 10 |
100 |
|
A 3 |
20 5 |
9 |
8 |
11 |
20 |
|
A 4 |
4 |
2 |
75 4 |
8 |
75 |
|
Потребность |
30 |
80 |
95 |
35 |
Считаем общую сумму доставки продукции
S = 1285 + Д12 * 15 = 1285 -2 * 15 = 1255 ден. ед.
Проверяем решение на оптимальность. Значение одного потенциала необходимо задать. Пусть u1 = 0. Последовательно найдем значения потенциалов.
Нет отрицательных оценок, следовательно, уменьшить общую стоимость доставки продукции невозможно. План является оптимальным, так как все оценки свободных клеток удовлетворяют условию Ui+Vj<Cij.
Минимальные затраты составят:
F(х)=6*10+3*15+7*20+4*65+10*35+5*20+4*75=1255 ден. ед.
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (10), во 2-й магазин (15), в 3-й магазин (20). Из 2-го склада необходимо груз направить во 2-й магазин (65), в 4-й магазин (35). Из 3-го склада необходимо весь груз направить в 1-й магазин. Из 4-го склада необходимо весь груз направить в 3-й магазин.
A1B1: |
v1 + u1 = 6 |
v1 = 6 - 0 = 6 |
|
A1B2: |
v2 + u1 = 3 |
v2 = 3 - 0 = 3 |
|
A1B3: |
v3 + u1 = 7 |
v3 = 7 - 0 = 7 |
|
A2B2: |
v2 + u2 = 4 |
u2 = 4 - 3 = 1 |
|
A2B4: |
v4 + u2 = 10 |
v4 = 10 - 1 = 9 |
|
A3B1: |
v1 + u3 = 5 |
u3 = 5 - 6 = -1 |
|
A4B3: |
v3 + u4 = 4 |
u4 = 4 - 7 = -3 |
Поставщик |
Потребитель |
U |
||||
B 1 |
B 2 |
B 3 |
B 4 |
|||
A 1 |
10 6 |
15 3 |
20 7 |
10 |
u1 = 0 |
|
A 2 |
10 |
65 4 |
12 |
35 10 |
u2 = 1 |
|
A 3 |
20 5 |
9 |
8 |
11 |
u3 = -1 |
|
A 4 |
4 |
2 |
75 4 |
8 |
u4 = -3 |
|
V |
v1 = 6 |
v2 = 3 |
v3 = 7 |
v4 = 9 |
Список литературы
1. Высшая математика для экономистов: учебник* / Кремер Н. Ш. [и др.]; ред. Н. Ш. Кремер. - М.: ЮНИТИ-ДАНА, 2010. - 479с.
2. Высшая математика для экономического бакалавриата: учебник* и практикум / Н. Ш. Кремер [и др.]; ред. Н. Ш. Кремер. - Москва: Юрайт, 2012. - 909с.
3. Красс, М. С. Математика для экономистов [Текст]: учебное пособие* / М. С. Красс, Б. П. Чупрынов. - М.; СПб.; Н. Новгород [и др.]: Питер, 2009. - 464 с.: рис. - (Учебное пособие). - Библиогр.: с. 461.
4. Грицюк С.Н. Математические методы и модели в экономике: учебник.- Ростов н/Д:Феникс, 2007
Размещено на Allbest.ru
...Подобные документы
- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Решение задач линейного программирования с применением алгоритма графического определения показателей и значений, с использованием симплекс-метода. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана ЗЛП.
контрольная работа [94,6 K], добавлен 23.04.2013Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.
курсовая работа [105,5 K], добавлен 02.10.2014Понятие математического программирования как отрасли математики, являющейся теоретической основой решения задач о нахождении оптимальных решений. Основные этапы нахождения оптимальных решений экономических задач. Примеры задач линейного программирования.
учебное пособие [2,0 M], добавлен 15.06.2015Характеристика и описание метода линейного программирования, основные области его применения и ограничения использования. Решение экономических задач, особенности формирования оптимизационной модели, расчет и анализ результатов оптимизации прибыли.
курсовая работа [99,0 K], добавлен 23.03.2010Математическая формулировка задачи линейного программирования. Применение симплекс-метода решения задач. Геометрическая интерпретация задачи линейного программирования. Применение методов линейного программирования к экстремальным задачам экономики.
курсовая работа [106,0 K], добавлен 05.10.2014Исследование методом Жордана-Гаусса системы линейных уравнений. Решение графическим и симплексным методом задач линейного программирования. Экономико-математическая модель задачи на максимум прибыли и нахождение оптимального плана выпуска продукции.
контрольная работа [177,8 K], добавлен 02.02.2010Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.
контрольная работа [135,3 K], добавлен 01.06.2014Целевая функция, экстремальное значение которой нужно найти в условиях экономических возможностей, как показатель эффективности или критерий оптимальности. Оптимальное использование ресурсов и производственных мощностей. Общая идея симплексного метода.
контрольная работа [1,1 M], добавлен 18.05.2015Нахождение области допустимых значений и оптимумов целевой функции с целью решения графическим методом задачи линейного программирования. Нахождение оптимальных значений двойственных переменных при помощи симплексного метода и теории двойственности.
контрольная работа [116,0 K], добавлен 09.04.2012Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.
контрольная работа [40,0 K], добавлен 04.05.2014Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Экономико-математическая модель оптимального плана выпуска продукции. Оптимальная организация рекламной компании. Решение транспортной задачи: нахождение суммарных затрат на перевозку. Задача об оптимальном назначении (линейного программирования).
контрольная работа [812,0 K], добавлен 29.09.2010Транспортная задача линейного программирования, закрытая модель. Создание матрицы перевозок. Вычисление значения целевой функции. Ввод зависимостей из математической модели. Установление параметров задачи. Отчет по результатам транспортной задачи.
контрольная работа [202,1 K], добавлен 17.02.2010Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
контрольная работа [613,3 K], добавлен 18.02.2014Построение экономико-математической модели задачи, комментарии к ней и получение решения графическим методом. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
контрольная работа [2,2 M], добавлен 27.03.2008Построение математической модели и решение задачи математического программирования в средах MathCad и MS Excel. Решение систем с произвольными векторами свободных коэффициентов. Определение вектора невязки. Минимизация и максимизация целевой функции.
отчет по практике [323,5 K], добавлен 01.10.2013Графическое решение и оптимальный план задачи линейного программирования. Свойства двойственных оценок и теорем двойственности. Адаптивная модель Брауна. Свойства независимости остаточной компоненты, соответствия нормальному закону распределения.
контрольная работа [556,2 K], добавлен 17.02.2010Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.
курсовая работа [30,5 K], добавлен 14.04.2004Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
курсовая работа [54,1 K], добавлен 05.03.2010