Методика и порядок проведения работы. Решение задачи линейного программирования в MS Excel
Лаб. Раб. №14
Решение задачи линейного программирования в MS Excel
1. Цель и содержание:изучение методики решения задачи линейного программирования с использованием табличного процессора Excel.
Теоретическое обоснование
2.1. Постановка задачи линейного программирования. Задача линейного программирования является достаточно распространенной задачей принятия оптимальных решений, особенно в экономике. Решение этой задачи рассмотрим на примере задачи распределения ресурсов.
Задача линейного программирования, которая является частным случаем задачи оптимизации, записывается следующим образом:
(1)
где F – функция цели;
– количество выпускаемой продукции j-го типа;
– количество располагаемого ресурса i-говида;
– норма расхода i-го ресурса для выпуска единицы продукции j-го типа;
– прибыль, получаемая от реализации единицы продукции j-го типа.
2.1.1. Задача распределения ресурсов. Частным случаем задачи линейного программирования является задача распределения ресурсов. Если финансы, оборудование, сырье и даже людей считать ресурсами, то значительное число задач в экономике можно рассматривать как задачи распределения ресурсов. Достаточно часто математической моделью таких задач является задача линейного программирования.
Рассмотрим следующий пример.
Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, финансовые, сырье. Количество ресурса каждого типа, необходимое для выпуска единицы продукции, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице 1. Там же приведено наличие располагаемого ресурса.
Таблица 1
| Ресурс | Прод1 | Прод2 | Прод3 | Прод4 | Ограничения | |
| Прибыль | = | max | ||||
| Трудовые | <= | |||||
| Сырье | <= | |||||
| Финансы | <= |
Как видно из таблицы 1, для выпуска единицы Прод1 требуется
6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6x1 единиц сырья, где x1 – количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:
(2)
В этом ограничении левая часть равна величине требующегося ресурса, а правая показывает количество имеющегося ресурса.
(3)
Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид: (3).
Аналитическое решение задачи линейного программирования осуществляется с помощью симплекс-метода. В Excel имеется математический аппарат, реализующий основные идеи данного метода. Решение задачи с помощью Excel будем рассматривать на примере задачи, математическая модель которой имеет вид (3).
Методика и порядок проведения работы
3.1. Задание 1. Решить задачу распределения ресурсов, исходные данных которой приведены в таблице 1.
3.1.1. Рекомендации по выполнению:
1. Введите данные в таблицу (рис.1).
2. 2. Введите зависимость для целевой функции (рис.2).
- В ячейку F6 введите формулу =СУММПРОИЗВ(B$3:E$3;B6:E6).
| A | B | C | D | E | F | G | H | |
| Переменные | ||||||||
| Ресурс | Прод1 | Прод2 | Прод3 | Прод4 | ||||
| Значение | ||||||||
| Нижняя граница | ||||||||
| Целевая функция | ||||||||
| Коэффициенты целевой функции | =СУММПРОИЗВ (B$3:E$3;B6:E6) | max | ||||||
| Ограничения | ||||||||
| левая часть | операция | правая часть | ||||||
| трудовые | =СУММПРОИЗВ (B$3:E$3;B10:E10) | <= | ||||||
| сырье | =СУММПРОИЗВ (B$3:E$3;B11:E11) | <= | ||||||
| финансы | =СУММПРОИЗВ (B$3:E$3;B12:E12) | <= |
Рисунок 1. Выпуск продукции
Рисунок 2. Диалоговое окно для ввода элементов массивов
- в Массив1 введите B$3:E$3. Нажмите знак 
, справа от поля ввода данных выделите мышью нужный диапазон ячеек и нажмите клавишуEnter. Для того чтобы сменить ссылку на ячейку с относительной B3 на абсолютную B$3, нажмите клавишу F4 до появления нужного результата.
- в Массив2 введите B6:E6.
- введите зависимости для левых частей ограничений. Для этого, скопируйте формулу из ячейки F6 в диапазон F10:F12.
- осуществите поиск решения. Выполните команду СЕРВИС>Поиск решения(рис. 3).
-
Рисунок 3. Диалоговое окно Поиск решения
- В диалоговом окне Поиск решения установите: Установить целевую ячейку: $F$6; Равной: максимальному значению;
Изменяя ячейки: $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 | Прод3 | Прод4 | ||||
| Значение | ||||||||
| Нижняя граница | ||||||||
| Целевая функция | ||||||||
| Коэффициенты целевой функции | max | |||||||
| Ограничения | ||||||||
| левая часть | операция | правая часть | ||||||
| трудовые | <= | |||||||
| сырье | <= | |||||||
| финансы | <= |
По таблице 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. Содержание отчета и его форма
1. Форма отчёта письменная.
2. Тема, цель лабораторной работы.
3. Краткое теоретичеcкое описание работы.
4. Описание выполнения работы.
5. Продемонстрировать электронный вариант таблиц .
6. Контрольные вопросы:
1. Каким методом решаются задачи линейного программирования?
2. Постановка задачи распределения ресурсов.
3. Опишите этапы решения задачи распределения ресурсов.
4. Назначения целевой функции.
5. Как определить ограничения целевой функции?
6. С помощью какого инструмента осуществляется поиск решения?
7. Опишите процесс решения задачи с помощью Поиска решения.
8. Задание экстремума функции.
9. Параметры Поиска решения.
10. Как произвести ввод и редактирование ограничений функции?
11. Опишите процесс анализа результатов решения задачи графическим методом.