- •Лабораторный практикум
- •По дисциплине «Математические методы в экономике»
- •Часть 2 .Линейное и дискретное программирование
- •Для подготовки студентов по направлениям 080500 - менеджмент и 080100 - экономика
- •Лабораторный практикум по дисциплине «Математические методы в экономике» . Часть 1.Линейное и дискретное программирование. Уч. Пособие. М.: фгоу впо ргау - мсха им. К.А. Тимирязева, - 127 с.
- •Содержание
- •Введение
- •Лабораторная работа № 13 «Решение задач линейного программирования в приложении ms Excel «Поиск решения»»
- •Последовательность выполнения
- •Лабораторная работа № 14 «Метод искусственного базиса или м- метод»
- •Лабораторная работа №15-17 «Основы теории двойственности»
- •1 Экономический смысл двойственных задач
- •2 Правило записи двойственных задач. Симметричные двойственные задачи
- •3 Свойства двойственных задач. Основные теоремы двойственности
- •4 Запись оптимального решение двойственной задачи по оптимальному решению прямой задачи. Краткий анализ оптимального решения прямой задачи
- •Лабораторная работа №18 «Транспортная задача на минимум целевой функции»
- •Лабораторная работа № 19 «Особенности решения транспортной задачи на максимум»
- •Лабораторная работа № 20 Видоизменения транспортной задачи (блокировка перевозок, ограничение пропускной способности).
- •I. Общая постановка задачи
- •II. Общая постановка задачи
- •Лабораторная работа № 21 «Транспортная задача с учетом производственных затрат»
- •Лабораторная работа № 22 «Решение задач о назначениях»
- •1 Постановка задачи и математическая формализация условий
- •2 Венгерский алгоритм решения задачи на минимум целевой функции
- •3 Особенности решения задачи на максимум
- •Лабораторная работа №23 «Целочисленное программирование»
- •Лабораторная работа № 24 «Параметрическое программирование с параметром в целевой функции»
- •Алгоритм решения задач в полных симплексных таблицах на максимум целевой функции
- •Лабораторная работа № 25. «Параметрическая транспортная задача с параметром в целевой функции»
- •Алгоритм решения параметрической транспортной задачи с параметром в целевой функции
- •Глоссарий основных понятий
- •Рекомендуемая литература
Лабораторная работа № 14 «Метод искусственного базиса или м- метод»
Теоретическая часть
Правила перехода к М-задаче от исходной (основной) задачи
В ограничения типа меньше или равно () вводим неотрицательные дополнительные переменные с коэффициентом плюс единица.
В ограничения типа больше или равно () вводим неотрицательные дополнительные переменные с коэффициентом минус единица.
В ограничения, не содержащие базисные переменные, вводим неотрицательные искусственные базисные переменные yi.
В целевую функцию дополнительные переменные вводятся с нулевым коэффициентом.
В целевую функцию искусственные базисные переменные при решении задачи на максимум целевой функции вводятся с коэффициентом "-М", а при решении задачи на минимум целевой функции вводятся с коэффициентом "+М", где "М" большое положительное число: М 104.
Алгоритм М-метода решения задачи на максимум целевой функции
М-задача записывается в симплексную таблицу.
В первую строку симплексной таблицы записываются коэффициенты целевой функции, причем свободный член целевой функции записывается с противоположным знаком. В первый столбец записываются коэффициенты целевой функции при базисных переменных. Базисные переменные записываются во второй столбец.
Подсчитываются оценки по формуле оценок:
, j=0, 1,..., n
и записываются в последнюю строку таблицы.
Проверка решения на оптимальность по признаку: решение задачи на максимум целевой функции оптимально, если все оценки при переменных неотрицательные. Если критерий выполняется, то переход к пункту 12, если нет, то переход к пункту 5.
Разрешающий столбец выбирается по минимальной отрицательной оценке.
Если в разрешающем столбце есть хотя бы один положительный элемент, то переходим к пункту 7. Если нет, то целевая функция М-задачи не ограничена, переход к пункту 14.
Вычисляются симплексные отношения, то есть отношения неотрицательных свободных членов к строго положительным элементам разрешающего столбца и записываются в последний столбец.
По наименьшему симплексному отношению находится разрешающая строка.
На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.
Пересчет таблицы по общим правилам и заполнение новой таблицы.
Переход к пункту 4.
Запись оптимального решения М-задачи и значения целевой функции.
Если все искусственные переменные М-задачи равны нулю, то запись соответствующего решения основной задачи. Если хоты бы одна из искусственных переменных отлична от нуля, то необходимо корректировать условие основной задачи.
Если целевая функция М-задачи не ограничена, то необходимо в М-задачу ввести дополнительное ограничение:
х1+ х2+…+ хn М и решить новую М-задачу. Если после решения новая М-задача
а) будет иметь оптимальное решение с нулевыми искусственными переменными, то целевая функция основной задачи не ограничена;
б) будет иметь оптимальное решение с ненулевыми искусственными переменными, то система ограничений основной задачи несовместная.
Пример выполнения работы
П ример
К аноническая форма записи:
В системе ограничений канонической формы нет единичного базиса. Необходимо ввести в 1-е и 3-е ограничения искусственные базисные переменные и перейти к М-задаче. Получим:
№1 |
Cj |
0 |
4 |
2 |
1 |
0 |
0 |
-M |
-M |
7-2M |
со сс |
Ci |
П БП |
ai0 |
X1 |
X2 |
X3 |
X4 |
X5 |
Y1 |
Y2 |
KΣ |
|
-M |
Y1 |
8 |
1 |
1 |
1 |
-1 |
0 |
1 |
0 |
11 |
8 |
0 |
X5 |
8 |
2 |
1 |
1 |
0 |
1 |
0 |
0 |
13 |
4 i* |
-M |
Y2 |
15 |
3 |
2 |
1 |
0 |
0 |
0 |
1 |
22 |
5 |
Z |
j |
-23M |
-4M - - 4 j* |
-3M -2 |
-2M --1 |
M |
0 |
0 |
0 |
-31M -7 |
X |
№2 |
Cj |
0 |
4 |
2 |
1 |
0 |
0 |
-M |
-M |
7-2M |
со C0 |
Ci |
П БП |
ai0 |
X1 |
X2 |
X3 |
X4 |
X5 |
Y1 |
Y2 |
KΣ |
|
-M |
Y1 |
4 |
0 |
1/2 |
1/2 |
-1 |
-1/2 |
1 |
0 |
9/2 |
8 |
4 |
X1 |
4 |
1 |
1/2 |
1/2 |
0 |
1/2 |
0 |
0 |
13/2 |
8 |
-M |
Y2 |
3 |
0 |
1/2 |
-1/2 |
0 |
-3/2 |
0 |
1 |
5/2 |
6 i* |
Z |
j |
-7М+16 |
0 |
-М j* |
1 |
M |
2М+2 |
0 |
0 |
-5М+19 |
X |
№3 |
Cj |
0 |
4 |
2 |
1 |
0 |
0 |
-M |
-M |
7-2M |
со C0 |
Ci |
П БП |
ai0 |
X1 |
X2 |
X3 |
X4 |
X5 |
Y1 |
Y2 |
KΣ |
|
-M |
Y1 |
1 |
0 |
0 |
1 |
-1 |
1 |
1 |
-1 |
2 |
1 i* |
4 |
X1 |
1 |
1 |
0 |
1 |
0 |
2 |
0 |
-1 |
4 |
1 |
2 |
Х2 |
6 |
0 |
1 |
-1 |
0 |
-3 |
0 |
2 |
5 |
- |
|
j |
-М+16 |
0 |
0 |
-М+1 j* |
М |
-М+2 |
0 |
2М |
19 |
X |
№4 |
Cj |
0 |
4 |
2 |
1 |
0 |
0 |
-M |
-M |
7-2M |
Ci |
П БП |
ai0 |
X1 |
X2 |
X3 |
X4 |
X5 |
Y1 |
Y2 |
KΣ |
1 |
Х3 |
1 |
0 |
0 |
1 |
-1 |
1 |
1 |
-1 |
2 |
4 |
X1 |
0 |
1 |
0 |
0 |
1 |
1 |
-1 |
0 |
2 |
2 |
Х2 |
7 |
0 |
1 |
0 |
-1 |
-2 |
1 |
1 |
7 |
Z |
j |
15 |
0 |
0 |
0 |
1 |
1 |
М-1 |
М+1 |
2М+17 |
Так как все оценки при переменных неотрицательные, то решение М-задачи оптимальное. Так как все оценки при свободных переменных не равны нулю, то оптимальное решение единственное. Хм*(0,7,1,0,0,0,0), max Zм = 15.
Искусственные переменные в оптимальном решении равны нулю, поэтому их можно отбросить и получить соответствующее оптимальное решение основной задачи: Х*(0,7,1,0,0), max Z = 15. Базисная переменная Х1 равна нулю, поэтому оптимальное решение – вырожденное.
Список индивидуальных заданий
Задание. Решить задачу.
1. min Z= x1+x2+5 4x1 + x2 2 x1+x2 6 x1 3 x1 0; x2 0
|
2. max Z= x1 + x2 +5 x1+ 2x2 2 3x1+ x2 3 x1+x2 4 x1 0; x2 0
|
3. max Z= 2x1+x2+4 -x1 + 2x2 3 x1+ 2x2 7 x1 0; x2 0 |
4. max Z= -x1-2x2+5 x1 + x2 1 x2 1 x1 0; x2 0 |
5. min Z= x2+6 x1 + x2 1 x1+x2 2 x1-x2 3 x1 0; x2 0;
|
6. min Z= -x1-2x2+3 x1 + x2 1 x2 1 x1 0; x2 0 |
7. min Z= x1 + x2 +5 x1+ 4x2 2 x1+ x2 6 x1 0; x2 0
|
8. max Z= x1 - x2 +3 x1+ x2 1 x1+ x2 2 x1 0; x2 0
|
9. max Z= x2+6 x1 + x2 1 x1+x2 2 x1-x2 3 x1 0; x2 0;
|
10. min Z= x2 -5 x1 + x2 1 x1+x2 2 x1-x2 3 x1 0; x2 0; |
11. min Z= 2x1 + x2 +4 x1+ x2 3 x1- x2 2 x1 0; x2 0
|
12. min Z= x1+x2+5 x1 + 4x2 2 x1+x2 6 x1 3 x1 0; x2 0
|
13. max Z= 2x1 +5 x1 + 2x2 3 2x1+x2 3 x1 0; x2 0; |
14. max Z= 2x1 - x2 +6 x1+ x2 4 2x1- x2 1 x1 0; x2 0
|
15. max Z= x1 + 2x2 +5 x1+ 3x2 3 2x1+ x2 3 x1+x2 4 x1 0; x2 0 |
16. Суточный рацион коровы должен содержать не менее 14,2 кг корм. ед. и 1650 г протеина. Концентратов должно быть не более 3,6 кг.
Таблица 1. Содержание питательных веществ в 1 кг корма и себестоимость 1 кг корма
Показатель |
Зерно озимого ячменя |
Солома |
Зеленый корм люцерны |
Содержится в 1 кг корма: кормовых единиц, кг к.ед. |
1,2 |
0,2 |
0,2 |
переваримого протеина, г |
80 |
18 |
35 |
Стоимость 1 кг корма, ден. ед |
11 |
2 |
2,1 |
Найти оптимальное сочетание кормов, обеспечивающее минимум себестоимости рациона.
17. Возделываются картофель и ячмень. Картофеля должно быть произведено не менее 20000 ц, ячменя - не менее 3000 ц.
Таблица 2. Наличие ресурсов и их затраты на производство 1 ц картофеля и ячменя
Показатель |
Затраты на 1 ц |
Объем ресурсов |
|
картофеля |
ячменя |
||
Пашня, га |
0,01 |
0,05 |
1000 |
Трудовые ресурсы чел.-ч |
1,6 |
0,8 |
64000 |
Трудовые ресурсы механизоторов, тракторо-смен |
0,021 |
0,03 |
900 |
Цена реализации 1 ц, ден. ед. |
3 |
5 |
|
Найти оптимальное сочетание посевов сельскохозяйственных культур, обеспечивающее максимум производства валовой продукции в стоимостном выражении.
18. Производится зерно, сахарная свекла на корм и мясо свиней. На корм используется 60% валового сбора зерна и весь сбор сахарной свеклы.
Таблица 3. Наличие ресурсов и их затраты на производство 1 ц
Показатель |
Зерно |
Свекла |
Привес свиней |
Объем ресурсов |
Затраты пашни на производство 1ц, га |
0,05 |
0,005 |
|
5000 |
Затраты труда на 1 ц, чел.-ч |
0,8 |
1,5 |
16 |
80000 |
Содержание ц кормовых единиц в 1 ц |
1,2 |
0,26 |
|
|
Затраты корма на 1 ц привеса, ц к.ед. |
|
|
5 |
|
Прибыль от реализации 1 ц, ден. ед. |
5 |
3 |
60 |
|
Найти оптимальное сочетание производства зерна, сахарной свеклы на корм и мяса свиней, обеспечивающее максимум прибыли.
19. Составить условия размещения производства в хозяйстве в двух отделениях.
Таблица 4. Наличие ресурсов и их затраты на 1 ц
Показатель |
I отделение |
II отделение |
Пшеница |
|
|
Затраты на 1 ц: |
|
|
пашни, га |
0,05 |
0,06 |
труда, чел.-ч |
0,80 |
0,90 |
Подсолнечник |
|
|
Затраты на 1 ц: |
|
|
пашни, га |
0,06 |
0,07 |
труда, чел.-ч |
0,40 |
0,40 |
Сахарная свекла |
|
|
Затраты на 1 ц: |
|
|
пашни, га |
0,003 |
0,002 |
труда, чел.-ч |
1,9 |
2,40 |
Объем ресурсов в двух отделениях: |
|
|
пашни, га |
500 |
600 |
труда, чел.-ч |
80000 |
96000 |
В хозяйстве необходимо произвести 1200 ц пшеницы, 9000 ц подсолнечника, 12000 ц сахарной свеклы. Цена реализации 1 ц пшеницы - 14 денежных единиц, подсолнечника - 18 денежных единиц, сахарной свеклы - 10 денежных единиц.
Найти оптимальное сочетание посевов сельскохозяйственных культур, обеспечивающее максимум валовой продукции в стоимостном выражении.
20. Имеются ресурсы: пашни – 500 га, трудовые ресурсы – 6000 чел.-дн., материально денежных средств – 1000000 ден.ед.
Таблица 5. Затраты ресурсов на 1 га, урожайность и выход продукции с 1 га культур
Культуры |
Урожайность, ц/га |
Затраты ресурсов на 1 га |
Выход продукции с 1 га, ден.ед. |
|
трудовых, чел.-дн. |
материально- денежных средств, ден.ед. |
|||
Пшеница |
20 |
4 |
100 |
20 |
Ячмень |
24 |
4 |
50 |
25 |
Капуста |
500 |
8 |
150 |
30 |
Пшеницы должно быть произведено не менее 2000 ц. Ресурсы могут быть недоиспользованы.
Найти оптимальное сочетание посевов сельскохозяйственных культур, обеспечивающее максимум производства валовой продукции в стоимостном выражении.
21. Имеются ресурсы: пашни – 500 га, трудовые ресурсы – 6000 чел.-дн., материально-денежных средств – 100000 ден.ед.
Таблица 6. Затраты ресурсов на 1 га, урожайность и выход продукции с 1 га культур
Культуры |
Урожайность, ц/га |
Затраты ресурсов на 1 га |
Выход продукции с 1 га, ден.ед. |
|
трудовых, чел.-дн. |
материально- денежных средств, ден.ед. |
|||
Пшеница |
20 |
4 |
100 |
20 |
Ячмень |
24 |
4 |
50 |
25 |
Корнеплоды |
300 |
8 |
150 |
30 |
Зерновых должно быть произведено не менее 3000 ц. Ресурсы могут быть недоиспользованы.
Найти оптимальное сочетание посевов сельскохозяйственных культур, обеспечивающее максимум производства валовой продукции в стоимостном выражении.
Контрольные вопросы
Всегда ли М-задача имеет исходное опорное решение?
Всегда ли М-задача имеет оптимальное решение?
Всегда ли основная задача имеет оптимальное решение?
Что можно сказать о решении основной задачи, если все искусственные переменные равны нулю?
Что можно сказать о решении основной задачи, если не все искусственные переменные равны нулю?