Решение задач линейного программирования в Excel - Реферат. Курсовая работа: Технология решения задач линейного программирования с помощью Поиска решений приложения Excel

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Частное образовательное учреждение высшего образования «Санкт-Петербургский университет технологий управления и экономики»

Кафедра экономики и менеджмента

КОНТРОЛЬНАЯ РАБОТА

По дисциплине: МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Выполнил:

Студент (ка) 3 курса, группа № 19731Д/3-2

Крюк Альбина Владимировна

Руководитель:

к.э.н., доцент Ж.М. Козлова.

Барнаул 2016

• Введение
• Заключение
• ВВЕДЕНИЕ
• Решение широкого круга задач электроэнергетики и других отраслей народного хозяйства основывается на оптимизации сложной совокупности зависимостей, описанных математически с помощью некоторой «целевой функции» (ЦФ). Подобные функции можно записать для определения затрат на топливо для электростанций, на потери электроэнергии при транспорте ее от электростанции к потребителям и многие другие проблемные задачи. В таких случаях требуется найти ЦФ при определенных ограничениях, накладываемых на ее переменные. Если ЦФ линейно зависит от входящих в ее состав переменных и все ограничения образуют линейную систему уравнений и неравенств, то такая частная форма оптимизационной задачи получила название «задачи линейного программирования».
• Темы контрольной работы «Решение задач линейного программирования в MS Excel», получить практические навыки в использовании электронных таблиц Microsoft Excel и решения оптимизационных задач линейного программирования.

1. Типовые задачи оптимизации и их экономико-математические модели

Экономико-математическое моделирование представляет собой процесс выражения экономических явлений математическими мо­делями. Экономическая модель -- это схематичное представление экономического явления или процесса с использованием научной абстракции, отражение их характерных черт. Математические мо­дели -- основное средство решения задач оптимизации любой дея­тельности. По своей сути эти модели -- средство плановых расче­тов. Ценность их для экономического анализа и оптимизации реше­ний состоит в том, что они позволяют оценить напряженность плановых заданий, определить лимитирующую группу оборудова­ния, видов ресурсов, получать оценки их дефицитности и т.п. Мате­матическое моделирование экономических явлений и процессов дает возможность получить четкое представление об исследуемом объекте, охарактеризовать и количественно описать его внутреннюю струк­туру и внешние связи. Модель -- условный образ объекта управле­ния /1/.

Экономико-математическая модель должна быть адекватной действительности, отражать существенные стороны и связи изучаемо­го объекта. Отметим принципиальные черты, характерные для по­строения экономико-математической модели любого вида. Процесс моделирования можно условно подразделить на три этапа:

1) ана­лиз теоретических закономерностей, свойственных изучаемому яв­лению или процессу и эмпирических данных о его структуре и особенностях; на основе такого анализа формируются модели;

2) определение методов, с помощью которых можно решить задачу;

3) анализ полученных результатов.

Важнейшим моментом первого этапа моделирования является четкая формулировка конечной цели построения модели, а также определение критерия, по которому будут сравниваться различные варианты решения. Такими критериями в системе менеджмента могут быть:

а) максимизация полезного эффекта товара при ограни­чении совокупности затрат;

б) максимизация прибыли фирмы при условии, что качество товара не снизится; в) снижение себестоимо­сти товара при условии, что его качество не снизится, затраты у потребителя не увеличатся;

г) рост производительности труда, улуч­шение использования оборудования или материалов, повышение оборачиваемости оборотных средств при условии, что качество то­вара не снизится и другие критерии не ухудшатся.

Таким образом, в качестве критерия оптимизации может быть целое или любой компонент прибыли, эффективности товара, объема рынка при ус­ловии, что другие компоненты при этом не ухудшатся.

Например, уравнение целевой функции (L) и система ограниче­ний по оптимизации прибыли фирмы (правда, у авторов нет огра­ничений по качеству товара) будет иметь следующий вид:

где хj -- количество производимой продукции j-го вида в нату­ральных измерениях;

Пj -- прибыль, получаемая от производства единицы про­дукции j-го вида;

аij -- норма расхода i-го производственного ресурса на про­изводство единицы j-го вида продукции;

щj -- запасы i-го вида производственного ресурса на рас­сматриваемый период времени.

Не для всякой экономической задачи нужна собственная модель. Некоторые процессы с математической точки зрения однотипны и могут описываться одинаковыми моделями. Например, в линейном программировании, теории массового обслуживания и других су­ществуют типовые модели, к которым приводится множество конк­ретных задач.

Вторым этапом моделирования экономических процессов являет­ся выбор наиболее рационального математического метода для реше­ния задачи. Например, для решения задач линейного программиро­вания известно много методов: симплексный, потенциалов и др. Луч­шей моделью является не самая сложная и самая похожая на реальное явление, а та, которая позволяет получить самое рациональное реше­ние и наиболее точные экономические оценки. Излишняя детализа­ция затрудняет построение модели, а излишнее укрупнение модели приводит к потере существенной экономической информации, к не­адекватному отражению реальности.

Третьим этапом моделирования является всесторонний анализ результата, полученного при изучении экономического явления. Окончательным критерием достоверности и качества модели явля­ются практика, соответствие полученных результатов и выводов реальным условиям, экономическая содержательность полученных оценок. Если результаты не соответствуют реальным условиям, то необходим анализ причин несоответствия, в качестве которых могут быть недостоверность информации, несоответствие модели эконо­мическим условиям и др. По результатам анализа причин несоответствия экономико-математическая модель корректируется и ре­шение задачи повторяется.

Решим графическим методом типовую задачу оптимизации

Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 кг азотных, 4 кг фосфорных и 1 кг калийных удобрений, а в улучшенный - 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений. Обычный набор стоит 3 ден. Ед., а улучшенный - 4 ден. Ед. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум, и почему?

Сформулируем прямую оптимизационную задачу.

Пусть х1 - количество обычных наборов удобрений;

х2 - количество улучшенных наборов удобрений.

А для некоторого газона требуется по крайней мере 10 кг азотных удобрений, следовательно:

3х1 + 2х2 ? 10

4х1 + 6х2 ? 20

Стоимость необходимых наборов удобрений составит:

Таким образом, получим следующую экономико-математическую модель задачи:

min (х) = 3х1 + 4х2

3х1 + 2х2 ? 10

4х1 + 6х2 ? 20

Построим область решений системы ограничений. Для этого рассмотрим равенства и построим их графики - прямые.

1) 3х1 + 2х2 ? 10

3х1 + 2х2 = 10

3) х1 + 3х2 ? 7

Неравенство не выполняется, значит, исходному неравенству соответствует полуплоскость, не содержащая точку О(0;0).

х1 = 0 - ось ОХ2.

х2 = 0 - ось ОХ1.

Следовательно, область решений системы ограничений находится только в первой четверти декартовой системы координат.

Рис.1. Графическое решение ЗЛП

Находим общую часть всех построенных полуплоскостей. Это выпуклая заштрихованная область.

Для нахождения оптимального решения задачи изобразим графически функцию цели:

(х) = d1x1 + d2x2

(х) = 3х1 + 4х2

Для этого строим вектор d, начало которого в точке (0;0), а конец в точке (d1;d2).

И строим одну из линий уровня функции цели (это линия, на которой функция цели принимает постоянное значение).

Для определения минимума данной функции, передвигаем линию уровня в направлении, противоположном вектору d, и видим, что она последний раз соприкасается с областью решений в точке В, где и будет достигнут min(х).

Определим координаты точки В:

3х1 + 2х2 = 10 *(-3)

4х1 + 6х2 = 20

9х1 - 6х2 = -30

4х1 + 6х2 = 20

Складываем почленно уравнения и получаем:

(х) = 3*2 + 4*2 = 14 (ден. ед.)

Таким образом, чтобы минимизировать стоимость удобрений, нужно купить 2 обычных набора удобрений и 2 улучшенных набора удобрений. При этом минимальные затраты на покупку удобрений составят 14 денежных единиц. microsoft excel программирование математический

Если решать данную задачу на максимум, то конечного оптимума не найдем, т.к. функция цели неограниченна, область решений системы ограничений бесконечна.

2. Задачи линейного программирования, решение средствами MS Excel

Линейное программирование является разделом, с которого начала развиваться дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и других задач. Термин «линейное программирование» возник в результате неточного перевода английского «linear programming». Одно из значений слова «programming» - составление планов, планирование. Следовательно, правильным переводом «linear programming» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Задачи линейного программирования является удобной математической моделью для большого числа экономических задач (планирование производства, расходование материалов, транспортные перевозки и т.д.). Использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями.
В электронных таблицах Excel с помощью функции поиска решения можно вести поиск значения в целевой ячейке, изменения значения переменных. При этом для каждой переменной можно задать ограничения, например верхнюю границу. Перед тем как запустить поиск решения, необходимо четко сформулировать в модели решаемую проблему, т.е. определить условия, выполняемые при оптимизации. Отправленной точкой при поиске оптимального решения является модель вычисления, созданная в рабочем листе. Программе поиска решения при этом необходимы следующие данные. 1. Целевая ячейка - это ячейка в модели вычисления, значения в которой должно быть максимизировано, минимизировано или же равняться определенному указанному значению. Она должна содержать формулу, которая прямо или косвенно ссылается на изменяемые ячейки, или же самой быть изменяемой. 2. Значения в изменяемых ячейках будут последовательно (методом итераций) изменяться до тех пор, пока не будет получено нужное значение в целевой ячейке. Эти ячейки, следовательно, прямо или косвенно должны влиять на значение целевой ячейки. 3. Вы можете задать как для целевой, так и для изменяемых ячеек, ограничения и граничные условия. Можно задать также ограничения для других ячеек. Прямо или косвенно присутствующих в модели. Программа предоставляет возможность задать специальные параметры, определяющие процесс поиска решения. После задания всех необходимых параметров можно запустить поиск решения. Функция поиска решения создаст по итогам своей работы три отчета, которые можно пометить в рабочую книгу.Ограничения - это условия, которые должны быть выполнены аппаратом поиска решения при оптимизации модели.

Изучение литературы показало, что:

1. Линейное программирование - это один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование».

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

· рационального использования сырья и материалов; задачи оптимизации раскроя;

· оптимизации производственной программы предприятий;

· оптимального размещения и концентрации производства;

· составления оптимального плана перевозок, работы транспорта;

· управления производственными запасами;

· и многие другие, принадлежащие сфере оптимального планирования.

2. Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

ЗАКЛЮЧЕНИЕ

С помощью правильной постановки задачи планирования производства и наличия основных производственных параметров, мы можем найти план выпуска продукции, при котором будет достигнута максимальная прибыль.

Благодаря программному продукту Excel, который входит в пакет MS Office, решение наших задач ускоряется в несколько десятков раз. А благодаря точным математическим расчетам данного ПО, мы можем без сомнения найти самые точные результаты исследований.

Размещено на Allbest.ru

Подобные документы

Краткие сведения об электронных таблицах MS Excel. Решение задачи линейного программирования. Решение с помощью средств Microsoft Excel экономической оптимизационной задачи, на примере "транспортной задачи". Особенности оформления документа MS Word.

курсовая работа , добавлен 27.08.2012


История развития и функции линейного программирования. Исследование условий типовых задач и возможностей табличного процессора. Решение задач о рационе питания, плане производства, раскрое материалов и рациональной перевозке груза в среде MS Excel.

курсовая работа , добавлен 28.04.2014


Принципы решения задач линейного программирования в среде электронных таблиц Excel, в среде пакета Mathcad. Порядок решения задачи о назначении в среде электронных таблиц Excel. Анализ экономических данных с помощью диаграмм Парето, оценка результатов.

лабораторная работа , добавлен 26.10.2013


Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.

курсовая работа , добавлен 21.03.2012


Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.

курсовая работа , добавлен 10.06.2014


Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.

дипломная работа , добавлен 20.11.2010


Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".

курсовая работа , добавлен 29.05.2015


Разработка таблиц в Excel методами линейного программирования с целью оптимизации расходов ресурсов и запасов на изготовление продукции: определение переменных величин, структуры целевой функции, построение математической модели и блок-схем решения задач.

курсовая работа , добавлен 07.06.2010


Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.

курсовая работа , добавлен 13.03.2015


Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.

Для решения задач линейного программирования симплекс-методом в среде 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. В таблице указаны состав поезда каждого типа и количество имеющихся в парке вагонов различного типа. Определить число скорых и пассажирских поездов, которые необходимо формировать ежедневно, чтобы число перевозимых пассажиров было максимальным.

Решение транспортных задач

Транспортными задачами называются задачи определения оптимального плана перевозок груза из данных пунктов отправления в заданные пункты потребления.