Экономико-математическое моделирование

Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей X и Y. Завод располагает фондом рабочего времени в 4000 чел.–ч. в неделю

ВНИМАНИЕ! Работа на этой странице представлена для Вашего ознакомления в текстовом (сокращенном) виде. Для того, чтобы получить полностью оформленную работу в формате Word, со всеми сносками, таблицами, рисунками (вместо pic), графиками, приложениями, списком литературы и т.д., необходимо скачать работу.

1. Завод-производитель высокоточных элементов для автомобилей выпускает два различных типа деталей X и Y. Завод располагает фондом рабочего времени в 4000 чел.–ч. в неделю. Для производства одной детали типа X требуется 1 чел.–ч., а для производства одной детали типа Y – 2 чел.-ч. Производственные мощности завода позволяют выпускать максимум 2250 деталей типа X и 1750 деталей типа Y в неделю. Каждая деталь типа X требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла. Уровень запасов каждого вида металла составляет 10000 кг в неделю. Кроме того, еженедельно завод поставляет 600 деталей типа X своему постоянному заказчику. Существует также профсоюзное соглашение, в соответствии с которым общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.
Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа X составляет 30 ден. ед., а от производства одной детали типа Y – 40 ден. ед.?
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум и почему?

Решение. Данная задача относится к классу задач линейного программирования, и ее можно решить графическим способом (см. рис. 1).
Построим математическую модель задачи:

Экономическая интерпретация данной модели такова:
• первое неравенство гарантирует, что сумма рабочего времени, используемого на производство одной детали типа X и производства одной детали типа Y, не превысит установленного лимита в 4000 чел.–ч. в неделю;
• второе и третье неравенства описывают потребление листового металла и металлических стержней при производстве деталей типов X и Y, причем количества указанных материалов при производстве этих деталей не должно превышать 10000 кг в неделю;
• четвертое неравенство описывает условие профсоюзного соглашения, когда общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук;
• пятое и шестое неравенства гарантируют, что завод–производитель не произведет за неделю деталей типов X и Y больше, чем позволяют его производственные мощности;
• седьмое неравенство описывает минимальную поставку деталей типа Х заводом–изготовителем постоянному заказчику в размере 600 штук;
• и, наконец, восьмое неравенство обеспечивает тот факт, что минимальное количество произведенных деталей типа Y не будет отрицательным.
На рисунке 1 пунктирной линией показана целевая функция , перемещающаяся вдоль вектора–градиента , указывающего направление наибольшего возрастания этой функции цели.

Рис. 1.
Графическое решение задачи линейного программирования находится в точке В, т.к. в этой точке целевая функция достигает максимального значения в области ограничений . Найдем координаты этой точки, решив систему уравнений:

Следовательно, оптимальное решение задачи соответствует точке , т.е. предприятие при получении максимальной прибыли в размере ден. ед. должно изготавливать каждую неделю деталей типа Х в размере 1500 штук, а деталей типа Y – 1250 штук.
На рисунках 2 и 3 продемонстрированы этапы решения данной задачи ЛП средствами в модуле «Поиск решения…». В ячейке записано выражение, описывающее целевую функцию, а в ячейках определены изменяемые значения переменных и соответственно. В поле «Ограничения» записана система ограничений .

Рис. 2.

В результате решения задачи ЛП мы получили оптимальные значения переменных и , равных соответственно 1500 и 1250 штук деталей, это показано на рисунке 3 в ячейках , которые определяют максимальное значение целевой функции в ячейке , равное 95000 ден.ед.

Рис. 3.

Сформулируем двойственную задачу ЛП на минимум и решим ее тоже средствами .

Рис. 4.
Если решать данную задачу на минимум, то оптимальным решением будет точка (см. рис. 4 – ячейки ), в ней целевая функция достигает минимального значения, равного 95000 ден. ед.

2.7. Предприятие выпускает четыре вида продукции и использует три вида оборудования: токарное, фрезерное, шлифовальное. Общий фонд рабочего времени оборудования каждого вида, нормы расхода и цены реализации единицы каждого вида продукции приведены в таблице.

Тип оборудования Нормы расхода ресурса на одно изделие Фонд раб. времени, ч.
А Б В Г
Токарное 2 1 1 3 300
Фрезерное 1 0 2 1 70
Шлифовальное 1 2 1 0 340
Цена изделия 8 3 2 1
Требуется:
1) Сформулировать прямую оптимизационную задачу на максимум выручки от реализации готовой продукции, получить оптимальный план выпуска продукции.
2) Сформулировать двойственную задачу и найти ее оптимальный план с помощью теорем двойственности.
3) Пояснить нулевые значения переменных в оптимальном плане.
4) На основе свойств двойственных оценок и теорем двойственности:
• проанализировать использование ресурсов в оптимальном плане исходной задачи;
• определить, как изменятся выручка и план выпуска продукции, если фонд рабочего времени шлифовального оборудования увеличить на 24 часа;
• оценить целесообразность включения в план изделия "Д" ценой 11 ед., если нормы затрат оборудования 8, 2 и 2 ед. соответственно.

Решение.
1) Сформулируем математическую модель задачи по определению максимальной выручки от реализации готовой продукции видов А, Б, В, Г. Пусть количество выпускаемой продукции соответствующих типов, тогда имеет место задача оптимизации

Решим данную задачу линейного программирования симплекс–методом, будем для этого использовать программный продукт SimplexWin 3.1. В следующей таблице приведены результаты работы программы в виде пошаговых симплекс–таблиц, а на рисунке 5 проиллюстрированы скрин–шоты этой программы.

Шаг 0
Базис БП x1 x2 x3 x4 x5 x6 X7
x5 300 2 1 1 3 1 0 0
x6 70 1 0 2 1 0 1 0
x7 340 1 2 1 0 0 0 1
ИС 0 -8 -3 -2 -1 0 0 0
Шаг 1
Базис БП x1 x2 x3 x4 x5 x6 x7
x5 160 0 1 -3 1 1 -2 0
x1 70 1 0 2 1 0 1 0
x7 270 0 2 -1 -1 0 -1 1
ИС 560 0 -3 14 7 0 8 0
Шаг 2
Базис БП x1 x2 x3 x4 x5 x6 x7
x5 25 0 0 -5/2 3/2 1 -3/2 -1/2
x1 70 1 0 2 1 0 1 0
x2 135 0 1 -1/2 -1/2 0 -1/2 1/2
ИС 965 0 0 25/2 11/2 0 13/2 3/2

Рис. 5.

Таким образом, оптимальным планом выпуска продукции является план , при котором максимальная выручка составит 965.
Проверим данное решение средствами , для этого в ячейке сформируем формулу, определяющую значение целевой функции , а в изменяемых ячейках зададим начальные значения переменных задачи ЛП (см. рис. 6). Далее запишем в ячейках условия, характеризующие ограничения

Рис. 6.

Рис. 7.
На рисунке 3 в изменяемых ячейках найдено оптимальное решение задачи ЛП, а именно – оптимальный план выпуска продукции, при котором максимальная выручка составит 965.

2), 3) Сформулируем двойственную задачу линейного программирования и найдем ее оптимальный план с помощью теорем двойственности.

Решение двойственной задачи найдем исходя условий:

Учитывая, что из системы (2) получим, что и система (1) принимает вид:

Значение целевой функции при оптимальном плане равно ден. ед.
Сравнивая результаты решения прямой и двойственной задач линейного программирования, делаем вывод, что значения целевых функций при оптимальных планах совпадают. Нулевые значения величин выпусков изделий типов В и Г в прямой задаче говорят о том, что эти виды изделий с большими издержками при их производстве на различных типах оборудования невыгодны предприятию и их доля при формировании дохода предприятия несущественна.

5) Определим, как изменится выручка и план выпуска продукции, если фонд рабочего времени шлифовального оборудования увеличить на 24 часа.
Для этого в последнем неравенстве области ограничений изменим величину фонда рабочего времени с 340 на 364, получим математическую модель:

Решим данную задачу линейного программирования симплекс–методом, используя программный продукт SimplexWin 3.1, получим пошаговые симплекс–таблицы.

Шаг 0
Базис БП x1 x2 x3 x4 x5 x6 x7
x5 300 2 1 1 3 1 0 0
x6 70 1 0 2 1 0 1 0
x7 364 1 2 1 0 0 0 1
ИС 0 -8 -3 -2 -1 0 0 0
Шаг 1
Базис БП x1 x2 x3 x4 x5 x6 x7
x5 160 0 1 -3 1 1 -2 0
x1 70 1 0 2 1 0 1 0
x7 294 0 2 -1 -1 0 -1 1
ИС 560 0 -3 14 7 0 8 0
Шаг 2
Базис БП x1 x2 x3 x4 x5 x6 x7
x5 13 0 0 -5/2 3/2 1 -3/2 -1/2
x1 70 1 0 2 1 0 1 0
x2 147 0 1 -1/2 -1/2 0 -1/2 1/2
ИС 1001 0 0 25/2 11/2 0 13/2 3/2

Результаты работы программы приведены на рисунке 8 . Анализируя полученные результаты можно сказать, что при увеличении фонда рабочего времени шлифовального оборудования на сутки оптимальный план выпуска продукции изменится , а максимальная выручка при этом составит 1001, что на 36 больше, если бы фонд рабочего времени остался бы прежним–340 часов.

Рис. 8.

5) Оценим целесообразность включения в план изделия "Д" ценой 11 ед., если нормы затрат оборудования 8, 2 и 2 ед. соответственно. Размерность математической модели увеличится на единицу, так как добавится новая переменная .

Опять решим данную задачу линейного программирования симплекс–методом, используя программный продукт SimplexWin 3.1, получим пошаговые симплекс–таблицы.

Шаг 0
Базис БП x1 x2 x3 x4 x5 x6 x7 x8
x6 300 2 1 1 3 8 1 0 0
x7 70 1 0 2 1 2 0 1 0
x8 340 1 2 1 0 2 0 0 1
ИС 0 -8 -3 -2 -1 -11 0 0 0
Шаг 1
Базис БП x1 x2 x3 x4 x5 x6 x7 x8
x6 20 -2 1 -7 -1 0 1 -4 0
x5 35 1/2 0 1 1/2 1 0 1/2 0
x8 270 0 2 -1 -1 0 0 -1 1
ИС 385 -5/2 -3 9 9/2 0 0 11/2 0
Шаг 2
Базис БП x1 x2 x3 x4 x5 x6 x7 x8
x2 20 -2 1 -7 -1 0 1 -4 0
x5 35 1/2 0 1 1/2 1 0 1/2 0
x8 230 4 0 13 1 0 -2 7 1
ИС 445 -17/2 0 -12 3/2 0 3 -13/2 0
Шаг 3
Базис БП x1 x2 x3 x4 x5 x6 x7 x8
x2 1870/13 2/13 1 0 -6/13 0 -1/13 -3/13 7/13
x5 225/13 5/26 0 0 11/26 1 2/13 -1/26 -1/13
x3 230/13 4/13 0 1 1/13 0 -2/13 7/13 1/13
ИС 8545/13 -125/26 0 0 63/26 0 15/13 -1/26 12/13
Шаг 4
Базис БП x1 x2 x3 x4 x5 x6 x7 x8
x2 135 0 1 -1/2 -1/2 0 0 -1/2 1/2
x5 25/4 0 0 -5/8 3/8 1 1/4 -3/8 -1/8
x1 115/2 1 0 13/4 1/4 0 -1/2 7/4 1/4
ИС 3735/4 0 0 125/8 29/8 0 -5/4 67/8 17/8
Шаг 5
Базис БП x1 x2 x3 x4 x5 x6 x7 x8
x2 135 0 1 -1/2 -1/2 0 0 -1/2 1/2
x6 25 0 0 -5/2 3/2 4 1 -3/2 -1/2
x1 70 1 0 2 1 2 0 1 0
ИС 965 0 0 25/2 11/2 5 0 13/2 3/2

Результаты работы программы приведены на рисунке 9 . Анализируя полученные результаты, можно сказать, что при добавлении нового вида продукции с соответствующими нормами затрат на ее производство по видам оборудования, оптимальный план выпуска продукции не изменится , а максимальная выручка при этом составит тоже значение 965, что и в исходной задаче. Следовательно, предприятие может перейти на выпуск не трех, а четырех видов продукции, не теряя общего дохода.

Рис. 9.

1.7. Фирма рекламирует свою продукцию с использованием четырех средств: телевидения, радио, газет и афиш. Из различных рекламных экспериментов, которые проводились в прошлом, известно, что эти средства приводят к увеличению прибыли соответственно на 10, 3, 7 и 4 у.е. в расчете на 1 у.е., затраченную на рекламу.
Распределение рекламного бюджета по различным средствам подчинено следующим ограничениям:
а) полный бюджет не должен превосходить 500 000 у.е.;
б) следует расходовать не более 40 % бюджета на телевидение и не более 20 % бюджета на афиши;
в) вследствие привлекательности для подростков радио на него следует расходовать, по крайней мере, половину того, что планируется на телевидение.
Сформулируйте задачу распределения средств по различным источникам как задачу линейного программирования и решите ее.

Решение. Сформулируем математическую модель данной задачи как задачу линейного программирования (ЛП). Пусть количество средств (у.е.), выделяемых фирмой на рекламу своей продукции, соответственно, на телевидение, радио, газеты и афиши. Тогда целевая функция, описывающая функцию получения прибыли от реализации рекламной кампании будет иметь вид:
.

Сформулируем систему ограничений .

Найдем максимальное значение целевой функции на системе ограничений, т.е. .
Решим задачу ЛП симплекс–методом, составляя на каждом шаге метода таблицы, в столбцах которых зеленым цветом выделены те переменные, которые вводятся в базисное решение, а в строках показаны переменные, выводящиеся из базиса.

Шаг 0
Базис БП x1 x2 x3 x4 x5 x6 x7 x8 z1
x5 500000 1 1 1 1 1 0 0 0 0
x6 200000 1 0 0 0 0 1 0 0 0
x7 100000 0 0 0 1 0 0 1 0 0
z1 100000 0 1 0 0 0 0 0 -1 1
ИС -100000M -10 -M-3 -7 -4 0 0 0 M 0
Шаг 1
Базис БП x1 x2 x3 x4 x5 x6 x7 x8 z1
x5 400000 1 0 1 1 1 0 0 1 -1
x6 200000 1 0 0 0 0 1 0 0 0
x7 100000 0 0 0 1 0 0 1 0 0
x2 100000 0 1 0 0 0 0 0 -1 1
ИС 300000 -10 0 -7 -4 0 0 0 -3 M+3

Шаг 2
Базис БП x1 x2 x3 x4 x5 x6 x7 x8 z1
x5 200000 0 0 1 1 1 -1 0 1 -1
x1 200000 1 0 0 0 0 1 0 0 0
x7 100000 0 0 0 1 0 0 1 0 0
x2 100000 0 1 0 0 0 0 0 -1 1
ИС 2300000 0 0 -7 -4 0 10 0 -3 M+3
Шаг 3
Базис БП x1 x2 x3 x4 x5 x6 x7 x8 z1
x3 200000 0 0 1 1 1 -1 0 1 -1
x1 200000 1 0 0 0 0 1 0 0 0
x7 100000 0 0 0 1 0 0 1 0 0
x2 100000 0 1 0 0 0 0 0 -1 1
ИС 3700000 0 0 0 3 7 3 0 4 M-4

В последней симплекс–таблице все оценки (см. нижнюю строку) имеют неотрицательные значения, следовательно, найдено оптимальное решение задачи ЛП, т.е. , при этом значение функции достигает своего максимального значения у.е.
Оптимальный план решения задачи распределения рекламных средств рекомендует фирме выделить одинаковое количество денежных средств 200000 у.е. на телевидение и газеты, меньшее количество – 100000 у.е. на радио и ничего не выделять на рекламные афиши. На рисунке 10 представлены результаты работы программы SimplexWin 3.1.

Рис. 10.

2.7. В распоряжении некоторой компании имеется 6 торговых точек и 5 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в таблице.

Прода–вец Объемы продаж по торговым точкам,
USD/тыс. шт.

I II III
72 75
60 58 III 40
42 47
70 68 IV V VI
А 68 72 75 83 75 69
В 56 60 58 63 61 59
С 35 38 40 45 25 27
D 40 42 47 45 53 36
Е 62 70 68 67 69 70

Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимального объема продаж?

Решение. Алгоритм решения задачи о назначениях предполагает минимизацию ее целевой функции. Если имеется задача о назначениях, целевую функцию которой нужно максимизировать, то поступают таким образом, все ее элементы умножаются на (–1). Исходная таблица не является квадратной, поэтому в нее следует включить дополнительную фиктивную строку, необходимую для приведения ее к квадратной форме. Пусть значения стоимости, соответствующие фиктивным клеткам, будут равны нулю, тогда таблица будет иметь вид.

Прода–вец Объемы продаж по торговым точкам,
USD/тыс. шт.

I II III
72 75
60 58 III 40
42 47
70 68 IV V VI
А –68 –72 –75 –83 –75 –69
В –56 –60 –58 –63 –61 –59
С –35 –38 –40 –45 –25 –27
D –40 –42 –47 –45 –53 –36
Е –62 –70 –68 –67 –69 –70
F 0 0 0 0 0 0
Назначения, размещаемые в клетках фиктивной строки F, будем считать фактически не существующими.
Найдем минимальный элемент каждой строки, получим таблицу.
Прода–вец

Объемы продаж по торговым точкам,
USD/тыс. шт. Минимальный элемент строки
I II III
72 75
60 58 III 40
42 47
70 68 IV V VI
А –68 –72 –75 –83 –75 –69 –83
В –56 –60 –58 –63 –61 –59 –63
С –35 –38 –40 –45 –25 –27 –45
D –40 –42 –47 –45 –53 –36 –53
Е –62 –70 –68 –67 –69 –70 –70
F 0 0 0 0 0 0 0
Минимальный (наибольший по абсолютной величине) элемент вычтем из всех элементов соответствующей строки, а затем определим в каждом столбце минимальный элемент (элементы последней 6–й строки в вычислениях не участвуют), получим таблицу.
15 11 8 0 8 14

 Минимальные элементы столбцов (выделены зеленым цветом)
7 3 5 0 2 4
10 7 5 0 20 18
13 11 6 8 0 17
8 0 2 3 1 0
0 0 0 0 0 0
7 0 2 0 0 0
Минимальный элемент вычтем из всех элементов соответствующего столбца, получим таблицу 1.
Таблица 1.
I II III IV V VI
А 8 11 6 0 8 14
В 0 3 3 0 2 4
С 3 7 3 0 20 18
D 6 11 4 8 0 17
Е 1 0 0 3 1 0
F 0 0 0 0 0 0

Дальнейший поиск оптимального решения осуществляется в соответствии с так называемым венгерским алгоритмом, алгоритм которого имеет два этапа.
Этап 1.
Если некоторое решение является допустимым, то каждой строке и каждому столбцу соответствует только один элемент. Если процесс распределения элементов осуществляется только в клетки с нулевой стоимостью, он приведет к получению минимального значения целевой функции.
1. Найти строку, содержащую только одно нулевое значение стоимости, и в клетку, соответствующую данному значению, поместить один элемент. Если такие строки отсутствуют, допустимо начать с любого нулевого значения стоимости.
2. Зачеркнуть оставшиеся нулевые значения данного столбца.
3. Пункты 1 и 2 повторять до тех пор, пока продолжение описанной процедуры окажется невозможным.
Если на данном этапе окажется, что есть несколько нулей, которым не соответствуют назначения и которые являются не зачеркнутыми, то необходимо:
4. Найти столбец, содержащий только одно нулевое значение, и в соответствующую клетку поместить один элемент.
5. Зачеркнуть оставшиеся нули в данной строке.
6. Повторять пункты 4 и 5 до тех пор, пока дальнейшая их реализация окажется невозможной.
Если окажется, что таблица содержит неучтенные нули, повторить операции 1-6. Если решение является допустимым, т.е. все элементы распределены в клетки, которым соответствует нулевая стоимость, то полученное решение одновременно является оптимальным. Если решение является недопустимым, осуществляется переход к этапу 2.

Этап 2.
1. Провести минимальное число прямых через строки и столбцы матрицы (но не по диагоналям) таким образом, чтобы они проходили через все нули, содержащиеся в таблице.
2. Найти наименьший среди элементов, через которые не проходит ни одна из проведенных прямых.
3. Вычесть его из всех элементов, через которые не проходят прямые.
4. Прибавить найденный элемент ко всем элементам таблицы, которые лежат на пересечении проведенных ранее прямых
5. Все элементы матрицы, через которые проходит только одна прямая, оставить без изменения.
В результате применения данной процедуры в таблице появляется, по крайней мере, один новый ноль. Необходимо возвратиться к этапу 1 и повторять алгоритм до тех пор, пока не будет получено оптимальное решение.
В результате работы алгоритма мы получим следующие таблицы 2, 3 и 4 назначений.
Таблица 2.
I II III IV V VI
А 8
11 6 0 8
14
В 0
3 3 0 2 4
С 3 7 3 0 20 18
D 6 11 4 8 0 17
Е 1
0 0 3 1 0
F 0 0 0 0 0 0
Таблица 3.
I II III IV V VI
А 11
11 6
0 11
11
В 0 0 0 0 2 1
С 3 7 0
0 20 15
D 6 8 1 5 0 14
Е 4
0
0
3 4 3
F 0 0 0 0 0 0

Таблица 4.
I II III IV V VI
А 12 11 7 0 12 10
В 0 0 0 0 2 0
С 3 6 0 0 20 14
D 6 7 1 4 0 13
Е 5 0 1 3 5 2
F 0 0 0 0 0 0

Прода–вец Объемы продаж по торговым точкам,
USD/тыс. шт.

I II III
72 75
60 58 III 40
42 47
70 68 IV V VI
А 68 72 75 83 75 69
В 56 60 58 63 61 59
С 35 38 40 45 25 27
D 40 42 47 45 53 36
Е 62 70 68 67 69 70

Максимальную прибыль от максимального объема продаж 83+56+40+53+70=302 торговая компания достигнет, если распределит продавцов по следующим торговым точкам: А в IV, B в I, C в III, D в V, E в II.


Скачиваний: 1
Просмотров: 2
Скачать реферат Заказать реферат