Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа №19
Решение задачи линейного программирования в MS Excel
(2 часа)
1. Цель и содержание: изучение методики решения задачи линейного программирования с использованием табличного процессора Excel 2010.
2. Теоретическое обоснование
2.1. Постановка задачи линейного программирования. Задача линейного программирования является достаточно распространенной задачей принятия оптимальных решений, особенно в экономике. Нахождение оптимума многомерных экономических функций сводится к поиску экстремумов функции. При этом нужно отличать глобальные и локальные экстремумы. Отсутствие наглядных графических представлений многомерных функций вынуждает применять численные методы нахождения оптимальных решений методами линейного программирования. С этой задаче успешно справляется пакет табличного процессора Excel 2010. Решение этой задачи рассмотрим на примере задачи распределения ресурсов.
Задача линейного программирования, которая является частным случаем задачи оптимизации, записывается следующим образом. Необходимо решить систему неравенств описывающих запасы ресурсов и экстремум функции выпуска продукции F:
(1)
где F – функция цели;
– количество выпускаемой продукции j-го типа;
– количество располагаемого ресурса i-го вида;
– норма расхода i-го ресурса для выпуска единицы продукции j-го типа;
– прибыль, получаемая от реализации единицы продукции j-го типа.
2.1.1. Задача распределения ресурсов. Частным случаем задачи линейного программирования является задача распределения ресурсов. Если финансы, оборудование, сырье и даже людей считать ресурсами, то значительное число задач в экономике можно рассматривать как задачи распределения ресурсов. Достаточно часто математической моделью таких задач является задача линейного программирования.
Рассмотрим следующий пример.
Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, финансовые, сырье. Количество ресурса каждого типа, необходимое для выпуска единицы продукции, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице 1. Там же приведено наличие располагаемого ресурса.
Таблица 1
|
Ресурс |
Прод1 |
Прод2 |
Прод3 |
Прод4 |
Ограничения |
|
|
Прибыль |
60 |
70 |
120 |
130 |
= |
max |
|
Трудовые |
1 |
1 |
1 |
1 |
<= |
16 |
|
Сырье |
6 |
5 |
4 |
3 |
<= |
110 |
|
Финансы |
4 |
6 |
10 |
13 |
<= |
100 |
Как видно из таблицы 1, для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6x1 единиц сырья, где x1 – количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:
(2)
В этом ограничении левая часть равна величине требующегося ресурса, а правая показывает количество имеющегося ресурса.
(3)
Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид: (3).
Аналитическое решение задачи линейного программирования осуществляется с помощью симплекс-метода. В Excel имеется математический аппарат, реализующий основные идеи данного метода. Решение задачи с помощью Excel будем рассматривать на примере задачи, математическая модель которой имеет вид (3).
3. Методика и порядок проведения работы
3.1. Задание 1. Решить задачу распределения ресурсов, исходные данных которой приведены в таблице 1.
3.1.1. Рекомендации по выполнению:
|
A |
B |
C |
D |
E |
F |
G |
H |
|
|
1 |
Переменные |
|||||||
|
2 |
Ресурс |
Прод1 |
Прод2 |
Прод3 |
Прод4 |
|||
|
3 |
Значение |
1 |
1 |
1 |
1 |
|||
|
4 |
Нижняя граница |
10 |
0 |
6 |
0 |
|||
|
5 |
Целевая функция |
|||||||
|
6 |
Коэффициенты целевой функции |
60 |
70 |
120 |
130 |
=СУММПРОИЗВ (B$3:E$3;B6:E6) |
max |
|
|
7 |
Ограничения |
|||||||
|
8 |
левая часть |
операция |
правая часть |
|||||
|
9 |
трудовые |
1 |
1 |
1 |
1 |
=СУММПРОИЗВ (B$3:E$3;B10:E10) |
<= |
16 |
|
10 |
сырье |
6 |
5 |
4 |
3 |
=СУММПРОИЗВ (B$3:E$3;B11:E11) |
<= |
110 |
|
11 |
финансы |
4 |
6 |
10 |
13 |
=СУММПРОИЗВ (B$3:E$3;B12:E12) |
<= |
100 |
Рисунок 1. Выпуск продукции
Рисунок 2. Диалоговое окно для ввода элементов массивов
Рисунок 3. Диалоговое окно Поиск решения
Изменяя ячейки: $B$3:$E$3.
Нажмите кнопку Добавить и в диалоговом окне Добавление ограничения введите Ограничения (рис. 4):
$B$3>=$B$4, $C$3>=$C$4, $D$3>=$D$4, $E$3>=$E$4, $F$10<=$H$10, $F$11<=$H$11, $F$12<=$H$12.
Рисунок 4. В диалоговом окне вводятся ограничения
3. Результаты решения задачи отражены в таблице 2.
Таблица 2. ОПТИМАЛЬНОЕ РЕШЕНИЕ ЗАДАЧИ
|
A |
B |
C |
D |
E |
F |
G |
H |
|
|
1 |
Переменные |
|||||||
|
2 |
Ресурс |
Прод1 |
Прод2 |
Прод3 |
Прод4 |
|||
|
3 |
Значение |
10 |
0 |
6 |
0 |
|||
|
4 |
Нижняя граница |
10 |
0 |
6 |
0 |
|||
|
5 |
Целевая функция |
|||||||
|
6 |
Коэффициенты |
60 |
70 |
120 |
130 |
1320 |
max |
|
|
7 |
Ограничения |
|||||||
|
8 |
левая часть |
операция |
правая часть |
|||||
|
9 |
трудовые |
1 |
1 |
1 |
1 |
16 |
<= |
16 |
|
10 |
сырье |
6 |
5 |
4 |
3 |
84 |
<= |
110 |
|
11 |
финансы |
4 |
6 |
10 |
13 |
100 |
<= |
100 |
По таблице 2 видно, что в оптимальном решении: Прод1 = 10, Прод2 = 0, Прод3 = 6, Прод4 = 0.
При этом максимальная прибыль будет составлять 1320, а количество использованных ресурсов равно: трудовых = 16, сырья = 84, финансов = 100. Таково оптимальное решение задачи распределения ресурсов.
3.2. Задание 2. Представить результат оптимизации в графическом виде.
3.2.1. Рекомендации по выполнению:
Постройте диаграмму Оптимальный план по строкам Ресурс и Значение.
Рисунок 5. Диаграмма оптимального плана
4 Аппаратура и материалы: IBM PC, табличный процессор MS Excel.
5. Содержание отчета и его форма
6. Контрольные вопросы: