Курсовая работа: Технология решения задач линейного программирования с помощью Поиска решений приложения Excel. Линейное программирование в Excel
Лабораторная работа "Использование средства Поиск решения"
Задание:
Решить в 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. Заполнение листа для решения задачи ... |
Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Задачи линейного программирования является удобной математической моделью для большого числа экономических задач (планирование производства, расходование материалов, транспортные перевозки и т.д.). Использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями.В электронных таблицах Excel с помощью функции поиска решения можно вести поиск значения в целевой ячейке, изменения значения переменных. При этом для каждой переменной можно задать ограничения, например верхнюю границу. Перед тем как запустить поиск решения, необходимо четко сформулировать в модели решаемую проблему, т.е. определить условия, выполняемые при оптимизации. Отправленной точкой при поиске оптимального решения является модель вычисления, созданная в рабочем листе. Программе поиска решения при этом необходимы следующие данные. 1. Целевая ячейка - это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой. 2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно должны влиять на значение целевой ячейки. 3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. Программа предоставляет возможность задать специальные параметры, определяющие процесс поиска решения. После задания всех необходимых параметров можно запустить поиск решения. Функция поиска решения создаст по итогам своей работы три отчета, которые можно пометить в рабочую книгу.Ограничения - это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели.
Изучение литературы показало, что:
1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».
Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:
- · рационального использования сырья и материалов; задачи оптимизации раскроя;
- · оптимизации производственной программы предприятий;
- · оптимального размещения и концентрации производства;
- · составления оптимального плана перевозок, работы транспорта;
- · управления производственными запасами;
- · и многие другие, принадлежащие сфере оптимального планирования.
- 2. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.
Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
Рассмотрим линейное программирование в Excel на примере задачи, ранее решенной .
Задача. Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно. Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд. На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц. Необходимо определить количество единиц продуктов А и В, которые Николай доложен производить в следующем месяце для максимизации маржинальной прибыли.
Скачать заметку в формате , пример в формате
1. Воспользуемся математической моделью построенной . Вот эта модель:
Максимизировать: Z = 2500 * х 1 + 3500 *х 2
При условии, что: 3 * х 1 + 10 * х 2 ≤ 330
16 * х 1 + 4 * х 2 ≤ 400
6 * х 1 + 6 * х 2 ≤ 240
2. Создадим экранную форму и введем в нее исходные данные (рис. 1).
Рис. 1. Экранная форма для ввода данных задачи линейного программирования
Обратите внимание на формулу в ячейке С7. Это формула целевой функции. Аналогично, в ячейки С16:С18 введены формулы для расчета левой части ограничений.
3. Проверьте, если у вас установлена надстройка «Поиск решения» (рис. 2), пропустите этот пункт.
Рис. 2. Надстройка Поиск решения установлена; вкладка «Данные», группа «Анализ»
Если надстройки «Поиск решения» вы на ленте Excel не обнаружили, щелкните на кнопку Microsoft Office, а затем Параметры Excel (рис. 3).
Рис. 3. Параметры Excel
Выберите строку Надстройки, а затем в самом низу окна «Управление надстройками Microsoft Excel» выберите «Перейти» (рис. 4).
Рис. 4. Надстройки Excel
В окне «Надстройки» установите флажок «Поиск решения» и нажмите Ok (рис. 5). (Если «Поиск решения» отсутствует в списке поля «Надстройки», чтобы найти надстройку, нажмите кнопку Обзор. В случае появления сообщения о том, что надстройка для поиска решения не установлена на компьютере, нажмите кнопку Да, чтобы установить ее.)
Рис. 5. Активация надстройки «Поиск решения»
После загрузки надстройки для поиска решения в группе Анализ на вкладке Данные становится доступна команда Поиск решения (рис. 2).
4. Следующим этапом заполняем окно Excel «Поиск решения» (рис. 6)
Рис. 6. Заполнение окна «Поиск решения»
В поле «Установить целевую ячейку» выбираем ячейку со значением целевой функции – $C$7. Выбираем, максимизировать или минимизировать целевую функцию. В поле «Изменяя ячейки» выбираем ячейки со значениями искомых переменных $C$4:$D$4 (пока в них нули или пусто). В области «Ограничения» с помощью кнопки «Добавить» размещаем все ограничения нашей модели. Жмем «Выполнить». В появившемся окне «Результат поиска решения» выбираем все три типа отчета (рис. 7) и жмем Ok. Эти отчеты нужны для анализа полученного решения. Подробнее о данных, представленных в отчетах, можно почитать .
Рис. 7. Выбор типов отчета
На основном листе появились значения максимизированной целевой функции – 130 000 руб. и изменяемых параметров х 1 = 10 и х 2 = 30. Таким образом, для максимизации маржинального дохода Николаю в следующем месяце следует произвести 10 единиц продукта А и 30 единиц продукта В.
Если вместо окна «Результат поиска решения» появилось что-то иное, Excel`ю найти решение не удалось. Проверьте правильность заполнения окна «Поиск решения». И еще одна маленькая хитрость. Попробуйте уменьшить точность поиска решения. Для этого в окне «Поиск решения» щелкните на Параметры (рис. 8.) и увеличьте погрешность вычисления, например, до 0,001. Иногда из-за высокой точности Excel не успевает за 100 итераций найти решение. Подробнее о параметрах поиска решения можно почитать .
Рис. 8. Увеличение погрешности вычислений
Для решения задач линейного программирования симплекс-методом в среде MS Excel заполняются ячейки исходными данными в режиме чисел и формулами математической модели.
MS Excel позволяет получить оптимальное решение без ограничения размерности системы неравенств целевой функции.
Решим задачу о выпускаемых изделиях симплекс-методом применяя надстройку «Поиск решения» в MS Excel.
1. Заполните таблицу Excel в режиме чисел (рис.1)
2. Заполните таблицу Excel в режиме формул (рис.2)
Рис.1 Таблица в режиме чисел
Рис.1 Таблица в режиме формул
Здесь: В9:С9 – результат (оптимальное количество изделий каждого вида);
В6:С6 – коэффициенты целевой функции;
В10 – значение целевой функции;
В3:С5 – коэффициенты ограничений;
D12:D14 – правая часть ограничений;
B12:B14 – вычисляемые (фактические) значения левой части ограничений.
Решим задачу с помощью команды Данные/Поиск решения. На экране появляется диалоговое окно Поиск решения.
В поле Установить целевую функция будет показана ссылка на активную ячейку, т.е. на В10. Причем эта ссылка абсолютная. В секции Равной устанавливаем переключатель Максимальному (минимальному) значению в зависимости от целевой функции. Ограничения устанавливаются с помощью кнопки Добавить, которая вызывает диалоговое окно их ввода Добавление ограничения.
В поле ввода Ссылка на ячейку: указывается адрес ячейки, содержащей формулу левой части ограничения. Затем выбирается из списка знак соотношения. В поле Ограничение указывается адрес ячейки, содержащей правую часть ограничения. Щёлкаем на кнопку Добавить и повторяем до следующего ограничения. После ввода всех ограничений нажимаем ОК.
Так как все переменные несут условия неотрицательности, то их положительность задается через кнопку Параметры в окне диалога Поиск решения. После щелчка по ней, на экране окно Параметры поиска решения.
Устанавливаем флажок Сделать переменные без ограничений неотрицательными и выбрать Метод решения Поиск решения линеных задач симплекс-методом. Щёлкаем на кнопке Найти решение.
Excel предъявит окно Результаты поиска решения с сообщением о том, что решение найдено, или о том, что не может найти подходящего решения.
Если вычисления оказались успешными, Excel предъявит следующее окно итогов. Их можно сохранить или отказаться. Кроме того, можно получить один из трёх видов отчётов (Результаты, Устойчивость, Пределы), позволяющие лучше осознать полученные результаты, в том числе, оценить их достоверность.
После найденного решения, в ячейках В9:С9 появится оптимальное количество изделий каждого вида.
При сохранении отчета выберите – Отчет по результатам (рис.3).
Из отчета видно, что ресурс 1 не используется полностью на 150 кг, а ресурс 2 и 3 используется полностью.
В результате получен оптимальный план, при котором изделий 1 вида необходимо выпустить в количестве 58 шт., а изделий 2 вида в количестве 42 шт. При этом прибыль от их реализации максимальная и составляет 4660 тыс.руб.
Рис.3 Отчет по результатам
1. Со станции формирования ежедневно отправляются пассажирские и скорые поезда, составленные из плацкартных, купейных и мягких вагонов. Число мест в плацкартном вагоне – 54, в купейном – 36, в мягком – 18. В таблице указаны состав поезда каждого типа и количество имеющихся в парке вагонов различного типа. Определить число скорых и пассажирских поездов, которые необходимо формировать ежедневно, чтобы число перевозимых пассажиров было максимальным.
Решение транспортных задач
Транспортными задачами называются задачи определения оптимального плана перевозок груза из данных пунктов отправления в заданные пункты потребления.
| b 1 | b 2 | … | b k | … | b g | |
| a 1 | } Загрузка...Возможно вам будет интересно:
Последние статьи
|
