Тема: Решение задач линейного программирования
Средствами ЭТ Excel
Цель:
Научиться решать задачи линейного программирования средствами ЭТ Excel
ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Функциональные возможности пакета Excel позволяют широко использовать его возможности для финансово-экономической обработки данных.
В комплекте Excel содержатся инструменты для решения важных задач из экономической жизнедеятельности предприятия. С помощью дополнительной программы Поиск решения можно легко решать многие задачи оптимизации, например задачи линейного программирования.
Чтобы дать программе «понять», что от нее требуется выполнить и какой результат получить, необходимо предварительно поставить задачу и задать исходные числовые данные. Основой для постановки задачи служит созданная пользователем таблица, в которой собран весь необходимый числовой материал. При этом таблица должна содержать формулы, отражающие зависимости между определенными данными таблицы.
После создания таблицы активизируется программа Поиск решения, которая позволяет по заданному значению результата находить значения переменных, удовлетворяющих некоторым заданным ограничениям. При этом полученные оптимальные решения можно автоматически занести в таблицу и проиллюстрировать графиком.
ПРИМЕР ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ
ПОСТАНОВКА ЗАДАЧИ
Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, чтобы прибыль от производства была максимальной. Для изготовления требуются ресурсы трех видов: трудовые, сырье, финансы. Нормы расхода, а так же прибыль, получаемая от реализации единицы каждого типа продукции, приведены на рисунке 1.1.
| Ресурс | Прод1 | Прод2 | Прод3 | Прод4 | Знак | Наличие | |
| Прибыль | Max | — | |||||
| Трудовые | £ | ||||||
| Сырье | £ | ||||||
| Финансы | £ |
Рисунок 1.1- Исходные данные к задаче
Математическая модель задачи имеет вид:
Целевая функция
F = 60 x1 + 70 x2 + 120 x3 + 130 x4 -> max
Система ограничений
x1 + x2 + x3 + x4 £ 16
6 x1 + 5 x2 + 4 x3 + 3 x4 £ 110
4 x1 + 6 x2 + 10 x3 + 13 x4 £ 100
Граничные условия : x1 ³ 0, x2 ³ 0, x3 ³ 0, x4 ³ 0
х1, х2, х3, х4 – количество продукции каждого вида
Ввод условий задачи
Ввод условий задачи состоит из следующих основных шагов:
1. Создание формы для ввода условий задачи.
2. Ввод исходных данных.
3. Ввод зависимостей из математической модели.
4. Назначение целевой функции.
5. Ввод ограничений и граничных условий.
Алгоритм 1.1. Ввод данных для решения задачи
линейного программирования
Примечание ¾ В алгоритмах используются условные обозначения:
М1 – щелкнуть левой кнопкой мышки 1 раз
М2 – щелкнуть левой кнопкой мышки 2 раза
МН – нажать левую кнопку мышки и протянуть
МП – щелкнуть правой кнопкой мышки 1 раз
1. Сделать форму для ввода условий задачи (рисунок 1.2)
Весь текст на рисунке 1.2 и в дальнейшем является комментарием и на решение задачи не влияет.
2. Ввести исходные данные в форму (рисунок 1.2)
Рисунок 1.2
3. Ввести зависимости из математической модели.
Для наглядности (но не обязательно!) можно перейти к режиму представления формул. При этом ввод данных приводится на рисунке 1.3 , а режим представления формул - на рисунке 1.4.
3.1. Ввести зависимость для целевой функции:
¨ Курсор в F6.
¨ Курсор на кнопку Мастер функций.
¨ М1.
На экране диалоговое окно Мастер функций шаг 1 из 2.(рисунок 1.5)
Рисунок 1.3
Рисунок 1.4
¨ Курсор в окно Категория на категорию Математические
¨ М1.
¨ Курсор в окно Имя функции на СУММПРОИЗВ.
¨ М1.
¨ ОК.
На экране: диалоговое окно (рисунок 1.6)
¨ В массив 1 ввести B$3:E$3.
Заметим, что во все диалоговые окна адреса ячеек удобно вводить не с клавиатуры а, протаскивая мышь по ячейкам, чьи адреса следует ввести.
¨ В массив 2 ввести В6:Е6.
¨ ОК.
На экране: рисунок 1.3, рисунок 1.4 (в F6 введены значения целевой функции).
3.2. Ввести зависимости для левых частей ограничений:
¨ Курсор в F6.
¨ Копировать в буфер.
¨ Курсор в F9.
¨ Вставить из буфера.
На экране: в F9 введена функция, как это показано на рисунке 1.4.
¨ Скопировать F9 в F10:F11.
На этом ввод данных в таблицы закончен.
 |
Рисунок 1.5
Рисунок 1.6
Алгоритм 1.2. Работа в диалоговом окне Поиск решения
1.Сервис, Поиск решения...
На экране: диалоговое окно Поиск решения (рисунок 1.7)
2. Назначить целевую функцию:
¨ Курсор в окно Установить целевую ячейку.
¨ Ввести адрес: F6.
¨ Ввести направление целевой функции: Максимальному значению.
3. Ввести адреса искомых переменных:
¨ Курсор в поле Изменяя ячейки.
¨ Ввести адреса: В3: Е3
4. Добавить...
На экране: диалоговое окно Добавление ограничения (рисунок 1.8)
5. Ввести граничные условия на переменные (Прод1- Прод4)³ 0
B3 ³ B4 , C3 ³ C4 , D3 ³ D4 , E3 ³ E4.
¨ В окне Ссылка на ячейку ввести B3.
¨ Курсор на стрелку.
¨ М1.
На экране: знаки для ввода в ограничения.
¨ Курсор на знак >=.
Рисунок 1.7
¨ M1.
¨ Курсор в правое окно.
¨ Ввести В4.
¨ Добавить...
На экране опять диалоговое окно Добавление ограничения (рисунок 1.8 )
Рисунок 1.8
Аналогично ввести граничные условия для остальных переменных.
6. Аналогично ввести ограничения:
F9 £ H9, F10 £ H10, F11 £ H11.
¨ После ввода последнего ограничения вместоДобавить... ввести ОК.
На экране: диалоговое окно Поиск решения с введенными условиями.
Если при вводе задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делается с помощью команд Изменить..., Удалить.
На этом ввод условий задачи заканчивается.
2.3 РЕШЕНИЕ ЗАДАЧИ
Решение задачи производится сразу же после ввода данных по алгоритму 1.2, когда на экране находится диалоговое окно Параметры поиска решения (рисунок 1.9)
Алгоритм 1.3. Решение задачи линейного программирования
1. Параметры...
На экране диалоговое окно Параметры поиска решения (рисунок 1.9).
С помощью команд, находящихся в этом диалоговом окне, можно вводить условия для решения задач оптимизации всех классов.
Максимальное время
Служит для назначения времени в секундах, выделяемого на поиск решения зачади. В поле можно ввести время £ 32767. Значение 100, используемое по умолчанию, подходит для решения большинства задач.
 |
Рисунок 1.9
Предельное число итераций
Служит для назначения числа итераций. Используемое по умолчанию значение 100 подходит для решения большинства задач.
После этих пояснений продолжим решение задачи.
2. Установить флажок Линейная модель, что обеспечивает применение Симплекс - метода.
3. ОК.
На экране: диалоговое окно Поиск решения (рисунок 1.7)
4. Выполнить.
На экране: диалоговое окно Результаты поиска решения. Решение найдено (рисунок 1.10) и результат оптимального решения задачи приведен в таблице (рисунок 1.11)
5. ОК
Рисунок 1.10
Рисунок 1.11
На рисунке 1.11 видно, что в оптимальном решении
Прод1 = В3 = 10
Прод2 = С3 = 0
Прод3 = D3 = 6
Прод4 = Е3 = 0
При этом максимальная прибыль будет составлять F6 = 1320, а количество использованных ресурсов равно
трудовых = F9 = 16
сырья = F10 = 84
финансов = F11 = 100
Для более наглядного представления полученного результата постройте гистограмму. Исходными значениями являются результаты решения задачи оптимизации ( рисунок 1.12 )
Рисунок 1.12
Встроенная диаграмма, созданная по этим данным приведена на рисунке 1.13, отформатированная диаграмма приведена на рисунке 1.14
Рисунок 1.13
Рисунок 1.14
ЗАДАНИЕ
- Решить задачу линейного программирования, рассмотренную в лабораторной работе
- Решить задачу линейного программирования. Решение задачи представить графически.
 |
Целевая функция
Система ограничений
Граничные условия
xi³0 , i=1,2,3,4,5
ТРЕБОВАНИЯ К ОТЧЕТУ ПО ЛАБОРАТОРНОЙ РАБОТЕ
Отчет должен содержать:
1. Краткий конспект последовательности решения задач линейного программирования
2. Условие задач.
3. Результаты решения задач.
Лабораторная работа N 2
Тема: Решение задач распределения ресурсов
средствами ЭТ Excel
Цель:
1. Ознакомиться с математической постановкой задачи распределения ресурсов
2. Освоить порядок решения задачи распределения ресурсов средствами Excel
3. Освоить порядок решения задач целочисленного программирования средствами Excel
4. Научиться оценивать полученные результаты
Теоретические сведения
Постановка задачи распределения ресурсов:
Имеется М видов ресурсов (i=1,2,3…M), из которых производят N (j=1,2,3…N) видов продукции. Известны нормы расхода i – го ресурса на j-е изделие – a(i,j), запас ресурса – b(i), затраты денежных средств на производство изделия s(j), отпускная цена изделия – с(j). Требуется составить такой план выпуска изделий, который даст максимум критерия эффективности.
Таблица 2.1 – Исходные данные к задаче
| Ресурс Изделие | … | М | Цена cj | Затраты sj | План выпуска | ||
| a11 | a21 | …. | am1 | c1 | s1 | x1 | |
| a21 | a22 | …. | am2 | c2 | s2 | x2 | |
| …. | …. | ….. | …. | …. | ….. | ….. | ….. |
| N | a1n | a2n | ….. | amn | cn | sn | xn |
| Запас ресурса b(i) | b1 | b2 | …. | bm |
Математическая модель:
Критерий эффективности – максимум прибыли, ограничения по запасам ресурса, граничные условия – неотрицательность управляемых переменных.
Целевая функция
(2.1)
Система ограничений
(2.2)
Граничные условия
xj³0, j=1,2,3… n
ПРИМЕР выполнения лабораторной работы
2.1 постановка задачи
Изделия четырех типов проходят последовательную обработку на двух станках. Время обработки одного изделия каждого типа на каждом из станков приведено в таблице
Таблица 2.2
| Станок | Время обработки изделий, ч | |||
| Тип 1 | Тип 2 | Тип 3 | Тип 4 | |
Стоимость машино-часа составляет 10$ для станка 1 и 8$ для станка 2. Допустимое время использования станков для обработки изделий всех типов ограничено следующими значениями: 500 машино-часов – для станка 1 и 380 машино-часов для станка 2. Цены изделий типов 1, 2, 3 и 4 равны 65, 70, 55 и 45$ соответственно. Сформулируйте для приведенных условий задачу максимизации чистой прибыли и решите ее.
Таблица 2.3
| Ресурс Изделие | Станок1 | Станок 2 | Цена cj | Затраты sj | План выпуска |
| 10*2+8*3=44 | x1 | ||||
| 10*3+8*2=46 | x2 | ||||
| 10*4+8*1=48 | x3 | ||||
| 10*2+8*2=36 | x4 | ||||
| Запас ресурса b(i) |
Математическая модель:
Целевая функция
Система ограничений
Граничные условия
xj³0, j=1,2,3,4
Предприятие выпускает «неделимую» продукцию, поэтому необходимо ввести дополнительные ограничения:
xj®целое , j=1,2,3,4
Решение задачи
Решение задач распределения ресурсов проводится по алгоритмам 1.1, 1.2, 1.3 из лабораторной работы №1 «Решение задач линейного программирования средствами ЭТ Excel». Задачи оптимизации, в результате решения которых искомые переменные должны быть целыми числами, называются задачами целочисленного программирования. Задачи целочисленного программирования решаются аналогично задачам линейного программирования. Основное отличие заключается в требовании целочисленности.
Алгоритм 2.1. Решение задач целочисленного программирования
1. Сделать форму для ввода условий задачи и ввести исходные данные
2.Сервис, Поиск решения...
На экране: диалоговое окно Поиск решения (рисунок 1.7)
3. Ввести:
· Условия, которые были введены для задачи линейного программирования
· Требования целочисленности
¨ Добавить
На экране: диалоговое окно Добавление ограничений
¨ Курсор в окно Ссылка на ячейку
¨ Ввести адрес ячейки В3
¨ Курсор на стрелку
¨ Ввести целое
¨ Повторить ввод требований целочисленности для всех целочисленных переменных
¨ После окончания ввода требований целочисленности вместо Добавить нажать кнопку ОК.
4. Параметры
На экране: диалоговое окно Параметры поиска решения
5. Установить флажок Линейная модель, что обеспечивает применение симплекс – метода.
6. ОК
На экране: диалоговое окно Поиск решения
7. Выполнить
На экране: диалоговое окно Результаты поиска решения
8. ОК
На экране результат решения.
На рисунке 2.1 представлена форма для решения задачи с введенными в нее исходными данными. Результаты поиска решения приведены на рисунке 2.2.
Ответ:
x1= 28 ед.
x2= 148 ед.
x3= 0 ед.
x4= 0 ед.
Целевая функция:
W= 4140 $
Вывод: Для получения наибольшей прибыли, равной 4140 $, предприятию необходимо выпустить изделий типа 1- 28 шт., изделий типа 2 – 148 шт.
Рисунок 2.1
Рисунок 2.2
Задание
- Решить задачу распределения ресурсов
Завод выпускает два вида деталей (А и Б), обработка которых осуществляется на токарных и фрезерных станках. На месяц заводу выделено N тонн металла. Его расход на изготовление детали А - a1 тонн, Б - a2 тонн. На изготовление детали А требуется t11 ч работы токарного и t21 ч работы фрезерного станков, а детали Б t12 и t22 ч соответственно. Всего на заводе r1 токарных станков и r2 фрезерных станка, работающих в две смены (т.е. месячный календарный фонд рабочего времени каждого станка составляет 300 ч). При реализации единицы каждого вида деталей прибыль составляет с1 и с2 соответственно. Необходимо составить план выпуска продукции, который бы обеспечивал получение максимальной прибыли при реализации всей выпущенной продукции.
Варианты заданий приведены в таблице 2.4.
- Составить и решить задачу распределения ресурсов (количество изделий – не менее 3, количество видов используемых ресурсов не менее 4).
Таблица 2.4 – Исходные данные к заданию по лабораторной работе
| Вариант | N | a1 | a2 | t11 | t21 | t12 | t22 | r1 | r2 | c1 | c2 |
| 0.10 | 0.13 | 3.7 | 3.8 | 6.0 | 8.0 | ||||||
| 0.10 | 0.13 | 6.0 | 2.0 | 6.0 | 8.0 | ||||||
| 0.12 | 0.13 | 3.7 | 3.8 | 3.5 | 4.2 | ||||||
| 0.10 | 0.13 | 3.7 | 3.8 | 3.5 | 4.2 | ||||||
| 0.24 | 0.11 | 6.0 | 2.0 | 5.5 | 12.0 | ||||||
| 0.18 | 0.13 | 6.0 | 2.0 | 6.0 | 8.0 | ||||||
| 0.10 | 0.13 | 3.6 | 3.8 | 6.0 | 8.0 | ||||||
| 5.9 | 2.0 | 6.0 | 8.0 | ||||||||
| 0.12 | 0.13 | 3.8 | 3.8 | 3.5 | 4.2 | ||||||
| 0.10 | 0.13 | 3.7 | 3.8 | 3.5 | 4.2 | ||||||
| 0.24 | 0.11 | 6.0 | 2.0 | 5.5 | 4.2 | ||||||
| 0.18 | 0.13 | 6.1 | 2.0 | 6.0 | 8.0 | ||||||
| 0.10 | 0.13 | 3.7 | 3.8 | 6.1 | 8.0 | ||||||
| 0.10 | 0.13 | 6.0 | 2.0 | 6.5 | 8.0 | ||||||
| 0.12 | 0.13 | 3.8 | 3.8 | 3.5 | 4.2 | ||||||
| 0.10 | 0.13 | 3.7 | 3.8 | 3.5 | 4.2 | ||||||
| 0.24 | 0.11 | 3.6 | 2.0 | 5.5 | 12.0 | ||||||
| 0.18 | 0.13 | 3.5 | 2.0 | 6.3 | 8.0 | ||||||
| 0.24 | 0.11 | 6.0 | 2.0 | 5.5 | 12.0 | ||||||
| 0.18 | 0.13 | 6.1 | 2.0 | 6.5 | 8.0 |
ТРЕБОВАНИЯ К ОТЧЕТУ ПО ЛАБОРАТОРНОЙ РАБОТЕ
Отчет должен содержать:
1. Словесное описание условия задачи
2. Таблицу исходных данных
3. Математическую модель
4. Результаты решения задачи
5. Выводы по решению задач
Лабораторная работа N 3