Полный текст:
Задача №1
Предприятие предполагает
выпускать два вида продукции А1 и А2, для производства которых используется
сырье трех видов. Производство обеспечено сырьем каждого вида в количествах: 401,
596, 300 кг. На изготовление единицы изделия А1 требуется затратить сырья
каждого вида 5, 6, 1 кг, соответственно, а для единицы изделия А2 - 1, 4, 3 кг.
Прибыль от реализации единицы изделия А1 составляет 60 д. ед., для единицы
изделия A2 - 33 д. ед.
Требуется составить план
производства изделий А1 и A2, обеспечивающий максимальную прибыль предприятия
от реализации готовой продукции.
Требуется:
1. Решить
задачу без использования ПЭВМ:
1.Сформулировать
и записать математическую модель задачи
1.2. Найти решение полученной
модели графически
1.3 Найти решение задачи
используя симплекс-метод ("Поиск решения"). Написать выводы.
1.4. Определить
интервалы устойчивости полученного решения по отношению к изменению прибыли на
единицу продукции
1.5. Определить теневые цены и
интервалы их устойчивости по отношению к изменению ресурсов. Указать
критическую точку данной производственной модели.
1.6. Оценить стоимость готовой
продукции, при изменении сырья каждого вида на величину ?bi. Найти новый
оптимальный план.
1.7. Сформулировать двойственную
задачу и найти ее решение. Проверить выполнение теорем двойственности.
2. Решить
задачу с помощью пакета MS Exel .
Таблица 1- Исходные данные для задачи 1
Вид сырья
Продукция
Ограничения по сырью
Изменения запасов
А1
А2
1-й
5
1
401
259
2-й
6
4
596
280
3-й
1
3
300
0
Прибыль
60
33
Решение:
- количество продукта
А1; - количество продукта
А2.
Тогда задача линейного
программирования выглядит следующим образом:
1.2 Графический метод решения задачи линейного
программирования.
Построим многоугольник допустимых решений.
Рисунок 1-Многоугольник решений ОABCD
Определим градиент целевой функции .
Рисунок 2 –Графическое
решение
Так как нас интересует максимальное решение,
поэтому двигаем прямую до последнего касания обозначенной области. Последней
точкой, которой каснется прямая будет точка C. Точка С
– это точка пересечения прямых и .
Находим значение целевой функции .
Оптимальный план производства: 72
ед. продукта А1 и 41 ед. продукта А2.
1.3 Симплекс –метод.
Каконоическая форма
В качестве базиса выберем .
Таблица 2- Симплекс таблица 1
Базис
Свободный член
Переменные
Оценочное отношение
401
5
1
1
0
0
801/5
596
6
4
0
1
0
991/3
300
1
3
0
0
1
300
Z
0
-60
-33
0
0
0
0
Разрешающий
элемент 5. Вместо в базис вводим .
Таблица 3- Симплекс
таблица 2
Базис
Свободный член
Переменные
Оценочное отношение
801/5
1
1/5
1/5
0
0
401
1144/5
0
24/5
-11/5
1
0
41
2194/5
0
24/5
-1/5
0
1
781/2
Z
4812
0
-21
12
0
0
0
Разрешающий
элемент 24/5 . В базис вместо вводим .
Таблица 4- Симплекс
таблица 3
Базис
Свободный
член
Переменные
Оценочное
отношение
72
1
0
2/7
-1/14
0
41
0
1
-3/7
5/14
0
105
0
0
1
-1
1
Z
5673
0
0
3
71/2
0
Последняя строка
не содержит отрицательных значений, значит план
оптимальный. Zmax=5673, Х*=(72,41;0;0; 105).
1.4 Воспользуемся приложением «Поиск решения» и определим интервалы устойчивости полученного
решения по отношению к изменению прибыли на единицу продукции.
Рисунок 3- Интервалы
устойчивости полученного решения
Нормированная
стоимость представляет собой дополнительные двойственные переменные. Они
показывают, насколько по модулю уменьшится целевая функция при принудительном
выпуске единицы данной продукции. Нормированная стоимость для каждого продукта А1 и А2 равняется нулю, то есть целевая
функция не уменьшиться при принудительном увеличении принудительном выпуске
единицы данных видов продукции. И продукт А1 и продукт А2 рентабельны.
Допустимое
увеличение показывает, насколько максимально можно увеличить коэффициент целевой
функции (то есть цену продукта), чтобы структура оптимального плана осталась
прежней. Допустимое уменьшение, наоборот, показывает, насколько можно
максимально уменьшить коэффициент целевой функции, чтобы осталась прежней
структура оптимального плана. То есть, чтобы
выпуск продукта А1 оставался рентабельным, максимально допустимое
увеличение его цены составляет примерно 105 ден. ед. Допустимое уменьшение 10,5ден. ед. Чтобы
выпуск продукта А2 оставался рентабельным, максимально допустимое
увеличение его цены составляет приблизительно 7 ден.
ед., допустимое уменьшение 21 ден. ед.
1.5. Определим теневую цену.
Рисунок 4- Теневая цена
Теневая цена представляет собой двойственные переменные.
Они показывают, как изменится целевая функция при изменения запаса ресурса на
единицу. Если ресурс использован полностью, то теневая цена этого ресурса
положительна. В нашем примере полностью
используются ресурсы вида 1 и 2, и их
теневые цены положительны. Если мы увеличим запас 1-го вида сырья на единицу, то ЦФ возрастёт на 3 ден. ед., если мы увеличим
запас 2- го вида сырья на единицу, то ЦФ возрастёт на 7,5 ден.ед.
Рисунок
5– Отчет по результатам
Несвязанным ограничением является третье ограничение. То есть ресурс вида 3
используется не полностью. Остаток ресурса составляет 105 ед.
Рисунок
6 – Отчет по пределам
В отчёте по пределам указаны значения ЦФ при выпуске
данного типа продукции на нижнем и верхнем пределах. Если будет выпускаться продукт А1, то значение
прибыли будет составлять 1353 ден.ед. Если будет выпускаться продукт А2 значение
прибыли будет составлять 4320ден.ед.
1.6 Оценим стоимость готовой продукции, при
изменении сырья каждого вида на заданную
в условии величину.
, - матрица, состоящая
из столбцов первоначального базиса () последней симплекс-таблицы:
Получаем, ; ; .
.
Все компоненты вектора положительны , то есть выполняется условие
. Значит,
при заданных изменениях запаса сырья двойственные оценки не изменятся. Это говорит
о том, что первый и второй виды сырья будут
по-прежнему использоваться полностью.
Отсюда находим новый план .
Новый оптимальный план Х**=(126;30).
Новая стоимость продукции Z нов. max (Х**)=60*126+33*30=8550 ден. ед.
Составим двойственную задачу к прямой задачи.
Y = C*A-1.
Y = C*A-1 =
Получаем оптимальный
план двойственной задачи: y1 = 3; y2 = 15/2; y3
= 0.
Оптимальное решение двойственной находится в индексной строке последней
симплекс-таблицы и столбцах, соответствующих первоначальному базису (вторая теорема двойственности).
Z(Y) = 401*3+596*15/2+300*0 = 5673. Получаем, что Zmax. ( первая теорема двойсвенности).
Как видим, оптимальное решение двойственной находится в индексной строке последней
симплекс-таблицы и столбцах, соответствующих первоначальному базису.
Z(Y) = 794*2+819*6+636*0 = 6502. Получаем, что Zmax. ( Первая теорема двойсвенности).
Задача №2
По заданной таблице 2.1
ожидаемой прибыли как функции полных капиталовложений, используя метод
динамического программирования, построить таблицу получения оптимальной прибыли
от вложения капитала от 1 до 10 млн. ден. ед. в три фонда: А, В и С. По
полученной таблице найти максимальную прибыль и распределение вложений в
предприятия при наличии суммарного капитала величиной S =8 млн. ден. ед.
Таблица 5 - Исходные данные к задачи №2
Вложения,
млн.ден.ед.
0
1
2
3
4
5
6
7
8
А
0
0,25
0,41
0,55
0,65
0,75
0,80
0,85
0,88
B
0
0,28
0,45
0,65
0,78
0,90
1,02
1,13
1,23
C
0
0,29
0,46
0,58
0,64
0,70
0,76
0,82
0,85
Решение:
Если j-ый фонд вкладывают - объем инвестиций, то прирост прибыли составит млн. ден.ед. Найдем
такое распределение
инвестиций между фондами, которое максимизирует прибыль.
Заполняем таблицу 2.2.
Значения складываем со
значениями и на каждой северо-восточной диаганали находим наибольшее число (выделено полужирным цветом)
и указываем соответствующее значение .
Таблица 6 – Первый оптимизационный шаг
0
1
2
3
4
5
6
7
8
0
0,25
0,41
0,55
0,65
0,75
0,80
0,85
0,88
0
0
0
0,25
0,41
0,55
0,65
0,75
0,80
0,85
0,88
1
0,28
0,28
0,53
0,69
0,83
0,93
1,03
1,08
1,13
2
0,45
0,45
0,70
0,86
1,00
1,10
1,20
1,25
3
0,65
0,65
0,90
1,06
1,20
1,30
1,40
4
0,78
0,78
1,03
1,19
1,33
1,43
5
0,9
0,90
1,15
1,31
1,45
6
1,02
1,02
1,27
1,43
7
1,13
1,13
1,38
8
1,23
1,23
На основании таблицы 2.3 заполняем таблицу 2.4.
Таблица 7 – Значения
0
1
2
3
4
5
6
7
8
0
0,28
0,53
0,70
0,90
1,06
1,20
1,33
1,45
0
1
1
2
3
3
3
4
5
Таблица 8 – Второй оптимизационный шаг
0
1
2
3
4
5
6
7
8
0
0,28
0,53
0,70
0,90
1,06
1,20
1,33
1,45
0
0
0
0,28
0,53
0,70
0,90
1,06
1,20
1,33
1,45
1
0,29
0,29
0,57
0,82
0,99
1,19
1,35
1,49
1,62
2
0,46
0,46
0,74
0,99
1,16
1,36
1,52
1,66
3
0,58
0,58
0,86
1,11
1,28
1,48
1,64
4
0,64
0,64
0,92
1,17
1,34
1,54
5
0,70
0,70
0,98
1,23
1,40
6
0,76
0,76
1,04
1,29
7
0,82
0,82
1,10
8
0,85
0,85
Наибольший элемент на последней диаганале, соответствует
максимуму прибыли- 1,66 млн.ден.ед. =2 млн. ден.ед.; млн. ден.ед.; млн. ден.ед.
Таким образом, наилучшим
является следующее распределение капиталовложений по фондам: в Фонд А вложить 3
млн.ден.ед., в Фонд В вложить 3 млн.ден.ед., в Фонд С вложить 2 млн.
ден.ед. Тогда прибыль будет максимальна 1,66
млн.ден.ед.
Задача №3
Хозяйство располагает следующими
ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство
производит четыре вида продукции П1, П2, П3, П4.
Организация производства характеризуется следующей таблицей 9.
Таблица 9 – Исходные данные к задаче №3
Продукция
Затраты
на 1 ед. продукции
Доход
от единицы продукции
площадь
труд
тяга
П1
2
2
2
1
П2
3
1
3
4
П3
4
2
1
3
П4
5
4
1
5
Составьте план выпуска
продукции, обеспечивающий хозяйству максимальную прибыль.
Решение
Пусть х1— количество продукта П1 ; х2 — количество продукта П2.; х3— количество продукта П3;
х4— количество продукта П4.
Целевая
функция
Составим систему ограничений задачи:
Задача
линейного программирования:
Используя
«Поиск решения» решим данную задачу.
Рисунок 7- Исходные данные
Рисунок 8 – Поиск решения
Рисунок 9– Параметры поиска решения
Рисунок 10 – Результаты
То есть необходимо
производить продукт П2 в количестве 25, а продукт П4 в
количестве 5, продукты П1 и П3 производить не нужно.
Тогда прибыль будет максимальной 125.
Список
литературы
Вентцель Е.С. Исследование
операций. – М.: Наука, 1980. – 448 с.Высшая математика для
экономистов: практикум/под.ред. Н.Ш. Кремера – М.: Высшее образование, 2006. –
232 с.Колемаев В.А. Математическая экономика . – М.:
Фмнстатинформ, 1999. – 540 с.