Решение задач линейного программирования в MS Excel

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

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

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

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

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

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

Выполнил:

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

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

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

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

Барнаул 2016

СОДЕРЖАНИЕ

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

Содержание в двух данных наборах азотных удобрений: 3х1 + 2х2

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

3х1 + 2х2 ? 10

Содержание в двух данных наборах фосфорных удобрений должно быть не менее 20 кг, т.е.:

4х1 + 6х2 ? 20

И содержание в двух данных наборах калийных удобрений должно быть не менее 7 кг, т.е.:

1х1 + 3х2 ? 7

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

3х1 + 4х2.

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

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

3х1 + 2х2 ? 10

4х1 + 6х2 ? 20

х1 + 3х2 ? 7

х1 0, х2 0

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

1) 3х1 + 2х2 ? 10

3х1 + 2х2 = 10

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

Возьмем точку О(0;0):

3*0 + 2*0 ? 10

0 ? 10 microsoft excel программирование математический

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

2) 4х1 + 6х2 ? 20

4х1 + 6х2 = 20

4*0 + 6*0 20

0 20

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

3) х1 + 3х2 ? 7

х1 + 3х2 = 7

1*0 + 3*0 7

0 7

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

4) х1 0

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

5) х2 0

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

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

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

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

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

(х) = d1x1 + d2x2

(х) = 3х1 + 4х2

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

d = (3; 4).

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

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

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

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

4х1 + 6х2 = 20

-9х1 - 6х2 = -30

4х1 + 6х2 = 20

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

-5х1 = -10

х1 = 2

В(2; 2)

(х) = 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