Математические модели в экономике
Основной расчет плана выпуска изделий, дающий наибольшую прибыль. Особенность составления математической модели прямой задачи линейного программирования. Характеристика построения симплексного метода. Определение новой базисной и свободной переменной.
Рубрика | Экономико-математическое моделирование |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 31.03.2015 |
Размер файла | 587,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Задача 1
Предприятие выпускает два вида изделий, используя для этого сырье трех видов. Норма расхода сырья на изготовление единицы каждого вида изделий, а также запасы сырья и прибыль от реализации изделий каждого вида даны в таблице:
Сырье |
Норма расхода сырья на единицу изделия (кг) |
Запасы сырья (кг) |
||
1 |
2 |
|||
1 2 3 |
2 7 3 |
3 3 5 |
120 210 90 |
|
Прибыль от реализации единицы изделия в у.е. |
60 |
55 |
Найти план выпуска изделий, дающий наибольшую прибыль.
Составить математическую модель задачи, решить ее графически. Составить двойственную задачу, решить ее с помощью теорем двойственности. Дать экономическую интерпретацию двойственных задач.
Решение: Составим математическую модель. Пусть будет изготовлено х1 - изделий вида А и х2-изделий вида В. Тогда план производства представляется вектором (х1, х2).
Прибыль от реализации одного изделия вида А составляет 60 единицы, а от реализации х1 изделий - 60х1 единиц. Прибыль от реализации одного изделия вида В составляет 55 единицы, а от реализации х2 изделий - 55х2 единиц. Общая прибыль предприятия составит 60х1+55х2. Целевая функция задачи имеет вид:
,
На производство единицы изделия А расходуется 2 единиц сырья первого вида, а на х1 изделий А расходуется 2х1 единиц сырья первого вида. На производство единицы изделия В расходуется 3 единиц сырья первого вида, а на х2 изделий В расходуется 3х2 единиц сырья первого вида. Запасы сырья первого вида составляют 300 единицы , следователь 2х1+3х2=120. Аналогичные рассуждения проводятся по 2 и 3 видам сырья. Количество произведенных изделий может быть либо положительным, либо равно нулю. Условий целочисленности на количество изделий не наложено. Математическая модель задачи имеет вид:
,
,
,
Решим задачу графическим методом. Область допустимых решений задачи -пересечение полуплоскостей, определенных каждым неравенством системы ограничений.
Для первого неравенство: 2х1+3х2120 строим прямую 2х1+3х2=120. Взяв произвольную точку из одной из полуплоскостей, определим, является ли данная полуплоскость множеством решений данного неравенства. Например: точка 0 (0;0). 2Ч0+3Ч0=120 Ю0< 120, т.е. полуплоскость, содержащая т.0 является множеством решений неравенства 2х1+3х2Ј120.
Аналогично строим полуплоскости, определяемые остальными неравенствами.
Пересечение этих полуплоскостей образует область допустимых решений, т.е. многоугольник ОАВC. По теореме об экстремуме целевой функции, если оптимальное решение существует, то оно совпадает с угловой точкой области допустимых решений. Для нахождения оптимального решения строим вектор , перпендикулярно ему проводим линию уровня, которую перемещаем по направлению вектора , т.к. задача решается на max. Последняя точка пересечения линии уровня и области допустимых решений является оптимальным решением задачи. Если оптимальное решение совпадает с двумя угловыми точками области допустимых решений, например, х1 и х2, то любая точка отрезка ? х1, х2? является оптимальным решением, т.е.
,
в т.B, которая лежит на пересечении I и II граничных прямых
,
,
,
,
Составим двойственную задачу к исходной. В исходной задаче ограничения заданы неравенствами и на переменные наложено ограничение неотрицательности, то получим симметричную пару задач.
Каждому ограничению исходной задачи соответствует переменная в двойственной. Цель задачи меняется на противоположную. Транспонируется матрица коэффициентов задачи, коэффициенты при переменных в целевой функции заменяются сводными членами системы ограничений исходной задачи.
,
,
,
Исходя из теорем двойственности, найдем решение двойственной задачи.
,
,
поэтому соответствующие им 1 и 2 ограничения двойственной задачи выполняются как равенства.
Получили: ,
Решение СЛАУ методом Гаусса.
Запишем систему в виде расширенной матрицы:
,
Работаем со столбцом №1.
Умножим 1-ую строку на и добавим ко 2-ой:
,
Получим единицы на главной диагонали. Для этого всю строку делим на соответствующий элемент главной диагонали:
,
Теперь исходную систему можно записать так:
,
Необходимо переменную принять в качестве свободной переменной и через нее выразить остальные переменные.
Приравниваем переменную к 0.
Из второй строки выражаем :
,
Из первой строки выражаем :
,
,
Экономический анализ: Для получения максимальной прибыли в 2620 у.е. необходимо произвести 18 кг изделия №1 и 28 кг изделия №2. При этом сырье 1,2,3 будет полностью израсходовано и каждая дополнительно привлеченная единица сырья 1 вида принесет дополнительно ед. прибыли, а каждая дополнительно привлеченная единица сырья второго вида даст прибыль в единицы. Сырье третьего вида не используется полностью, и предприятию можно было не покупать кг этого сырья.
Задача 2
Решить симплексным методом.
,
.
,
1) Использование встроенных функций MS Excel для решения задач линейного программирования симплексным методом.
1. Пронумеруем ячейки B1-F1 соответственно x1, x2, x3, x4, x5, а ячейку H1 соответственно B.
2. В ячейку A4 впишем F(x) и далее запишем данные этой функции соответственно: -1, 8, 5, 1, -2.
3. В ячейку G4 запишем 0, в ячейку H4 знак «».
4. В ячейку I4 запишем формулу: =B4*B2+C4*C2+D4*D2+E4*E2+F4*F2+G4.
5. Пронумеруем ячейки A6-A8 соответственно 1, 2, 3.
6. В ячейки B6:F8 занесем данные системы уравнений.
7. В ячейки G6-G8 занесем знак «=».
8. В ячейки H6-H8 занесем переменные системы уравнений соответственно 33, 7, 21.
9. В ячейку I6 занесем формулу: =B6*B2+C6*C2+D6*D2+E6*E2+F6*F2+0,
I7: =B7*B2+C7*C2+D7*D2+E7*E2+F7*F2+0,
I8: =B8*B2+C8*C2+D8*D2+E8*E2+F8*F2+0.
Получили следующее:
Теперь с помощью меню Данные > Поиск решения вызываем одноименное диалоговое окно, которое служит для формулирования задачи и запуска алгоритма оптимизации. Оно имен следующий вид:
Для того, что выполнить эту команду, опишем алгоритм:
1. Перейдите к ячейке I4.
2. Выполните команду Данные / Поиск решения.
3. В диалоговом окне укажем: вид поиска (максимальное значение),
в поле <изменяя ячейки>: $B$2:$F$2,
в поле <Ограничения> добавьте заданные ограничения: $B$2:$F$2>=0, $I$6=$H$6, $I$7=$H$7, $I$8=$H$8.
4. Командой Выполнить запускаем алгоритм. В следующий момент появляется диалоговое окно Результаты поиска решения:
5. Выбираем Сохранить найденное решение и нажимаем ОК.
На рабочем листе в диапазоне переменных появились числа, которые в точности соответствуют оптимальному решению задачи.
2) Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим минимальное значение целевой функции F(X) = - x1 + 8x2 + 5x3 + x4 - 2x5 при следующих условиях-ограничений.
3x1 - 3x2 + 4x3 + 14x4 + x5=33
x1 - 3x2 + x3 + 2x4=7
2x1 - 2x2 + 2x3 + 9x4 + x5=21
Введем искусственные переменные x: в 1-м равенстве вводим переменную x6; в 2-м равенстве вводим переменную x7; в 3-м равенстве вводим переменную x8;
3x1-3x2 + 4x3 + 14x4 + 1x5 + 1x6 + 0x7 + 0x8 = 33
1x1-3x2 + 1x3 + 2x4 + 0x5 + 0x6 + 1x7 + 0x8 = 7
2x1-2x2 + 2x3 + 9x4 + 1x5 + 0x6 + 0x7 + 1x8 = 21
Для постановки задачи на минимум целевую функцию запишем так:
F(X) = -1x1+8x2+5x3+x4-2x5+Mx6+Mx7+Mx8 > min
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
x6 = 33-3x1+3x2-4x3-14x4-x5
x7 = 7-x1+3x2-x3-2x4
x8 = 21-2x1+2x2-2x3-9x4-x5
которые подставим в целевую функцию:
F(X) = -x1 + 8x2 + 5x3 + x4-2x5 + M(33-3x1+3x2-4x3-14x4-x5) + M(7-x1+3x2-x3-2x4) + M(21-2x1+2x2-2x3-9x4-x5) > min
F(X) = (-1-6M)x1+(8+8M)x2+(5-7M)x3+(1-25M)x4+(-2-2M)x5+(61M) > min
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
3 |
-3 |
4 |
14 |
1 |
1 |
0 |
0 |
|
1 |
-3 |
1 |
2 |
0 |
0 |
1 |
0 |
|
2 |
-2 |
2 |
9 |
1 |
0 |
0 |
1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных: x6, x7, x8
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,33,7,21)
Базисное решение называется допустимым, если оно неотрицательно.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
|
x6 |
33 |
3 |
-3 |
4 |
14 |
1 |
1 |
0 |
0 |
|
x7 |
7 |
1 |
-3 |
1 |
2 |
0 |
0 |
1 |
0 |
|
x8 |
21 |
2 |
-2 |
2 |
9 |
1 |
0 |
0 |
1 |
|
F(X0) |
61M |
1+6M |
-8-8M |
-5+7M |
-1+25M |
2+2M |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai4
и из них выберем наименьшее:
min (33 : 14 , 7 : 2 , 21 : 9 ) = 21/3
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (9) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
min |
|
x6 |
33 |
3 |
-3 |
4 |
14 |
1 |
1 |
0 |
0 |
25/14 |
|
x7 |
7 |
1 |
-3 |
1 |
2 |
0 |
0 |
1 |
0 |
31/2 |
|
x8 |
21 |
2 |
-2 |
2 |
9 |
1 |
0 |
0 |
1 |
21/3 |
|
F(X1) |
61M |
1+6M |
-8-8M |
-5+7M |
-1+25M |
2+2M |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x8 в план 1 войдет переменная x4.
Строка, соответствующая переменной x4 в плане 1, получена в результате деления всех элементов строки x8 плана 0 на разрешающий элемент РЭ=9
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x4 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x4 и столбец x4.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (9), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
|
x6 |
1/3 |
-1/9 |
1/9 |
8/9 |
0 |
-5/9 |
1 |
0 |
-14/9 |
|
x7 |
7/3 |
5/9 |
-23/9 |
5/9 |
0 |
-2/9 |
0 |
1 |
-2/9 |
|
x4 |
7/3 |
2/9 |
-2/9 |
2/9 |
1 |
1/9 |
0 |
0 |
1/9 |
|
F(X1) |
21/3+22/3M |
12/9+4/9M |
-82/9-24/9M |
-47/9+14/9M |
0 |
21/9-7/9M |
0 |
0 |
1/9-27/9M |
Итерация 1
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (1/3 : 8/9 , 21/3 : 5/9 , 21/3 : 2/9 ) = 3/8
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (8/9) и находится на пересечении ведущего столбца и ведущей строки. математический линейный прибыль симплексный
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
min |
|
x6 |
1/3 |
-1/9 |
1/9 |
8/9 |
0 |
-5/9 |
1 |
0 |
-15/9 |
3/8 |
|
x7 |
21/3 |
5/9 |
-25/9 |
5/9 |
0 |
-2/9 |
0 |
1 |
-2/9 |
41/5 |
|
x4 |
21/3 |
2/9 |
-2/9 |
2/9 |
1 |
1/9 |
0 |
0 |
1/9 |
101/2 |
|
F(X2) |
21/3+22/3M |
12/9+4/9M |
-82/9-24/9M |
-47/9+14/9M |
0 |
21/9-7/9M |
0 |
0 |
1/9-27/9M |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 2 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=8/9
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x3 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
|
x3 |
3/8 |
-1/8 |
1/8 |
1 |
0 |
-5/8 |
9/8 |
0 |
-7/4 |
|
x7 |
17/8 |
5/8 |
-21/8 |
0 |
0 |
1/8 |
-5/8 |
1 |
3/4 |
|
x4 |
9/4 |
1/4 |
-1/4 |
0 |
1 |
1/4 |
-1/4 |
0 |
1/2 |
|
F(X2) |
41/8+21/8M |
5/8+5/8M |
-75/8-25/8M |
0 |
0 |
-7/8+M |
53/8-15/8M |
0 |
-81/4-M |
Итерация 2.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (- , 21/8 : 5/8 , 21/4 : 1/4 ) = 32/5
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (5/8) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
min |
|
x3 |
3/8 |
-1/8 |
1/8 |
1 |
0 |
-5/8 |
11/8 |
0 |
-13/4 |
- |
|
x7 |
21/8 |
5/8 |
-25/8 |
0 |
0 |
1/8 |
-5/8 |
1 |
3/4 |
32/5 |
|
x4 |
21/4 |
1/4 |
-1/4 |
0 |
1 |
1/4 |
-1/4 |
0 |
1/2 |
9 |
|
F(X3) |
41/8+21/8M |
5/8+5/8M |
-75/8-25/8M |
0 |
0 |
-7/8+M |
53/8-15/8M |
0 |
-81/4-M |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x7 в план 3 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 3, получена в результате деления всех элементов строки x7 плана 2 на разрешающий элемент РЭ=5/8
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x1 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
|
x3 |
4/5 |
0 |
-2/5 |
1 |
0 |
-3/5 |
1 |
1/5 |
-8/5 |
|
x1 |
17/5 |
1 |
-21/5 |
0 |
0 |
1/5 |
-1 |
8/5 |
6/5 |
|
x4 |
7/5 |
0 |
4/5 |
0 |
1 |
1/5 |
0 |
-2/5 |
1/5 |
|
F(X3) |
2 |
0 |
-5 |
0 |
0 |
-1 |
6-M |
-1-M |
-9-M |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
|
x3 |
4/5 |
0 |
-2/5 |
1 |
0 |
-3/5 |
1 |
1/5 |
-8/5 |
|
x1 |
17/5 |
1 |
-21/5 |
0 |
0 |
1/5 |
-1 |
8/5 |
6/5 |
|
x4 |
7/5 |
0 |
4/5 |
0 |
1 |
1/5 |
0 |
-2/5 |
1/5 |
|
F(X4) |
2 |
0 |
-5 |
0 |
0 |
-1 |
6-M |
-1-M |
-9-M |
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
x3 = 4/5
x1 = 32/5
x4 = 12/5
F(X) = 5*4/5 -1*32/5 + 1*12/5 = 2
Задача 3
Решить транспортную задачу.
130 |
150 |
120 |
110 |
200 |
||
190 |
3 |
7 |
6 |
1 |
5 |
|
220 |
4 |
2 |
5 |
8 |
3 |
|
300 |
6 |
9 |
2 |
4 |
8 |
Решение:
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
3 |
7 |
6 |
1 |
5 |
190 |
|
2 |
4 |
2 |
5 |
8 |
3 |
220 |
|
3 |
6 |
9 |
2 |
4 |
8 |
300 |
|
Потребности |
130 |
150 |
120 |
110 |
200 |
Проверим необходимое и достаточное условие разрешимости задачи.
?a = 190 + 220 + 300 = 710
?b = 130 + 150 + 120 + 110 + 200 = 710
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
3 |
7 |
6 |
1 |
5 |
190 |
|
2 |
4 |
2 |
5 |
8 |
3 |
220 |
|
3 |
6 |
9 |
2 |
4 |
8 |
300 |
|
Потребности |
130 |
150 |
120 |
110 |
200 |
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 1
Для этого элемента запасы равны 190, потребности 110. Поскольку минимальным является 110, то вычитаем его.
x14 = min(190,110) = 110.
3 |
7 |
6 |
1 |
5 |
190 - 110 = 80 |
|
4 |
2 |
5 |
x |
3 |
220 |
|
6 |
9 |
2 |
x |
8 |
300 |
|
130 |
150 |
120 |
110 - 110 = 0 |
200 |
0 |
Искомый элемент равен 2
Для этого элемента запасы равны 220, потребности 150. Поскольку минимальным является 150, то вычитаем его.
x22 = min(220,150) = 150.
3 |
x |
6 |
1 |
5 |
80 |
|
4 |
2 |
5 |
x |
3 |
220 - 150 = 70 |
|
6 |
x |
2 |
x |
8 |
300 |
|
130 |
150 - 150 = 0 |
120 |
0 |
200 |
0 |
Искомый элемент равен 2
Для этого элемента запасы равны 300, потребности 120. Поскольку минимальным является 120, то вычитаем его.
x33 = min(300,120) = 120.
3 |
x |
x |
1 |
5 |
80 |
|
4 |
2 |
x |
x |
3 |
70 |
|
6 |
x |
2 |
x |
8 |
300 - 120 = 180 |
|
130 |
0 |
120 - 120 = 0 |
0 |
200 |
0 |
Искомый элемент равен 3
Для этого элемента запасы равны 80, потребности 130. Поскольку минимальным является 80, то вычитаем его.
x11 = min(80,130) = 80.
3 |
x |
x |
1 |
x |
80 - 80 = 0 |
|
4 |
2 |
x |
x |
3 |
70 |
|
6 |
x |
2 |
x |
8 |
180 |
|
130 - 80 = 50 |
0 |
0 |
0 |
200 |
0 |
Искомый элемент равен 3
Для этого элемента запасы равны 70, потребности 200. Поскольку минимальным является 70, то вычитаем его.
x25 = min(70,200) = 70.
3 |
x |
x |
1 |
x |
0 |
|
x |
2 |
x |
x |
3 |
70 - 70 = 0 |
|
6 |
x |
2 |
x |
8 |
180 |
|
50 |
0 |
0 |
0 |
200 - 70 = 130 |
0 |
Искомый элемент равен 6
Для этого элемента запасы равны 180, потребности 50. Поскольку минимальным является 50, то вычитаем его.
x31 = min(180,50) = 50.
3 |
x |
x |
1 |
x |
0 |
|
x |
2 |
x |
x |
3 |
0 |
|
6 |
x |
2 |
x |
8 |
180 - 50 = 130 |
|
50 - 50 = 0 |
0 |
0 |
0 |
130 |
0 |
Искомый элемент равен 8
Для этого элемента запасы равны 130, потребности 130. Поскольку минимальным является 130, то вычитаем его.
x35 = min(130,130) = 130.
3 |
x |
x |
1 |
x |
0 |
|
x |
2 |
x |
x |
3 |
0 |
|
6 |
x |
2 |
x |
8 |
130 - 130 = 0 |
|
0 |
0 |
0 |
0 |
130 - 130 = 0 |
0 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
1 |
2 |
3 |
4 |
5 |
Запасы |
||
1 |
3[80] |
7 |
6 |
1[110] |
5 |
190 |
|
2 |
4 |
2[150] |
5 |
8 |
3[70] |
220 |
|
3 |
6[50] |
9 |
2[120] |
4 |
8[130] |
300 |
|
Потребности |
130 |
150 |
120 |
110 |
200 |
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 3*80 + 1*110 + 2*150 + 3*70 + 6*50 + 2*120 + 8*130 = 2440
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 3; 0 + v1 = 3; v1 = 3
u3 + v1 = 6; 3 + u3 = 6; u3 = 3
u3 + v3 = 2; 3 + v3 = 2; v3 = -1
u3 + v5 = 8; 3 + v5 = 8; v5 = 5
u2 + v5 = 3; 5 + u2 = 3; u2 = -2
u2 + v2 = 2; -2 + v2 = 2; v2 = 4
u1 + v4 = 1; 0 + v4 = 1; v4 = 1
v1=3 |
v2=4 |
v3=-1 |
v4=1 |
v5=5 |
||
u1=0 |
3[80] |
7 |
6 |
1[110] |
5 |
|
u2=-2 |
4 |
2[150] |
5 |
8 |
3[70] |
|
u3=3 |
6[50] |
9 |
2[120] |
4 |
8[130] |
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ? cij.
Минимальные затраты составят:
F(x) = 3*80 + 1*110 + 2*150 + 3*70 + 6*50 + 2*120 + 8*130 = 2440
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (80), в 4-й магазин (110)
Из 2-го склада необходимо груз направить в 2-й магазин (150), в 5-й магазин (70)
Из 3-го склада необходимо груз направить в 1-й магазин (50), в 3-й магазин (120), в 5-й магазин (130)
Задача 4
Руководство некоторой компании решает, создать ли для выпуска новой продукции крупное производство, малое предприятие или продать патент другой фирме. Размер выигрыша, который может получить фирма, зависит от состояния рынка. Размер прибыли при благоприятных условиях рынка и при неблагоприятных дан в таблице.
Выбор компании |
Благоприятные условия рынка |
Неблагоприятные условия рынка |
|
Крупное предприятие |
220 |
- 120 |
|
Малое предприятие |
100 |
-20 |
|
патент |
20 |
20 |
Определить наиболее выгодный выбор компании. Решение найти, используя критерии Вальда, максимума, Гурвица.
Решение: Критерий Вальда. Выбираем максиминную стратегию из условия:
.
,
Согласно этому критерию следует выбирать патент.
Критерий максимума. Стратегия выбирается из условия:
,
,
Следовательно, целесообразно выбрать крупное предприятие.
Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле:
,
где б степень оптимизма и изменяется в диапазоне [ 0; 1 ] . Пусть б=0,5.Тогда стратегию определяем из условия:
,
Рекомендуется сделать выбор на крупное предприятие.
Список используемой литературы
1. Акулич И.А. Математическое программирование в примерах и задачах: Учебное пособие. 3-е изд., стер. - СПб.: Издательство «Лань», 2011. - 352 с.: ил. - (Учебники для вузов. Специальная литература).
2. Балдин К.В. Математические методы и модели в экономике: учебник / Балдин К.В., В.Н. Башлыков, А.В. Рукосуев. - М.: Флинта: НОУ ВПО «МПСИ», 2012. - 328 с.
3. Красс М.С., Чупрынов Б.П. Математические методы и модели для магистрантов экономики: Учебное пособие. 2-е изд., доп. - СПб.: Питер, 2010. - 496 с.: ил. - (Серия «Учебное пособие»).
4. Семенов А.Г. математические модели в экономике: учебное пособие / А.Г. Семенов, И.А. Печерских; Кемеровский технологический институт пищевой промышленности. - Кемерово, 2011. - 187 с.
Размещено на Allbest.ru
...Подобные документы
Построение экономической модели по оптимизации прибыли производства. Разработка математической модели задачи по оптимизации производственного плана и её решение методами линейного программирования. Определение опорного и оптимального плана производства.
дипломная работа [311,3 K], добавлен 17.01.2014Построение математических моделей по определению плана выпуска изделий, обеспечивающего максимальную прибыль, с помощью графического и симплексного метода. Построение моделей по решению транспортных задач при применении метода минимальной стоимости.
задача [169,2 K], добавлен 06.01.2012Построение математической модели, максимизирующей прибыль фирмы от реализации всех сделок в виде задачи линейного программирования. Сущность применения алгоритма венгерского метода. Составление матрицы эффективности, коэффициентов затрат и ресурсов.
контрольная работа [168,7 K], добавлен 08.10.2009Составление математической модели задачи. Расчёт оптимального плана перевозок с минимальной стоимостью с использованием метода потенциалов. Оптимальный вариант специального передвижного оборудования для технического обеспечения управления производством.
контрольная работа [135,3 K], добавлен 01.06.2014Построение одноиндексной математической модели задачи линейного программирования, ее решение графическим методом. Разработка путей оптимизации сетевой модели по критерию "минимум исполнителей". Решение задачи управления запасами на производстве.
контрольная работа [80,8 K], добавлен 13.12.2010Построение экономико-математической модели задачи, комментарии к ней и получение решения графическим методом. Использование аппарата теории двойственности для экономико-математического анализа оптимального плана задачи линейного программирования.
контрольная работа [2,2 M], добавлен 27.03.2008Математические и программные средства моделирования при решении конкретной производственной задачи. Метод реализации задачи планирования производства и нахождение оптимального плана с помощью симплексного метода. Программа на языке программирования С.
курсовая работа [603,8 K], добавлен 06.06.2011Моделирование экономических систем: основные понятия и определения. Математические модели и методы их расчета. Некоторые сведения из математики. Примеры задач линейного программирования. Методы решения задач линейного программирования.
лекция [124,5 K], добавлен 15.06.2004Использование симплексного метода решения задач линейного программирования для расчета суточного объема производства продукции. Проверка плана на оптимальность. Пересчет симплексной таблицы методом Жордана-Гаусса. Составление модели транспортной задачи.
контрольная работа [613,3 K], добавлен 18.02.2014Целевая функция, экстремальное значение которой нужно найти в условиях экономических возможностей, как показатель эффективности или критерий оптимальности. Оптимальное использование ресурсов и производственных мощностей. Общая идея симплексного метода.
контрольная работа [1,1 M], добавлен 18.05.2015Решение задачи линейного программирования графическим способом. Построение математической модели задачи с использованием симплекс-таблиц, её экономическая интерпретация. Поиск оптимального плана перевозки изделий, при котором расходы будут наименьшими.
задача [579,8 K], добавлен 11.07.2010Роль экономико-математических методов в оптимизации экономических решений. Этапы построения математической модели и решение общей задачи симплекс-методом. Составление экономико-математической модели предприятия по производству хлебобулочных изделий.
курсовая работа [1,3 M], добавлен 09.07.2015Определение наиболее выгодного суточного объема выпуска изделий, обеспечивающего максимум прибыли. Построение математической модели задачи, ее решение графическим методом и в среде MS Excel. Расчет диапазона дефицитности ресурсов и дрейфа оптимума.
контрольная работа [994,1 K], добавлен 16.02.2013Основы математического моделирования экономических процессов. Общая характеристика графического и симплексного методов решения прямой и двойственной задач линейного программирования. Особенности формулирования и методика решения транспортной задачи.
курсовая работа [313,2 K], добавлен 12.11.2010Расчет оптимального числа поездов, при которых перевозится максимальное число пассажиров, плана перевозки с минимальными расходами. Выбор стратегии выпуска новой продукции. Построение регрессионной модели зависимости расходов на питание от дохода семьи.
контрольная работа [3,3 M], добавлен 28.03.2010Задача оптимального составления смесей при производстве бензина различных сортов. Модели формирования шихты при выплавке чугуна и смешивания волокон. Решение задач линейного программирования с помощью различных приемов и математического программирования.
курсовая работа [94,6 K], добавлен 17.11.2016Основные понятия моделирования. Общие понятия и определение модели. Постановка задач оптимизации. Методы линейного программирования. Общая и типовая задача в линейном программировании. Симплекс-метод решения задач линейного программирования.
курсовая работа [30,5 K], добавлен 14.04.2004Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Характеристика и описание метода линейного программирования, основные области его применения и ограничения использования. Решение экономических задач, особенности формирования оптимизационной модели, расчет и анализ результатов оптимизации прибыли.
курсовая работа [99,0 K], добавлен 23.03.2010Определение оптимальных объемов производства по видам изделий за плановый период и построение их математической модели, обеспечивающей максимальную прибыль предприятию. Решение задачи по минимизации затрат на перевозку товаров средствами модели MS Excel.
курсовая работа [3,4 M], добавлен 26.05.2013