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

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

Темы контрольной работы «Решение задач линейного программирования в MS Excel», получить практические навыки в использовании электронных таблиц Microsoft Excel и решения оптимизационных задач линейного программирования.

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

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