7. Задачи математического программирования

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

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

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

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

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

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

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

В данном разделе будет продемонстрировано, как при помощи средства Поиск решения решаются линейные оптимизационные задачи на примере двух типичных задач:

- планирование производства;

- транспортная задача.

Пример 1

Для составления плана выпуска четырёх видов продукции Р₁, Р₂, Р₃ и Р₄ на предприятии используют три вида сырья S₁, S₂ и S₃. Объёмы выделенного сырья, нормы расхода сырья и прибыль, полученная в результате выпуска каждого вида продукции, приведены в таблице. Какое количество продукции всех видов необходимо произвести, чтобы прибыль была максимальной.

Вид Сырья	Вид продукции				Запасы сырья
	Р1	Р2	Р3	Р4
S1	4	2	2	3	35
S2	1	1	2	3	30
S3	3	1	2	1	40
Прибыль	14	10	14	11

Решение

1. Составим экономико-математическую модель задачи.

Обозначим через и объёмы производства соответствующего вида продукции. Целевая функция — это математическая запись критерия оптимальности, т.е. выражение (ожидаемая прибыль), которое необходимо максимизировать

.

Ограничения по ресурсам выглядят следующим образом:

2. Создадим форму для ввода условий задачи.

Запускаем Excel, выбрав Microsoft Excel из подменю Программы главного меню Windows. Открывается чистый лист и мы создаем текстовую форму — таблицу для ввода условий задачи (рис. 1):

		Переменные
	X1	X2	X3	X4
Значение					ЦФ
коэф. В ЦФ
		Ограничения
Вид ресурсов					левая часть	знак	правая часть
S1
S2
S3

Рис. 1

3. Внесём исходные данные в таблицу (рис. 2):

		Переменные
	X1	X2	X3	X4
Значение					ЦФ
коэф. В ЦФ	14	10	14	11
		Ограничения
Вид ресурсов					левая часть	знак	правая часть
S1	4	2	2	3		<=	35
S2	1	1	2	3		<=	30
S3	3	1	2	1		<=	40

Рис.2

3. Укажем адреса ячеек, в которых будет помещён результат решения (изменяемые ячейки). В нашей задаче оптимальные значения компонент вектора , будут помещены в ячейках B3:E3, оптимальное значение функции — в ячейке F4.

4. Вводим зависимость для целевой функции в ячейку F4, используя функцию СУММПРОИЗВ(B$3:E$3,B4:E4) (рис. 3).

5. Вводим зависимость для ограничений в ячейки F7: F9, используя функции СУММПРОИЗВ(B$3:E$3,B7:E7),СУММПРОИЗВ(B$3:E$3,B8:E8),СУММПРОИЗВ(B$3:E$3,B9:E9) (рис. 3).

		Переменные
	X1	X2	X3	X4
Значение					ЦФ
коэф. В ЦФ	14	10	14	11	0
		Ограничения
Вид ресурсов					левая часть	знак	правая часть
S1	4	2	2	3	0	<=	35
S2	1	1	2	3	0	<=	30
S3	3	1	2	1	0	<=	40

Рис. 3

6. Выбрать в строке Меню Сервис>Поиск решения:

• установим целевую ячейку, введя её адрес $F$4;

• вводим направление целевой функции — по Максимальному значению;

• в строку Изменяя ячейки вводим адреса искомых переменных B$3:E$3;

• вводим ограничения в диалоговое окно Добавление ограничения:

а) в строке Ссылка на ячейку вводим адреса $F$7: $F$9;

б) вводим знак ограничения <=;

в) в строке Ограничение вводим адреса $H$7: $H$9;

• после введения последнего ограничения нажимаем кнопку OK.

7. В диалоговом окне Поиск решения установить Параметры поиска решения: Линейная модель и Неотрицательные значения. Нажать кнопку OK.

8. В диалоговом окне Поиск решения нажать на кнопку Выполнить.

9. Через непродолжительное время появится диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками B$3:E$3 для значений и ячейка $F$4 с максимальным значением целевой функции (см. рис.4):

		Переменные
	X1	X2	X3	X4
Значение	0	5	12,5	0	ЦФ
коэф. В ЦФ	14	10	14	11	225
		Ограничения
Вид ресурсов					левая часть	знак	правая часть
S1	4	2	2	3	35	<=	35
S2	1	1	2	3	30	<=	30
S3	3	1	2	1	30	<=	40

Рис. 4

Ответ:

Полученное решение означает, что максимальная прибыль 225 у.е. будет получена предприятием при выпуске и реализации 5 единиц продукции Р₂ и 12,5 единиц продукции Р₃. При этом сырьё S₁ и сырьё S₂ будут израсходованы полностью, а из 40 единиц сырья S₃ будет использовано 30 единиц.

Пример 2

Перед менеджером нефтяной компании «Магнум» стоит задача создания схемы поставки нефтепродуктов от четырёх нефтеперерабатывающих комплексов компании к пяти регионам страны. Одним из основных условий поставленной задачи является минимизация стоимости перевозок, при этом все мощности нефтеперерабатывающих комплексов должны быть реализованы и все потребности регионов должны быть удовлетворены.

Мощности поставщиков и мощности потребителей, а также стоимость перевозок нефтепродуктов представлены в следующей таблице (в условных единицах).

Мощности поставщиков	Мощности потребителей
	600	400	700	500	1000
700	4	8	5	1	6
800	3	5	2	3	4
900	2	6	5	4	3
800	1	4	3	5	3

Экономико-математическая модель

Обозначим через

m — число поставщиков (m=4);

n — число потребителей(n=5);

— величину поставки i-го поставщика j-ому потребителю ;

— тариф перевозки единицы продукции от i-го поставщика j-ому потребителю ;

— мощность (объём выпуска) i-го поставщика ;

— потребности j-ого потребителя ;

— общие затраты грузоперевозок.

Приходим к следующей математической постановке транспортной задачи:

при ограничениях:

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

Замечание

Если условие сбалансированности данных нарушено , то следует поступить следующим образом:

1. если , т.е. когда суммарная мощность поставщиков превышает суммарные нужды потребителей, тогда в систему следует ввести «фиктивного» потребителя с нулевыми транспортными тарифами и потребностью в нефтепродуктах в количестве, равном разности ;

2. если , т.е. когда суммарная мощность потребителей превышает суммарные потребности поставщиков, тогда в систему следует ввести «фиктивного» поставщика с нулевыми транспортными тарифами и мощностью поставок нефтепродуктов в количестве, равном разности .

Решение

Ввод условий задачи состоит из следующих основных этапов.