Цель: научиться решать задачи линейного программирования в Excel с помощью надстройки «Поиск решения».
Краткие теоретические сведения
Оптимизационные задачи находят широкое применение в различных областях практической деятельности: при организации работы транспортных систем, в управлении промышленными предприятиями, при составлении проектов сложных систем. Многие распространенные классы задач системного анализа, в частности, задачи оптимального планирования, распределения различных ресурсов, управления запасами, календарного планирования, межотраслевого баланса укладываются в рамки моделей линейного программирования.
Постановка задачи линейного программирования (ЗЛП).
Имеется множество переменных X= (x 1 , х 2 ,..., х n). Целевая функция линейно зависит от управляемых параметров:
Имеются ограничения, которые представляют собой линейные формы
где 
(2)
Требуется определить максимум (минимум) линейной функции
при условии, что точка (х 1 , х 2 ,..., х n) принадлежит некоторому множеству D, которое определяется системой линейных неравенств
(4)
Любое множество значений (х 1 *, х 2 *,..., х n *), которое удовлетворяет системе неравенств (4) задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство
c 1 х 1 o + c 2 х 2 o +..+ c n х n o ≥ c 1 х 1 + c 2 х 2 +..+ c n х n
для всего множества значений x 1 , х 2 ,..., х n , то значение х 1 o ..х n o является оптимальным решением задачи линейного программирования.
Пример построения математической модели и решения ЗЛП.
Задача. Требуется определить, в каком количестве надо выпускать продукцию четырех типов A, B, C иD, для изготовления которой требуются ресурсы трех видов: трудовые, сырье и финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице1. Там же приведено наличие располагаемого ресурса.
Таблица1.
|
Ресурс |
A |
B |
C |
D |
знак |
наличие |
|
трудовые |
||||||
Составим математическую модель, для чего введем следующие обозначения:
x i - количество выпускаемой продукции i-го типа, i = 1,2,3,4
b j – количество располагаемого ресурса j-го вида, j = 1,2,3
a ji – норма расхода j-го ресурса для выпуска i-ой продукции
c i – прибыль от реализации единицы продукции i-го типа.
Как видно из таблицы 1, для выпуска единицы продукции A требуется 6 единиц сырья, значит, для выпуска всей продукции A требуется 6x 1 единиц сырья, где x 1 - количество выпускаемой продукции A . С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:
6x 1 + 5x 2 + 4x 3 + 3x 4 ≤ 110
В этом ограничении левая часть равна величине требуемого ресурса, а правая часть показывает количество имеющегося ресурса.
Аналогично можно составить ограничения для других видов ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:
x 1 + x 2 + x 3 + x 4 ≤ 16
6x 1 + 5x 2 + 4x 3 + 3x 4 ≤ 110
4x 1 + 6x 2 + 10x 3 + 13x 4 ≤ 100
x i ≥ 0, i=1,2,3,4
1. Для ввода условий задачи создадим форму в Excel (рис.1). В ячейках B3:E3 будут отображаться вычисленные значения x i .
рис.1. Форма для ввода условий задачи
2. Введем коэффициенты целевой функции и ограничений в форму. Из математической модели введем зависимости. Введенные данные отображены на рис.2.
рис.2. Исходные данные задачи
В ячейке F6 записана формула целевой функции, в F9-F11- левые части ограничений из математической модели. На рис. 3 отображен режим представления формул. Перейти к данному режиму можно с помощью последовательности действий: нажмите кнопку Microsoft Office , щелкните Параметры Excel, откройте вкладку Дополнительно и установите флажок Показывать формулы, а не их значения.
рис.3. Режим представления формул.
3. Загрузим надстройку поиск решения Данные │Анализ │Поиск решения .
4. В поле Установить целевую ячейку введем ссылку на целевую ячейку, для чего установим курсор в поле и щелкнем левой кнопкой мыши по ячейке F6.
5. Выберем направление поиска, установив флажок равной максимальному значению.
6. Установим курсор в поле Изменяя ячейки и введем с помощью мыши имена изменяемых ячеек B3:E3. В этих ячейках в результате поиска решения будет выведено решение – значения переменных x i ., при которых целевая функция имеет максимальное значение при заданных ограничениях.
7. Введем
ограничения на искомые переменные: x i ≥
0 (нижняя
граница по умолчанию равна 0, количество выпускаемой продукции не может быть
отрицательным). Так же введем ограничения на ресурсы 
(н е может быть использовано больше ресурсов, чем их запасы). Щелкнем
по кнопке Добавить
, в появившемся окне Добавление ограничения
в левом поле с
помощью мыши введем ссылку на ячейку B3, из
раскрывающегося списка выберем знак ≥,
в
правом поле щелкнем мышью по ячейкеB4 (рис.4). Аналогично
введем остальные ограничения.
Рис.4. Окно добавления ограничений.
На рисунке 5 показано заполненное окно Поиск решения.
Рис.5 Заполненное окно Поиск решения
8. Далее нажимаем на кнопку Выполнить. Появляется диалоговое окно Результаты поиска решения (рис.6). Решение найдено. Все ограничения и условия оптимальности выполнены. Сохраняем найденное решение. В этом окне также можно получить три вида отчетов: по результатам, устойчивости и пределам, отчеты формируются в новых рабочих листах.
рис.6. Окно Результаты поиска решения
Результаты оптимального решения задачи приведены в таблице (рис.7).
рис.7. Результаты оптимального решения
Таким образом, получилось оптимальное решение (10;0;6;0), т.е. целесообразно выпускать 10 единиц продукции А и 6 единиц продукции С. Максимальная прибыль равна 1320 денежным единицам, при этом используются все трудовые и финансовые ресурсы, 84 единиц сырья, в запасе остается 26 единиц сырья.
Задания для лабораторной работы.
Составить математическую модель и решить полученную задачу линейного программирования в Excel с помощью надстройки Поиск решения.
Для перевозки грузов используются машины типов А и Б. Грузоподъемность машин обоих типов одинаковая и равна h т. За одну ходку машина А расходует а 11 кг смазочных материалов и а 12 л горючего, машина Б - а 21 кг смазочных материалов иа 22 л горючего. На базе имеется d 1 кг смазочных материалов и d 2 л горючего. Прибыль от перевозки одной машины А составляет с 1 руб., машины Б - с 2 руб. Необходимо перевезти H т груза (исходные данные приведены в нижеследующей таблице).
Сколько надо использовать машин обоих типов, чтобы доход от перевозки груза был максимальным.
|
№ варианта |
||||||||||
Инструкция по выполнению лабораторной работы.
- Изучить теоретический материал.
- Выполнить приведенный пример.
- Выбрать свой вариант по последней цифре.
- Составить математическую модель задачи.
- Найти оптимальное решение с помощью Поиска решения.
- Сделать выводы по полученным решениям, сформировать отчеты по результатам решения, устойчивости и пределам.
- Создать отчет по лабораторной работе.
- Титульный лист.
- Словесная постановка задачи.
- Математическая формулировка задачи.
- Заполненное окно Поиск решения
- Результаты поиска решения (таблица).
- Выводы по полученным решениям.
Список источников
- Гельман В.Я. Решение математических задач средствами Excel: Практикум. – СПб.:Питер, 2003
- Курицкий Б.Я. Поиск оптимальных решений средствами Excel. – СПб.: BHV-Санкт-Петербург, 1997
- Пазюк К.Т. Математические методы и модели в экономике. – Хабаровск: Издательство ХГТУ, 2002
- Джон Уокенбах. MS OfficeExcel 2007 - Библия пользователя, Издатель: Вильямс, 2008
Лабораторная работа "Использование средства Поиск решения"
Задание:
Решить в Excel все приведенные ниже задачи (каждую на отдельном листе) и сохранить решения в файле LAB4.xls на своем пользовательском диске.
Задача 1 1
Решение задачи линейного программирования с помощью EXCEL. 2
Задача 2 4
Задача планирования производства красок 4
Задача 3 5
Решение транспортной задачи с помощью средства Поиск решения 5
Задача 1
Задача распределения ресурсов.
Если финансы, оборудование, сырье и даже людей полагать ресурсами, то значительное число задач в экономике можно рассматривать как задачи распределения ресурсов. Достаточно часто математической моделью таких задач является задача линейного программирования.
Например:
Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, Прод3, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведена ниже.Составим математическую модель, для чего введем следущие обозначения:
x j - количество выпускаемой продукции j-го типа, j=1,4 ;
b i - количество располагаемого ресурса i-го вида, i=1,3 ;
a ij - норма расхода i-го ресурса для выпуска единицы продукции j-го типа;
c j - прибыль, получаемая от реализации единицы продукции j-го типа.
Теперь приступим к составлению модели.
Для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6 х 1 единиц сырья, где х 1 - количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:
6х 1 +5х 2 +4х 3
В этом ограничении левая часть равна величине потребного ресурса, а правая показывает количество имеющегося ресурса. Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:
F=60x 1 +70x 2 +120x 3 +130x 4 --> max
x 1 +x 2 +x 3 +x 4
6x 1 +5x 2 +4x 3 +3x 4
4x 1 +6x 2 +10x 3 +13x 4
x j >=0; j=1,4
Решение задачи линейного программирования с помощью EXCEL.
1
.
Сделать активной ячейку F6.
2. Мастер функций Математические СУММПРОИЗВ на жмите кнопку Далее. На экране диалоговое окно
3. Введите зависимости для левых частей ограничений.
Работа в диалоговом окне Поиск решения.
1
.
Сервис, Поиск решения...
2 . Курсор в поле Установить целевую ячейку и введите адрес F6.
3 . Введите направление целевой функции: Максимальному значению .
4 . Курсор в поле Изменяя ячейки и введите адреса B3:E3
5. Нажмите кнопку Добавить... и в ведите граничные условия на переменные
6. После ввода ограничений, нажмите кнопку Выполнить . В результате вычислений в ячейках В3:Е3, будут отражены найденные числовые значения х i , а в ячейке F6 – значение целевой функции.
Т.О, видно, что в оптимальном решении Прод1=В3=10, Прод2=С3=0, Прод3=D3=6, Прод4=Е3=0.
При этом максимальная прибыль будет составлять F6=1320 , количество использованных ресурсов равно трудовых=F9=16, сырья=F10=84, финансов=F11=100.
С помощью диалогового окна Результат поиска решения. Решение найдено можно получить отчеты трех типов: результаты, устойчивость, пределы.
Задача 2
Задача планирования производства красок
Для производства красок для наружных и внутренних работ используют два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно.
Суточный спрос на краску для внутренних работ никогда не превышает спроса на краску для наружных работ более чем на 1т.
Спрос на краску для внутренних работ не превышает 2т. в сутки.
Оптовые цены одной тонны красок равны: 3000 руб. для краски для наружных работ и 2000 руб. для краски для внутренних работ .
Какое количество краски каждого вида следует производить, чтобы доход от реализации был максимальным?
Расходы продуктов А и В на 1т. приведены в таблице:
|
исходный продукт |
расход исходных продуктов на тонну краски |
максимально возможный запас |
|
|
для внутренних работ |
для наружных работ |
||
х 1 - суточный объем производства краски для внутренних работ
х 2 - суточный объем производства краски для наружных работ
f -суммарная суточная прибыль от производства обоих видов красок (целевая функция)
f = 3000х 1 +2000х 2
Определить при каких допустимых значениях х 1 и х 2 значение f - максимальное
Ограничения:
Решение задачи в Excel
|
Переменные |
|||
|
Целевая функция: |
3000*А3+2000*В3 |
||
|
Ограничения |
|||
Выполните: Cервис, Поиск решения
Целевая ячейка С4
Установить: М аксимальному значению
Изменяемые ячейки: А3:В3
Ограничения:
После ввода данных нажмите кнопку Выполнить
Полученное решение:
|
Переменные |
|||
|
Целевая функция: |
|||
|
Ограничения: |
|||
Вывод: оптимальным является производство 3,3 т. краски для наружных работ и 1,3 т. краски для внутренних работ в сутки. Этот объем принесет прибыль 12,7 тыс. руб.
Задача 3
Решение транспортной задачи с помощью средства Поиск решения
Фирма имеет четыре фабрики: А, В, С, D и пять центров распределения ее товаров: №1, №2, №3, №4, №5.
Производственные возможности фабрик соответственно составляют:
А – 200, В – 150, С – 225, D – 175 единиц продукции ежедневно.
Потребности центров распределения соответственно составляют:
№1 – 100, №2 – 200, №3 – 50, №4 – 250, №5 – 150 единиц продукции ежедневно.
Хранение на фабрике единицы продукции, не поставленной в центр распределения, составляет $0,75 в день.
Штраф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $2,5 в день.
Стоимость перевозки единицы продукции с фабрик в пункты распределения представлена в таблице:
Спланировать перевозки так, чтобы минимизировать суммарные транспортные расходы.
Модель рассматриваемой задачи сбалансирована (суммарный объем произведенной продукции равен суммарному объему потребностей в ней), значит не нужно учитывать издержки, связанные как со складированием, так и с недопоставками продукции. В противном случае в модель следует ввести:
В случае перепроизводства – фиктивный пункт распределения, стоимость перевозок единицы продукции, в который полагается равной стоимости складирования, а объемы перевозок – объемам складирования излишков продукции на фабриках.
В случае дефицита – фиктивную фабрику, стоимость перевозок единицы продукции с которой полагается равной стоимости штрафов за недопоставку продукции, а объемы перевозок – объемам недопоставок продукции в пункты распределения.
x ij – объем перевозок с i-й фабрики в j-й центр распределения.
c ij – стоимость перевозки единицы продукции с i-й фабрики в j-й центр распределения.
а i – объем производства на i-й фабрике.
в j – спрос в j-м центре распределения.
Т
ребуется
минимизировать суммарные транспортные
расходы, т.е.
Ограничения:
x
ij
0 , i
, j
Механизм решения задачи в Excel с использованием средства Поиск решения
В ячейки А1:Е4 введите стоимости перевозок.
А6:Е9 – отведите под значения неизвестных (объемы перевозок).
В ячейки G6:G9 введите объемы производства на фабриках.
В А11:Е11 – потребность в продукции в пунктах распределения.
В ячейку F10 – введите целевую функцию
В А10:Е10 –введите формулы, определяющие объем продукции, ввозимой в центры распределения
В F6: F9 – формулы, вычисляющие объем продукции, вывозимой с фабрик.
|
СУММ(A6:E6) |
|||||||
|
СУММ(A7:E7) |
|||||||
|
СУММ(A8:E8) |
|||||||
|
СУММ(A9:E9) |
|||||||
|
СУММ(A6:A9) |
СУММ(B6:B9) |
СУММ(C6:C9) |
СУММ(D6:D9) |
СУММ(E6:E9) |
СУММПРОИЗВ(A1:E4;A6:E9) |
||
Сервис Поиск решения
В
окне диалога Поиск решения:
Установить
целевую ячейку $F$10
Равной
мин
имальному
значению
Изменяя
ячейки:
$А$6:$E$9
Ограничения:
$А$10:$E$10=$A$11:$E$11
$А$6:$E$9>=0
$F$6:$F$9=$G$6:$G$9
Щелкните на кнопке Параметры… и установите флажок Линейная модель
Нажмите кнопку Выполнить
Оптимальное решение транспортной задачи будет отражено в диапазоне А6:Е9
Решите транспортную задачу самостоятельно, используя выше описанный механизм.
|
Excel необходимо: ... Задачи линейного программирования. Графический метод решения задач линейного программированияРешениеMicrosoft Excel . Решение задач выпуклого программирования при помощи линейной аппроксимации. Приближённое решение задач математического программирования методом сепарабельного программирования . Экономические задачи , решаемые с помощью ... Инструкция по использованию microsoft Excel для решения задач лп 5 3 Одноиндексные задачи лп 6 > 3 Ввод исходных данных 6 > 3 Решение задачи 13Инструкция1. ЛАБОРАТОРНАЯ РАБОТА №1 “РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ Microsoft Excel ” 1.1. ЦЕЛЬ РАБОТЫ Приобретение навыков решения задач линейного программирования (ЛП) в табличном... Некоторые понятия линейного программированияДокументМы приведем решение этой задачи с помощью программы Tora. рассмотрим реализацию задачи линейного программирования в... задачи с помощью Microsoft Excel . 1. Осуществляем ввод данных в таблицу Excel (рис. 1). Рис. 1. Заполнение листа для решения задачи ... |
Ввод условий задачи состоит из следующих основных шагов:
Создание формы для ввода условий задачи.
Ввод исходных данных.
Ввод зависимостей из математической модели.
Назначение целевой функции.
ввод ограничений и граничных условий.
Ход решения задачи:
Форма для ввода условий задачи:
|
Переменные |
||||||
|
Значение |
||||||
|
Коэффициент в целевой функции |
(формула) |
|||||
|
Ограничения |
||||||
|
Коэффициенты в ограничениях |
Правая часть ограничения |
|||||
Поочередно в представленную форму заносятся коэффициенты целевой функции, ограничений, их знаки, формулы описания целевой функции и ограничений, представленные в математической модели задачи.
Для описания формулы целевой функции и ограничений используется диалоговое окно Мастер функций; категория функций – математические; функция СУММПРОИЗВ. (в диалоговом окне в массиве 1 указывается интервал ячеек значения переменной В3:С3, в массиве 2 – коэффициенты при этих переменных. В функции это интервал ячеек В4:С4, в ограничениях – В8:C8, В9:C9 и т.д.)
Решение задачи осуществляется с использованием команд Сервис, Поиск решения…
В диалоговом окне Поиск решения заполняем строки, указывая адреса ячеек:
Целевая функция: Е4
Равная: max (min)
Изменяя ячейки: указывается месторасположения переменных (В3:C3)
Ограничения: с использованием клавиши Добавить записываются адреса ячеек с указанием условий ограничений (например: D8>= F8 и т.д.). Обязательным является ввод ограничения целочисленного решения.
Если при вводе задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это осуществляется с помощью команд Изменить.., Удалить.
Для получения оптимального решения задачи линейного программирования в Поиске решения задействуется клавиша Параметры…:
Максимальное время: 100 сек
Предельное число итераций: 100
Относительная погрешность 0,000001
Допустимое отклонение: 5%
Устанавливаем флажок Линейная модель, что обеспечивает применение симплекс-метода.
В появившемся окне Поиск решения выполняем команду Выполнить.
Решение найдено, результат оптимального решения приведен в исходной таблице.
Решение задач линейного программирования в Excel
Используя данные прямой двойственной задачи, решите ее в системе Excel, с помощью следующих таблиц
Переменные
Ограничения
|
Вид ресурса |
Коэффициенты в ограничениях |
Левая часть ограничения (формула) |
Правая часть ограничения |
||
Цель работы: изучение современных программных средств решения задачи линейного программирования; практическое решение задач линейного программирования графическим методом, симплекс-методом и средствами программыMicrosoftExcel; программная реализация симплекс-метода на языке программирования высокого уровня.
1. Теоретическая часть
Для решения задач линейного программирования в программе Microsoft Excel имеется надстройка Поиск решения , обращение к которой производится из меню Сервис .
Если команда Поиск решения отсутствует в меню Сервис , то требуется установить надстройку «Поиск решения». Для этого в меню Сервис выбирается команда Надстройки , которая открывает диалоговое окно, показанное на рис. 1.
Покажем использование надстройки «Поиск решения» на примере решения следующей задачи.
Постановка задачи
Предприятие изготавливает и реализует три вида продукции – P 1 , Р 2 и Р 3 . Для производства продукции используются три вида ресурсов – комплектующие изделия, сырье и материалы. Запасы ресурсов и их расход на изготовление единицы продукции каждого вида приведены в табл. 1.
Таблица 1
Прибыль от реализации единицы продукции каждого вида составляет 240, 210 и 180 денежных единиц для P 1 , Р 2 и Р 3 соответственно.
Требуется определить производственную программу предприятия таким образом, чтобы прибыль от реализации продукции была максимальной.
Математическая модель задачи
Обозначим переменными x 1 , x 2 и x 3 искомые объемы производства продукции видов P 1 , Р 2 и Р 2 , а через F – прибыль предприятия. Тогда математическая постановка представленной задачи принимает следующий вид.
Определить значения переменных x 1 , x 2 и x 3 , для которых достигается максимум целевой функции
F = 240 x 1 + 210 х 2 + 180 x 3
при ограничениях:
Целевая функция описывает суммарную прибыль от реализации произведенной продукции всех трех видов. Ограничения (1), (2) и (3) учитывают расход и запасы комплектующих изделий, сырья и материалов соответственно. Поскольку объемы производства продукции не могут быть отрицательными, добавляются условия
x 1 ≥ 0; x 2 ≥ 0; x 3 ≥ 0.
Порядок оптимального решения задачи
Примерные действия, необходимые для решения задачи линейного программирования средствами программы Excel, представим в виде последовательности шагов.
Шаг 1. Исходные данные задачи записываются на рабочем листе электронной таблицы. Один из вариантов показан на рис. 2.
Замечание. Если известно исходное допустимое базисное решение, то можно несколько ускорить процесс поиска оптимального решения. Для этого начальные значения некоторых или всех переменных могут быть заданы вручную. В данном примере для их хранения используются ячейки $B$2, $C$2 и $D$2. Если допустимое базисное решение не задано, то программа Excel автоматически определяет начальные значения переменных задачи.
Шаг 2. В ячейку E3 вводится формула
СУММПРОИЗВ(В3:D3; $B$2:$D$2)
для вычисления текущего значения целевой функции, которая находит сумму попарных произведений ячеек (В3:D3) с коэффициентами при переменных в выражении целевой функции на ячейки ($B$2:$D$2) с текущими значениями переменных.
Шаг 3. Чтобы задать ограничения решаемой задачи, в ячейки E5, E6 и E7 копируется формула из ячейки E3. После этого в указанных ячейках должны быть получены формулы, представленные в табл. 2.
Таблица 2
|
СУММПРОИЗВ(В5:D5; $B$2:$D$2) |
|
|
СУММПРОИЗВ(В6:D6; $B$2:$D$2) |
|
|
СУММПРОИЗВ(В7:D7; $B$2:$D$2) |
Шаг 4. После создания таблицы с исходными данными курсор устанавливается в ячейку E3, содержащую формулу для вычисления целевой функции. Далее в меню Сервис выбирается команда Поиск решения , которая открывает диалоговое окно, приведенное на рис. 3.
В поле Установить целевую ячейку окна «Поиск решения», показанного на рис. 3, должен появиться адрес ячейки с формулой целевой функции (в данном примере это ячейка $E$3).
Затем в этом окне (рис. 3) заполняются следующие поля этого окна:
В поле Равной переключатель вида экстремума целевой функции устанавливается в положение максимальное значение (или минимальное значение при соответствующей постановке задачи);
В поле Изменяя ячейки указывается диапазон ячеек со значениями переменных задачи, выделяемый на рабочем листе электронной таблицы (в примере это ячейки $B$2:$D$2);
В поле Ограничения задаются ограничения исходной задачи. Для этого курсор устанавливается в поле ввода ограничений и нажимается кнопка Добавить . В результате выводится диалоговое окно «Добавление ограничения», показанное на рис. 4.
В этом окне в поле Ссылка на ячейку вводится адрес ячейки с формулой соответствующего ограничения (например, для ограничения (1) это будет ячейка E5), а в поле Ограничение указывается предельное значение, которое может принимать выбранное ограничение (в данном примере правая часть ограничения (1) находится в ячейке G5).
Следует заметить, что заполнение полей Ссылка на ячейку и Ограничение в окне «Добавление ограничения» можно выполнить выделением соответствующих ячеек рабочего листа электронной таблицы.
Затем выбирается вид отношения, связывающего левую и правую части ограничения, что показано на рис. 5.
После нажатия кнопки Добавить в окне «Добавление ограничения» (или кнопки ОК для ввода последнего ограничения) данное ограничение попадает в список ограничений решаемой задачи. С помощью кнопок Удалить и Изменить можно удалять выделенные в списке ограничения или вносить в них исправления.
Замечание . В окне «Добавление ограничения» можно указать, что все или некоторые переменные должны принимать только целые значения (рис. 5). Это позволяет получать решения задач целочисленного линейного программирования (полностью или частично целочисленных).
Шаг 5. После заполнения всех полей окна «Поиск решения» нажимается кнопка Параметры (рис. 3), которая открывает диалоговое окно «Параметры поиска решения», показанное на рис. 6.
В этом окне требуется установить флажки Линейная модель для решения задачи линейного программирования и Неотрицательные значения , если такое условие накладываются на все переменные задачи.
Здесь (рис. 6) также можно определить параметры процесса решения: предельное время поиска решения, максимальное количество итераций, точность и т.п. Флажок Показывать результаты итераций позволяет по шагам следить за поиском решения. Флажок Автоматическое масштабирование включается в том случае, когда разброс значений переменных очень велик.
Шаг 6. Задав необходимые параметры в окне «Параметры поиска решения», следует нажать на кнопку Выполнить для поиска решения задачи (рис. 3) в окне «Поиск решения». Если решение найдено, то на экран выводится окно с соответствующим сообщением (рис. 7).
Полученные результаты отображаются на рабочем листе электронной таблицы, как это показано на рис. 8. В частности, значения переменных - в ячейках $B$2:$D$2, значение целевой функции – в ячейке E3.
Таким образом,
получено оптимальное решение исходной
задачи в виде вектора
,
где
,
и
,
для которого значение целевой функцииF
максимально и составляет F
*
= 129825.
Результаты решения задачи линейного программирования также можно сохранить в виде отдельных рабочих листов с именами Отчет по результатам , Отчет по устойчивости и Отчет по пределам . Для сохранения результатов в виде отчетов необходимо предварительно в поле Тип отчета выделить требуемые типы отчетов (рис. 7). В этом же окне можно отказаться от полученных решений и восстановить исходные значения переменных.
Отчет по результатам для рассмотренной задачи показан на рис. 9.
В данном отчете
представлены оптимальное решение задачи
линейного программирования и его
расположение в области допустимых
решений. В графах Результат
выводятся
оптимальные значения целевой функции
F
*
и переменных задачи
,
а также их значения для исходного
базисного решения, с которого начинался
поиск оптимального решения (графаИсходное
значение
).
Состояние
ограничений (графа Статус
)
характеризует расположение точки
в области допустимых решений. ГрафаРазница
показывает разности между значениями
левых и правых частей ограничений
(невязки). Для связанного ограничения
невязка равна нулю, что свидетельствует
о расположение точки
на границе области допустимых решений,
которая задается этим ограничением.
Если ограничение являются не связанным,
то оно не влияет на оптимальное решение.
Замечание . В экономической интерпретации связанные ограничения соответствуют дефицитным ресурсам. Для не связанных ограничений графа Разница показывает оставшиеся объемы неиспользованных не дефицитных ресурсов. В рассмотренной задаче ограничения (1) и (3) соответствуют комплектующим изделиям и материалам, которые являются дефицитными ресурсами. Ограничение (2) является не связанным, т.е. не влияет на оптимальный план производства продукции по критерию максимальной прибыли. Это означает, что второй ресурс (сырье) не использован в объеме 292,5 ед.
В отчете по устойчивости (рис. 10) приведены границы устойчивости переменных задачи (графы Допустимое увеличение и Допустимое уменьшение коэффициентов целевой функции), а также границы устойчивости теневых цен (т.е. переменных двойственной задачи), в пределах которых оптимальное решение не изменяется. Большие значения пределов (1Е+30) означают фактическое отсутствие соответствующих границ, т.е. переменная может изменяться до бесконечности.
В графе Нормированная стоимость элемент во второй строке (-150) показывает, на сколько уменьшится значение функции, если в решении переменную x 2 увеличить на единицу. С другой стороны, при допустимом увеличении коэффициента функции при неизвестной x 2 на 150 единиц значение этой переменной не изменится, т.е. неизвестная x 2 будет равна нулю, а если выйти за пределы допустимого увеличения (коэффициент при x 2 увеличить более чем на 150), то неизвестная x 2 в решении будет больше нуля.
В отчете по пределам (рис. 11) показаны нижние и верхние пределы возможного изменения переменных (в пределах области допустимых решений) и соответствующие значения целевой функции (графа Целевой результат ) при этих изменениях. В частности, если x 1 = 0, а x 2 и x 3 остаются без изменений, то F = 2400 + 2100 + 180191,25 = 34425; при x 3 = 0 и неизменных x 1 и x 2 получим F = 240397,5 + 2100 + 1800 = 95400.
Размер: px
Начинать показ со страницы:
Транскрипт
1 Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет» Решение задач линейного программирования в Microsoft Excel 00 Методические указания к выполнению лабораторных работ по информатике для обучающихся по всем программам бакалавриата и специалитета дневной формы обучения Хабаровск Издательство ТОГУ 05
2 УДК 68.58(076.5) Решение задач линейного программирования в Microsoft Excel 00: методические указания к выполнению лабораторных работ по информатике для обучающихся по всем программам бакалавриата и специалитета дневной формы обучения / сост. Н. Д. Берман, Н. И. Шадрина. Хабаровск: Изд-во Тихоокеан. гос. ун-та, с. Методические указания составлены на кафедре информатики. Включают общие сведения о задачах линейного программирования, задания для выполнения лабораторных работ с вариантами задач, рекомендательный библиографический список. Печатается в соответствии с решениями кафедры информатики и методического совета факультета компьютерных и фундаментальных наук. Тихоокеанский государственный университет, 05
3 . ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В MICROSOFT EXCEL 00. ОБЩИЕ СВЕДЕНИЯ Общая характеристика задач оптимизации Задачи линейной оптимизации относятся к широко распространённому классу задач, встречающихся в различных сферах деятельности: в бизнесе, на производстве, в быту. Как оптимально распорядиться бюджетом или за минимальное время добраться до нужного места в городе, как наилучшим образом спланировать деловые встречи, минимизировать риски капитальных вложений, определить оптимальные запасы сырья на складе это те задачи, в которых нужно найти наилучшее из всех возможных решений. Различают следующие типы линейных оптимизационных задач: задачи о перевозках, например, минимизация расходов по доставке товаров с нескольких фабрик в несколько магазинов с учетом спроса; задачи распределения рабочих мест, например, минимизация расходов на содержание штата с соблюдением требований, определенных законодательством; управление ассортиментом товаров: извлечение максимальной прибыли с помощью варьирования ассортиментным набором товаров (при соблюдении требований клиентов). Аналогичная задача возникает при продаже товаров с разной структурой затрат, рентабельностью и показателями спроса; замена или смешивание материалов, например, манипуляция материалами с целью снижения себестоимости, поддержания необходимого уровня качества и соблюдения требований потребителей; задача о диете. Из имеющихся в распоряжении продуктов требуется составить такую диету, которая, с одной стороны, удовлетворяла бы минимальным потребностям организма в питательных веществах (белки, жиры, углеводы, минеральные соли, витамины), с другой требовала бы наименьших затрат; задача распределения ресурсов, например, распределение ресурсов между работами таким образом, чтобы максимизировать прибыль, или минимизировать затраты, или определить такой состав работ, который можно выполнить, используя имеющиеся ресурсы, и при этом достичь максимума опре- 3
4 деленной меры эффективности, или рассчитать, какие ресурсы необходимы для того, чтобы выполнить заданные работы с наименьшими издержками. Математическая постановка задачи линейного программирования Рассмотрим наиболее распространенный класс оптимизационных задач задачи линейного программирования. К такому классу относятся задачи, описываемые линейными математическими моделями. Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции () при условиях: () () () (3) () (4) где заданные постоянные величины и Функция () называется целевой функцией задачи, а условия ()(4) ограничениями задачи. Совокупность чисел (), удовлетворяющих ограничениям задачи, называется допустимым решением. Решение, при котором целевая функция задачи принимает максимальное (минимальное) значение, называется оптимальным. Использование надстройки Excel для решения задач линейного программирования Поиск решения это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Если команда Поиск решения или группа Анализ отсутствует, необходимо загрузить надстройку Поиск решения. 4
5 На вкладке Файл выберите команду Параметры, а затем категорию Надстройки (рис.). Рис. В поле Управление выберите значение Надстройки Excel и нажмите кнопку Перейти. В поле Доступные надстройки установите флажок рядом с пунктом Поиск решения (рис.) и нажмите кнопку ОК. Рис. Пример решения оптимизационных линейных задач в MS Excel 00 Схема решения задач линейного программирования в MS Excel 00 следующая: 5
6 . Составить математическую модель.. Ввести на рабочий лист Excel условия задачи: а) создать форму на рабочем листе для ввода условий задачи; б) ввести исходные данные, целевую функцию, ограничения и граничные условия. 3. Указать параметры в диалоговом окне Поиск решения. 4. Проанализировать полученные результаты. Рассмотрим решение задачи оптимизации на примере. Пример. Задача определения оптимального ассортимента продукции Предприятие изготавливает два вида продукции П и П, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья А и В. Максимально возможные запасы сырья в сутки составляют 9 и 3 ед. соответственно. Расход сырья на единицу продукции вида П и П табл.. Таблица Сырье Расход сырья на ед. продукции П П Запас сырья, ед. А 3 9 В 3 3 Опыт работы показал, что суточный спрос на продукцию П никогда не превышает спроса на продукцию П более чем на ед. Кроме того, известно, что спрос на продукцию П никогда не превышает ед. в сутки. Оптовые цены единицы продукции равны: 3 д. е. для П и 4 д. е. для П. Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным? Решение. Построим математическую модель для решения поставленной задачи. Предположим, что предприятие изготовит x единиц продукции П и x единиц продукции П. Поскольку производство продукции ограничено имеющимися в распоряжении предприятия сырьем каждого вида и спросом на данную продукцию, а также учитывая, что количество изготовляемых изделий не может быть отрицательным, должны выполняться следующие неравенства: 6
7 Доход от реализации x единиц продукции П и x единиц продукции П составит Cреди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значения F max. Рассматриваемая задача относится к разряду типовых задач оптимизации производственной программы предприятия. В качестве критериев оптимальности в этих задачах могут быть также использованы: прибыль, себестоимость, номенклатура производимой продукции и затраты станочного времени. Создадим на рабочем листе форму для ввода исходных данных (рис. 3). Заливкой выделены ячейки для ввода функций. Рис. 3 В ячейку E5 введем формулу для целевой функции (рис. 4). Используя обозначения соответствующих ячеек в Excel, формулу для расчета целевой функции можно записать как сумму произведений каждой из ячеек, отведенной для значений переменных задачи (B3, C3), на соответствующие ячейки, отведенные для коэффициентов целевой функции (B5, C5). 7
8 Рис. 4 Аналогично в ячейки D0:D введены формулы для расчета левой части ограничений (рис. 5). Рис. 5 На вкладке Данные в группе Анализ выберем команду Поиск решения. В диалоговом окне Параметры поиска решения установим следующее (рис. 6): 8
9 в поле Оптимизировать целевую функцию выбираем ячейку со значением целевой функции Е5; выбираем, максимизировать или минимизировать целевую функцию; в поле Изменяя ячейки переменных выбираем ячейки со значениями искомых переменных B3:C3 (пока в них нули или пусто); в области В соответствии с ограничениями с помощью кнопки Добавить размещаем все ограничения нашей задачи (рис. 7); в поле Выберите метод решения указываем Поиск решения линейных задач симплекс-методом; нажимаем кнопку Найти решение. Рис. 6 9
10 Добавляем ограничения для нашей задачи. Для неравенств указываем в поле Ссылка на ячейки диапазон D0:D, выбираем в раскрывающемся списке знак неравенства, в поле Ограничение выделяем диапазон F0:F и нажимаем кнопку Добавить (рис. 7), чтобы принять ограничение и добавить следующее ограничение. Для принятия ограничения и возврата к диалоговому окну Поиск решения нажмите кнопку Ok. Рис. 7 Покажем окна для добавления ограничений: преобразуем в (рис. 8); Рис. 8 0
11 (рис. 9); Рис. 9, (рис. 0). Рис. 0 После выбора кнопки Найти решение появляется окно Результаты поиска решения (рис.). Рис.
12 Для сохранения полученного решения необходимо использовать переключатель Сохранить найденное решение в открывшемся окне диалога Результаты поиска решения. После чего рабочий лист примет вид, представленный на рис.. Рис. Сохранить модель поиска решения можно следующим образом:) при сохранении книги Excel после поиска решения все значения, введенные в окнах диалога Поиск решения, сохраняются вместе с данными рабочего листа. С каждым рабочим листом в рабочей книге можно сохранить один набор значений параметров Поиска решения;) если в пределах одного рабочего листа Excel необходимо рассмотреть несколько моделей оптимизации (например, найти максимум и минимум одной функции или максимальные значения нескольких функций), то удобнее сохранить эти модели, используя кнопку Загрузить/Сохранить окна Параметры поиска решения. Диапазон для сохраняемой модели содержит информацию о целевой ячейке, об изменяемых ячейках, о каждом из ограничений и все значения диалога Параметры. Выбор модели для решения конкретной оптимизационной задачи осуществляется с помощью кнопки Загрузить/сохранить диалогового окна Параметры поиска решения; 3) сохранить модель можно в виде именованных сценариев, для этого необходимо нажать на кнопку Сохранить сценарий диалогового окна Результаты поиска решений (см. рис.). Кроме вставки оптимальных значений в изменяемые ячейки, Поиск решения позволяет представлять результаты в виде трех отчетов (Результаты,
13 Устойчивость и Пределы). Для генерации одного или нескольких отчетов необходимо выделить их названия в окне диалога Результаты поиска решения (рис.). Рассмотрим более подробно каждый из них. Отчет по устойчивости (рис. 3) содержит информацию о том, насколько целевая ячейка чувствительна к изменениям ограничений и переменных. Этот отчет имеет два раздела: один для изменяемых ячеек, а второй для ограничений. Правый столбец в каждом разделе содержит информацию о чувствительности. Каждая изменяемая ячейка и ограничения приводятся в отдельной строке. При использовании целочисленных ограничений Excel выводит сообщение Отчеты об устойчивости и Пределы не применимы для задач с целочисленными ограничениями. Рис. 3 Отчет по результатам (рис. 4) содержит три таблицы: в первой приведены сведения о целевой функции до начала вычисления, во второй значения искомых переменных, полученные в результате решения задачи, в третьей результаты оптимального решения для ограничений. Этот отчет также содержит информацию о таких параметрах каждого ограничения, как статус и разница. Статус может принимать три состояния: связанное, несвязанное или невыполненное. Значение разницы это разность между значением, выводимым в ячейке ограничения при получении решения, и числом, заданным в правой части формулы ограничения. Связанное ограничение это ограничение, для которого значение разницы равно нулю. Несвязанное 3
14 ограничение это ограничение, которое было выполнено с ненулевым значением разницы. Рис. 4 Отчет по пределам (рис. 5) содержит информацию о том, в каких пределах значения изменяемых ячеек могут быть увеличены или уменьшены без нарушения ограничений задачи. Для каждой изменяемой ячейки этот отчет содержит оптимальное значение, а также наименьшие значения, которые ячейка может принимать без нарушения ограничений. Рис. 5 4
15 Полученное решение означает, что объем производства продукции вида П должен быть равен,4 ед., а продукции П,4 ед. продукции. Доход, получаемый в этом случае, составит,8 д. е. Допустим, что к условию задачи добавилось требование целочисленности значений всех переменных. В этом случае описанный выше процесс ввода условия задачи необходимо дополнить следующими шагами. В окне Поиск решения нажмите кнопку Добавить и в появившемся окне Добавление ограничений введите ограничения следующим образом (рис. 6): в поле Ссылка на ячейки введите адреса ячеек переменных задачи B3:C3; в поле ввода знака ограничения установите целое; подтвердите ввод ограничения нажатием кнопки OK. Рис. 6 Решение задачи при условии целочисленности ее переменных рис. 7. Рис. 7 5
16 . ЛАБОРАТОРНЫЕ РАБОТЫ Лабораторная работа Задание Найти максимум линейной функции при заданной системе ограничений. Вариант Целевая функция F Ограничения { { { { 3 { { 4 { { 5 { { 6 { { 7 { { 8 { { 9 { { 0 { { { { { { 3 { { 4 { { 5 { { 6
17 Лабораторная работа Задание. Построить математическую модель задачи.. Представить ее в табличной форме на листе Excel. 3. Найти решение задачи средствами надстройки Поиск решения. 4. Вывести отчеты по результатам и устойчивости. Вариант Для производства столов и шкафов мебельная фабрика использует необходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида табл.. Таблица Ресурсы Древесина, м 3: -го вида -го вида Нормы затрат ресурсов на одно изделие Стол Шкаф 0, 0, 0, 0,3 Общее количество ресурсов Трудоемкость, чел.ч,5 37,4 Прибыль от реализации одного изделия, р. 6 8 Определить, сколько столов и шкафов следует изготавливать фабрике, чтобы прибыль от их реализации была максимальной. Ответ. Прибыль 940 р. при количестве столов и шкафов 0 и 66. Вариант Для производства двух видов изделий A и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида, общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия табл. 3. 7
18 Таблица 3 Затраты времени, стан.-ч, Тип оборудования на обработку одного изделия А В Фрезерное 0 8 Токарное 5 0 Шлифовальное 6 Прибыль от реализации одного изделия, р. 4 8 Общий фонд полезного рабочего времени оборудования, ч Найти план выпуска изделий А и В, обеспечивающий максимальную прибыль от их реализации. Ответ. Прибыль 76 р. при выпуске изделий и 6. Вариант 3 Для изготовления трех видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования, общий фонд рабочего времени каждого из типов используемого оборудования, прибыль от реализации одного изделия данного вида табл. 4. Таблица 4 Тип оборудования Фрезерное Токарное Сварочное Шлифовальное Затраты времени, стан.-ч, на обработку одного изделия вида А В С Прибыль, р. 0 4 Общий фонд рабочего времени оборудования, ч Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Ответ. Прибыль 49 р. при выпуске изделий 4, 8, 0. 8
19 Вариант 4 Для поддержания нормальной жизнедеятельности человеку ежедневно необходимо потреблять не менее 8 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в кг каждого вида потребляемых продуктов, а также цена кг каждого из этих продуктов табл. 5 Таблица 5 Питательные вещества Содержание, г, питательных веществ в кг продуктов Мясо Рыба Молоко Масло Сыр Крупа Картофель Белки Жиры Углеводы Минеральные соли Цена кг продуктов, р.,8,0 0,8 3,4,9 0,5 0, Составить дневной рацион, содержащий не менее минимальной суточной нормы потребности человека в необходимых питательных веществах при минимальной общей стоимости потребляемых продуктов. Ответ. Минимальная общая стоимость 0, р. при количестве продуктов: мясо 0; рыба 0; молоко 0; масло 0,03335; сыр 0; крупа 0,9053; картофель 0. Вариант 5 Кондитерская фабрика для производства трех видов карамели А, В, и С использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья каждого вида на производство т карамели данного вида, общее количество сырья каждого вида, прибыль от реализации т карамели табл. 6. 9
20 Таблица 6 Вид сырья Сахарный песок Патока Фруктовое пюре Нормы расхода сырья, т, на т карамели А В С 0,8 0,4 0,5 0,4 0, 0,6 0,3 0, Прибыль от реализации т продукции, р Общее количество сырья, т Найти план производства карамели, обеспечивающий максимальную прибыль от ее реализации. Ответ. Максимальная прибыль р. при выпуске карамели 00, 0, 00 т. Вариант 6 На швейной фабрике для изготовления четырех видов изделий может быть использована ткань трех артикулов. Нормы расхода тканей всех артикулов на пошив одного изделия, имеющееся в распоряжении фабрики общее количество тканей каждого артикула и цена одного изделия данного вида табл. 7. Таблица 7 Артикул ткани I II III Норма расхода ткани, м, на одно изделие вида 3 4 Цена одного изделия, р Общее количество ткани, м Определить, сколько изделий каждого вида должна произвести фабрика, чтобы стоимость изготовленной продукции была максимальной. Ответ. Максимальная стоимость продукции 5 р. при выпуске изделий 95, 0, 0, 0. 0
21 Вариант 7 Предприятие выпускает четыре вида продукции и использует три типа основного оборудования: токарное, фрезерное и шлифовальное. Затраты времени на изготовление единицы продукции для каждого из типов оборудования, общий фонд рабочего времени каждого из типов оборудования и прибыль от реализации одного изделия данного вида табл. 8. Таблица 8 Затраты времени, стан.-ч, Тип оборудования на единицу продукции вида 3 4 Токарное Фрезерное Шлифовальное Прибыль от реализации 3 единицы продукции, р. 8 3 Общий фонд рабочего времени, стан.-ч Определить такой объем выпуска каждого из изделий, при котором общая прибыль от их реализации является максимальной. Ответ. Максимальная прибыль 965 р. при выпуске изделий 70, 35, 0, 0. Вариант 8 Торговое предприятие планирует организовать продажу четырех видов товара, используя при этом только два вида ресурсов: рабочее время продавцов в количестве 840 ч и площадь торгового зала 80 м. При этом известны плановые нормативы затрат этих ресурсов в расчете на единицу товаров и прибыль от их продажи табл. 9. Таблица 9 Показатели Расход рабочего времени на единицу товара, ч Использование площади торгового зала на единицу товара, м Товар А В С D 0,6 0,8 0,6 0,4 0, 0, 0,4 0, Прибыль от продажи единицы товара, р Общее количество ресурсов
22 Требуется определить оптимальную структуру товарооборота, обеспечивающую торговому предприятию максимальную прибыль. Ответ. Максимальная прибыль 6 00 р. при продаже товаров 0, 0, 0, 800. Вариант 9 Из трех видов сырья необходимо составить смесь, в состав которой должно входить не менее 6 ед. химического вещества А, 30 ед. вещества В и 4 ед. вещества С. Количество единиц химического вещества, содержащегося в кг сырья каждого вида, цена кг сырья каждого вида табл. 0 Таблица 0 Вещество А В С Цена кг сырья, р. Количество единиц вещества, содержащегося в кг сырья вида Составить смесь, содержащую не менее нужного количества веществ данного вида и имеющую минимальную стоимость. Ответ. Минимальная стоимость 6 р. при количестве 0; 0; 0; 6,5 кг. Вариант 0 Для производства трех видов продукции предприятие использует два типа технологического оборудования и два вида сырья. Нормы затрат сырья и времени на изготовление одного изделия каждого вида, общий фонд рабочего времени каждой из групп технологического оборудования, объемы имеющегося сырья каждого вида, цена одного изделия каждого вида, ограничения на возможный выпуск каждого из изделий табл..
23 Ресурсы Производительность оборудования в нормочасах: I типа II типа Сырье, кг: -го вида -го вида Цена одного изделия, р. Выпуск, шт.: минимальный максимальный Нормы затрат на одно изделие вида Таблица Общее количество ресурсов Составить план производства продукции, по которому будет изготовлено необходимое количество изделий каждого вида, при максимальной общей стоимости всей изготовляемой продукции. Ответ. Общая стоимость 495 р. при выпуске продукции 0, 33, 45. Вариант При производстве четырех видов кабеля выполняется пять групп технологических операций. Нормы затрат на км кабеля данного вида для каждой из групп операций, прибыль от реализации км каждого вида кабеля, а также общий фонд рабочего времени, в течение которого могут выполняться эти операции, табл. Таблица Технологическая операция Нормы затрат времени, ч, на обработку км кабеля вида 3 4 Волочение Наложение изоляций Скручивание элементов в кабель Освинцовывание Испытание и контроль,0 6,4 3,0,8 0,4 5,6,5,6 0,8 6,0,8 0,8,4 0,7 8,0,4 3,0 Прибыль от реализации км кабеля, р., 0,8,0,3 Общий фонд рабочего времени, ч
24 Определить план выпуска кабеля, при котором общая прибыль от реализации изготовляемой продукции является максимальной. Ответ. Общая прибыль от реализации 939,48 57 р. при выпуске 00; 64,8 57; 0; 0. Вариант Стальные прутья длиной 0 см необходимо разрезать на заготовки длиной 45, 35 и 50 см. Требуемое количество заготовок данного вида составляет соответственно 40, 30 и 0 шт. Возможные варианты разреза и величина отходов при каждом из них табл. 3. Таблица 3 Варианты разреза Длина заготовки, см Величина отходов, см Определить, сколько прутьев по каждому из возможных вариантов следует разрезать, чтобы получить не менее нужного количества заготовок каждого вида при минимальных отходах. Ответ. Минимальные отходы равны 550 см при количестве прутьев 0, 0, 0, 0, 0, 0 шт. Вариант 3 Для производства трех видов изделий А, В, С предприятие использует четыре вида сырья. Нормы затрат сырья каждого вида на производство единицы продукции данного вида, прибыль от реализации одного изделия каждого вида табл. 4. 4
25 Таблица 4 Нормы затрат сырья, кг, на единицу продукции Вид сырья А В С I II III IV Прибыль от реализации одного изделия Изделия А, В и С могут производиться в любых соотношениях (сбыт обеспечен), но для их производства предприятие может использовать сырье I вида не более 00 кг, II вида не более 0 кг, III вида не более 80 кг, IV вида не более 38 кг. Определить план производства продукции, при котором общая прибыль предприятия от реализации всей продукции была бы наибольшей. Ответ. План производства изделий 7, 5, 0 кг при общей прибыли 5 кг. Вариант 4 Туристическое агентство собирается заказать издательству выпуск художественных альбомов трех типов A, B, C. Их изготовление лимитируется затратами ресурсов трех видов, удельные расходы которых приведены в табл. 5. Вид ресурса Финансы, $ Бумага, л. Трудозатраты, чел. ч Таблица 5 Удельные затраты ресурсов на выпуск альбомов A B C 4 4 Издательство для выполнения заказа получило финансовые средства в объеме $ 3 600, имеет в наличии л. бумаги и может использовать трудовые ресурсы в объеме 00 чел. ч. Агентство платит за выпуск одного альбома типа А дол., за альбом В 8 дол., за альбом С 30 дол. 5
26 Сколько альбомов каждого типа должно выпустить издательство, чтобы получить наибольшую прибыль? Ответ. Максимальный суммарный доход дол., количество альбомов: 400; 800; 0 шт. Вариант 5 Предприятие оптовой торговли может реализовать T j, j, 4 группы товаров. Для этого используется несколько видов ресурсов. Исходные данные для построения математической модели табл. 6. Лимитирующие ресурсы и показатели Товарная группа T T T 3 T4 Объем ресурса Таблица 6 Складские площади, м Трудовые ресурсы, чел.ч Издержки обращения, ден. ед Товарные запасы, ден. ед План товарооборота, ден. ед Минимально допустимые значения товарооборота по j-й группе, ед. Прибыль в расчете на единицу товарооборота j-й группы, ден. ед. Вид огра ниче- ния Требуется рассчитать план хозяйственной деятельности торгового предприятия, обеспечивающий максимум прибыли при заданных ограничениях на складские площади, трудовые ресурсы, издержки обращения, товарные запасы, величину товарооборота, если торговая прибыль в расчете на единицу товарооборота j -й группы задана. Ответ. Максимальна прибыль ден. ед. Товарооборот по группам: Т 00 ед., Т 000 ед., Т ед., Т ед. 6
27 3. РЕКОМЕНДАТЕЛЬНЫЙ БИБЛИОГРАФИЧЕСКИЙ СПИСОК. Акулич, И. Л. Математическое программирование в примерах и задачах: учеб. пособие для студентов экон. спец. сузов / И. Л. Акулич. М. : Высш. шк., с.. Леоненков, А. В. Решение задач оптимизации в среде MS Excel / А. В. Леоненков. СПб. : БХВ-Петербург, с. 3. Васильев, А. Н. Финансовое моделирование и оптимизация средствами Excel007 / А. Н. Васильев. СПб. : Питер, с. 4. Уокенбах, Дж. Microsoft Excel 00. Библия пользователя: пер. с англ. / Дж. Уокенбах. М. : И. Д. Вильямс, 0. 9 с. 5. Уокенбах, Дж. Формулы в Microsoft Excel 00: пер. с англ. / Дж. Уокенбах. М. : И. Д. Вильямс, с. 6. Иванов, И. Microsoft Excel 00 для квалифицированного пользователя / И. Иванов. М. : Академия АЙТИ, с. 7. Справка и инструкции по Excel // Поддержка по Microsoft Office [Электронный ресурс]. Режим доступа: (дата обращения:). 8. Решение задач оптимизации управления с помощью MS Excel 00 // НОУ «ИНТУИТ» [Электронный ресурс]. Режим доступа: (дата обращения:). Оглавление. Задачи линейного программирования в Microsoft Excel 00. Общие сведения... 3 Общая характеристика задач оптимизации... 3 Математическая постановка задачи линейного программирования... 4 Использование надстройки Excel для решения задач линейного программирования... 4 Пример решения оптимизационных линейных задач в MS Excel Лабораторные работы... 6 Лабораторная работа... 6 Лабораторная работа Рекомендательный библиографический список
28 Решение задач линейного программирования в Microsoft Excel 00 Методические указания к выполнению лабораторных работ по информатике для обучающихся по всем программам бакалавриата и специалитета дневной формы обучения Нина Демидовна Берман Нина Ивановна Шадрина Главный редактор Л. А. Суевалова Редактор Е. Н. Ярулина Подписано в печать Формат 60 x 84 / 6. Бумага писчая. Гарнитура «Калибри». Печать цифровая. Усл. печ. л.,68. Тираж 60 экз. Заказ 70. Издательство Тихоокеанского государственного университета, Хабаровск, ул. Тихоокеанская, 36. Отдел оперативной полиграфии издательства Тихоокеанского государственного университета, Хабаровск, ул. Тихоокеанская, 36. 8
ОБЪЕМНОЕ ПЛАНИРОВАНИЕ РАБОТЫ ТЕХНОЛОГИЧЕСКИХ СТАНОЧНЫХ СИСТЕМ Х а б а р о в с к 2 0 0 9 Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования
Практическое занятие 3. 1. Для данных условий сформулируйте оптимизационную задачу, составьте математическую модель, найдите оптимальный план производства с помощью надстройки «Поиск решения» в EXCEL.
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Тихоокеанский государственный университет» Н. И. Шадрина, Н.
Составление, решение и анализ задачи линейного программирования в Excel ЗАДАНИЕ. Построить математическую модель задачи и решить её средствами Excel. Записать сопряжённую задачу. Провести анализ и сделать
Задача распределения ресурсов предприятия Содержательная постановка задачи Фабрика выпускает сумки: женские, мужские, дорожные. Данные о материалах, используемых для производства сумок и месячный запас
Лабораторная работа 11 Решение задачи оптимального распределения ресурсов Задание Предприятие выпускает продукты нескольких видов. Для их изготовления используется сырье различного типа. Известны нормы
Лабораторная работа 3_9. Поиск и принятие решений в Excel. Что осваивается и изучается? Решение задачи определения оптимального плана и транспортной задачи при помощи надстройки «Поиск решения». Задание
Лабораторная работа 3. Поиск решения в Microsoft Excel Целью лабораторной работы является изучение возможностей средства Поиск решения MS Excel для решения оптимизационных задач. К защите лабораторной
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬ- НОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ДОНСКОЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» Кафедра «Технология
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «ТИХООКЕАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Совместная работа
ЛАБОРАТОРНАЯ РАБОТА СРЕДСТВА ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ КАК ФУНКЦИИ EXCEL Команда Подбор параметра Задание 1. Рассмотрим задачу, составленную на основании задачи по использованию функции ЧПС. Вас просят
ВАРИАНТ Для изготовления изделий двух видов имеется 00 кг металла. На одно изделие -го вида расходуется кг металла, а изделия -говида кг. Составить план производства, обеспечивающий получение наибольшей
Лабораторная работа 4 Тема работы: Решение задачи об оптимальном распределении ресурсов при выпуске продукции с использованием процедуры Поиск решения Microsoft Excel. Цель работы: Научиться использовать
Практическая работа 5.4. Решение задачи об оптимальном распределении ресурсов при выпуске продукции с использованием процедуры «Поиск решения» Microsoft Excel Цель работы. Выполнив эту работу, Вы научитесь:
Московская Государственная Академия Тонкой Химической Технологии имени М. В. Ломоносова Корнюшко В.Ф., Морозова О.А. Детерминированные модели экономических систем Методическое пособие по дисциплине Математические
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КУРГАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КАФЕДРА «ИНФОРМАТИКА» РЕАЛИЗАЦИЯ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ В СРЕДЕ EXCEL Методические указания к проведению лабораторных
Оптимизация производственной программы Методические указания к лабораторной работе по экономике электротехнической промышленности Ульяновск 009 В 9 Васильев, В. Н. Оптимизация производственной программы
Экономико-математические методы и моделирование. Практическая работа 2. Симплексный метод решения задач линейного программирования. Решить задачу линейного программирования (ЛП) симплексным методом. Расчеты
РАБОТА 2 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель работы: ознакомление с методами решения задач линейного программирования в табличном процессоре Ecel. Решение экономических задач, как правило, связано
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет» Кафедра «Технология деревообработки» МОДЕЛИРОВАНИЕ
АНАЛИЗ ДАННЫХ В MS EXCEL Гедранович Валентина Васильевна 27 июня 2012 г. Аннотация Глава 11 из УМК: Гедранович, В.В. Основы компьютерных информационных технологий: учеб.-метод. комплекс / В.В. Гедранович,
Решение задачи линейного программирования графическим методом, симплекс-методом и через «Поиск решения» в Ecel ЗАДАНИЕ. Предприятие выпускает два вида продукции: Изделие и Изделие. На изготовление единицы
Лабораторная работа 3. Надстройка Поиск решения в Microsoft Excel. Диспетчер сценариев в Microsoft Excel. Целью данной лабораторной работы является изучение возможностей средства Поиск решения в Microsoft
Негосударственное образовательное частное учреждение высшего профессионального образования Уральский институт фондового рынка Кафедра Экономики предприятия ЭКОНОМИКА ФИРМЫ Сборник кейсов тема «Планирование
Практическое занятие 4. Для условий задачи cформулируйте двойственную задачу и найдите объективно обусловленные оценки. Проанализируйте использование ресурсов в оптимальном плане. Вариант 1. Для изготовления
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Курганский государственный университет» Кафедра
ЛАБОРАТОРНАЯ РАБОТА 6 Тема: Анализ данных в OpenOffice Calc 1. Основные понятия Процесс изменения значений ячеек и анализа влияния этих изменений на результат вычисления формул в OpenOffice.org Calc называется
Подбор параметра При обработке табличных данных часто возникает необходимость в прогнозировании результата на основе известных исходных данных или наоборот, в определении того, какими должны быть исходные
2 ПЛАН ЛЕКЦИИ: АНАЛИЗ ДАННЫХ В MS EXCEL Информатика 2 семестр Кондратенко Ольга Брониславовна [email protected] Инструмент анализа «что если» Инструмент анализа «что если» создание таблиц данных с одной
Практическая работа 13 Тема: ЗАДАЧИ ОПТИМИЗАЦИИ (ПОИСК РЕШЕНИЯ) В MICROSOFT EXCEL Цель занятия. Изучение технологии поиска решения для задач оптимизации (минимизации, максимизации). Задание 13.1. Минимизация
Приложение Содержимое кейса Задача 1 Одна вновь организованная коммерческая фирма решила выпускать два типа стульев х1 и х2. Для их производства необходимо два вида материалов: дерево и ткань. Фирма ежемесячно
ЛАБОРАТОРНАЯ РАБОТА 2 ИСПОЛЬЗОВАНИЕ MICROSOFT EXCEL 2007 ПРИ РЕШЕНИИ ПРАКТИЧЕСКИХ ЗАДАЧ (ДЛЯ СТУДЕНТОВ НАПРАВЛЕНИЯ 100800.62) 2.1 Решение задач оптимизации Задача. Завод производит электронные приборы
МОСКОВСКИЙ РАДИОТЕХНИЧЕСКИЙ КОЛЛЕДЖ им. А.А.Расплетина ЛАБОРАТОРНАЯ РАБОТА По предмету «Математические методы» «Двухиндексные задачи линейного программирования» Составил: Преподаватель МРТК им.а.а.расплетина
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ федеральное государственное автономное образовательное учреждение высшего образования «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» УТВЕРЖДАЮ
СОДЕРЖАНИЕ. ЗАДАНИЕ.... ЭТАПЫ РАБОТЫ..... Формирование математической модели задачи..... Решение прямой задачи симплекс-методом..... Построение двойственной задачи... 6.4. Решение прямой и двойственной
ЛАБОРАТОРНАЯ РАБОТА РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ Microsoft Ecel ЦЕЛЬ РАБОТЫ Приобретение навыков решения задач линейного программирования (ЛП) в табличном редакторе Microsoft
МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ» Кафедра «Технология машиностроения»
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМ. Р.
Тверь Реферат Сервис Содержание Задача 1. Ассортимент продукции... 3 Условие задачи... 3 Математическая постановка задачи... 3 Табличная модель задачи... 5 Отчет о результатах решения задачи 1.... 6 Вывод...
ЗАДАНИЕ ПРАКТИЧЕСКОЙ РАБОТЫ 4 И ПРАКТИЧЕСКОЙ РАБОТЫ 5 Задачи линейной оптимизации Построение экономико-математических моделей (ЭММ). Решение задач линейной оптимизации с использованием информационных технологий.
ЛАБОРАТОРНЫЕ РАБОТЫ ПО MS EXCEL 2007 ЛАБОРАТОРНАЯ РАБОТА 1.... 1 ЛАБОРАТОРНАЯ РАБОТА 2... 3 ЛАБОРАТОРНАЯ РАБОТА 3... 4 ЛАБОРАТОРНАЯ РАБОТА 4... 7 ЛАБОРАТОРНАЯ РАБОТА 5... 8 ЛАБОРАТОРНАЯ РАБОТА 6... 10
Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Ульяновский государственный технический университет ИНФОРМАЦИОННЫЕ СИСТЕМЫ В ЭКОНОМИКЕ
1 Лабораторная работа 3 Решение задач. Подбор параметров, поиск решения 1. Реализация математической модели в Excel Математическая модель это описание состояния поведения некоторой реальной системы (объекта,
Gnumeric: электронная таблица для всех И.А.Хахаев, 2007-2010 7 Линейная оптимизация (поиск решения) 7.1 Оптимизация как задача линейного программирования Пусть имеется функция, называемая целевой, линейно
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА Государственное образовательное учреждение высшего профессионального образования «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» Институт экономики
МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего образования «Самарский государственный технический университет» ИНЖЕНЕРНО-ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ КАФЕДРА ЭКОНОМИКИ
ЗАНЯТИЕ ПРИБЛИЖЕННОЕ РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ Отделение корней Пусть дано уравнение f () 0, () где функция f () C[ a; Определение Число называется корнем уравнения () или нулем функции f (), если
Министерство образования и науки Российской Федерации Федеральное агентство по образованию Саратовский государственный технический университет РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ В СРЕДЕ MS EXCEL Методические указания
«Юго-Западный государственный университет» ЮЗГУ) Кафедра конструирования и технологии электронновычислительных средств МЕТОДЫ УСЛОВНОЙ ОПТИМИЗАЦИИ Методические указания по выполнению лабораторной работы
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тихоокеанский государственный университет»
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ» (МИИТ)
МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Самарский государственный технический университет» (ФГБОУ ВПО «СамГТУ») Кафедра
Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Уральский государственный лесотехнический университет Кафедра
Лабораторная работа 4 «Электронные таблицы Excel и автоматизация вычислений на ПК» РАЗДЕЛ 4. Решение систем уравнений и оптимизационных задач. Вычислительные возможности программы Excel достаточно широки,
Введение Линейное программирование раздел математики, в котором изучаются теория и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии
ФЕДЕРАЛЬНОЕ АГЕНСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ
АНАЛИЗ УСТОЙЧИВОСТИ КОММЕРЧЕСКОЙ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЯ Дегтярёва Нина Адамовна, к.э.н., доцент Коммерческая работа - это деятельность предприятия, направленная на решение особого комплекса задач. Изучение
ЛАБОРАТОРНАЯ РАБОТА 2 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 1. Цели работы: построение математической модели задачи линейного программирования; решение задачи линейного программирования графическим
