1 Модель общей задачи линейного программирования

Формируемые навыки и умения:

- освоение методики составления оптимизационной модели; - освоение методики решения модели общей задачи линейного программирования на ЭВМ с использованием пакета Excel; - освоение навыков проведения содержательного послеоптимизационного анализа полученных результатов.

Теоретическая поддержка

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

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

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

Среди линейных моделей математического программирования особое место занимают четыре типа моделей:

1. модель общей задачи линейного программирования;

2. модель транспортной задачи линейного программирования;

3. модель распределительной задачи линейного программирования;

4. модель ассортиментной задачи линейного программирования.

Рассмотрим модель общей задачи линейного программирования.

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

Найти значения n переменных x₁, х₂, ..., х_n (например, количество продаваемого товара), которые удовлетворяют системе ограничений:

f_i (х₁, х₂, …, х_n) {<,=,>} b_i () (1.1)

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

Z = f (х₁, х₂, …, х_n) (max / min). (1.2)

Если на переменные налагается условие неотрицательности, тогда в модель задачи вводится условие

(x_j > 0), (j = ). (1.3)

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

Пример решения задачи

Постановка задачи. Торговое предприятие реализует товары нескольких групп: А, В, С. Для реализации данных товарных групп расходуются следующие ресурсы: рабочее время, площадь торговых залов и издержки обращения. Известны нормативы затрат ресурсов а_ij в расчете на единицу товара по каждой группе и соот­ветственно величины ресурсов b_i. Доход при реализации единицы товара группы А равен 3 ден. ед., товара группы В – 5 ден. ед., товара группы С – 4 ден. ед.

Таблица 1.1 – Исходные данные

Ресурсы	Нормативы затрат ресурсов по продаже товаров (аij)			Ограниченные объемы ресурсов (bi)
	А	В	С
Рабочее время, чел.-час.	0,1	0,2	0,4	1100
Площадь торговых залов, м^2	0,05	0,02	0,02	120
Издержки обращения, ден. ед.	3	1	2	8000
Доход в расчете на еди­ницу товара, ден. ед.	3	5	4
План продажи товаров, ед.	х1 = ?	х2 = ?	х3 = ?

Требуется:

1. составить экономико-математическую модель задачи, пользуясь которой, можно найти план товарооборота по кри­терию максимума дохода f;

2. найти оптимальный план товарооборота и максимальную величину дохода с помощью инструмента Excel Поиск решения;

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

Решение задачи

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

Известно, что величина дохода линейно связана с объемом продажи товаров х₁, х₂ и х₃. В связи с этим целевую функцию можно записать таким образом:

f = (3x₁ + 5х₂ + 4х₃) → max.

Очевидно, что объем продажи товаров не может быть отрицатель­ной величиной. Поэтому x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0.

Учитывая нормы за­трат рабочего времени и то, что общие затраты в целом не должны превышать имеющихся ресурсов, запишем следующее ограничение:

Исходя из торговой площади и общей площади запишем следую­щее ограничение:

Поскольку известны ограничения по издержкам обращения, запи­шем последнее ограничение:

Экономико-математическую формулировку и модель этой за­дачи в компактном виде можно представить таким образом: из существующего множества решений системы линейных ограничений по ресурсам

_,

_,

_,

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0,

найти такие величины объемов продажи товаров x₁, x₂, x₃, ко­торые бы обеспечили максимальную величину дохода в линейной функции цели:

f = (3x₁ + 5х₂ + 4х₃) → max.

2 Решение задачи с помощью инструмента Excel Поиск решения

Алгоритм решения задачи состоит из нескольких этапов:

1. Ввод исходных данных (таблица 1.1)

Таблица 1.1 - Постановка условий задачи

	А	В	С	D	E	F	G
1		Переменные
2	имя	Товар А	Товар В	Товар С
3	значение
4					ЦФ	направление
5	коэффициент в ЦФ	3	5	4		макс
6			Ограничения
7	вид	Товар А	Товар В	Товар С	левая часть	знак	правая часть
8	Рабочее время, чел.-час.	0,1	0,2	0,4		<	1100
9	Площадь торговых залов, м^2	0,05	0,02	0,02		<	120
10	Издержки обращения, ден. ед.	3	1	2		<	8000

2) Ввод зависимости из математической модели

Ввести зависимость для целевой функции:

• курсор в ячейку Е5;

• курсор на кнопку Мастер функций;

• на экране диалоговое окно Мастер функций – шаг 1 из 2;

• курсор в окно Категория на категорию Математические;

• курсор в окно Функции на СУММПРОИЗВ;

• на экране диалоговое окно (рисунок 1.1);

• в массив 1 ввести В$3:D$3;

• в массив 2 ввести B5:D5;

• курсор на кнопку ОК;

• на экране (таблица 1.2) в ячейке Е5 введены значения целевой функции.

Ввести зависимости для левых частей ограничений:

• курсор в ячейку Е5;

• курсор на кнопку Копировать;

• курсор в ячейку Е8;

• курсор на кнопку Вставить;

• скопировать в Е9:Е10;

- на экране (таблица 1.2) в ячейки Е15:Е17 введены функции.

Рисунок 1.1 - Мастер функций

Таблица 1.2 - Ввод зависимостей

	А	В	С	D	E	F	G
1		Переменные
2	имя	Товар А	Товар В	Товар С
3	значение
4					ЦФ	направление
5	коэффициент в ЦБ	3	5	4	=СУММПРОИЗВ (В$3:D$3;B5:D5)	макс
6		Ограничения
7	вид	Товар А	Товар В	Товар С	левая часть	знак	правая часть
8	Рабочее время, чел.-час.	0,1	0,2	0,4	=СУММПРОИЗВ (В$3:D$3;B8:D8)	<	1100
9	Площадь торговых залов, м^2	0,05	0,02	0,02	=СУММПРОИЗВ (В$3:D$3;B9:D9)	<	120
10	Издержки обращения, ден. ед.	3	1	2	=СУММПРОИЗВ (В$3:D$3;B10:D10)	<	8000

3) Решение задачи

Ввести данные в окно поиска решения. Для этого:

• выполнить команду Сервис → Поиск решения;

• на экране диалоговое окно Поиск решения (рисунок 1.2);

• в окне Поиск решения в поле Установить целевую ячейку ввести ссылку $E$5, щелкнув по ячейке с целевой функцией Е5 на рабочем листе;

• в группе Равной установить опцию Максимальному значению;

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

• нажать на кнопку Добавить для ввода ограничений;

• в окне Добавление ограничения в поле Ссылка на ячейку ввести ссылку на ячейку, содержащую формулу левой части текущего ограничения, например $E$8, щелкнув по этой ячейке на рабочем листе. Затем выбрать из раскрывающегося списка в средней части поля нужное ограничение (<=). В правую часть поля ввести значение правой части ограничения (число 1100 или адрес G8 с этим числом). Далее нажать на кнопку Добавить, чтобы ввести следующие ограничения. После добавления всех ограничений нажать на кнопку ОК для возвращения в окно Поиск решения (рисунок 1.2);

Рисунок 1.2 - Диалоговое окно Поиск решения

• если при вводе задачи возникает необходимость в изменении или удалении внесенных ограничений, то надо щелкнуть на кнопку Изменить или Удалить;

• в окне Поиск решения щелкнуть на кнопку Параметры и установить параметры поиска решения (рисунок 1.3), т.е. установить флажок на Линейная модель и нажать на кнопку ОК;

Рисунок 1.3 - Диалоговое окно Параметры поиска решения

• в окне Поиск решения нажать на кнопку Выполнить;

• на экране появится диалоговое окно Результаты поиска решения (рисунок 1.4);

• нажать на кнопку ОК.

Рисунок 1.4 - Диалоговое окно «Результаты поиска решения»

Результат оптимального решения приведен в таблице (таблица 1.3).

Таблица 1.3 - Результаты расчета

	А	В	С		D	E	F	G
1		Переменные
2	имя	Товар А		Товар В	Товар С
3	значение	250		5375	0
4						ЦФ	направление
5	коэффициент в ЦФ	3		5	4	27625	макс
6				Ограничения
7	вид	Товар А		Товар В	Товар С	левая часть	знак	правая часть
8	Рабочее время, чел.-час.	0,1		0,2	0,4	1100	<=	1100
9	Площадь торговых залов, м^2	0,05		0,02	0,02	120	<=	120
10	Издержки обращения, ден. ед.	3		1	2	6125	<=	8000

3 Анализ оптимального решения

Чтобы вызвать отчеты анализа, необходимо в диалоговом окне Результаты поиска решения установить курсор на одном из отчетов и нажать кнопку ОК.

Отчет по результатам (таблица 1.4) состоит из трех таблиц:

• таблица 1 приводит сведения о целевой функции;

• таблица 2 приводит значения искомых переменных, полученные в результате решения задачи;

• таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.

Отчет по пределам (таблица 1.5) показывает, в каких пределах может изменяться объем реализации продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения.

Отчет по устойчивости (таблица 1.6) состоит из двух таблиц:

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

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

Таблица 1.4 - Отчет по результатам

Целевая ячейка (Максимум)
	Ячейка	Имя	Исходно	Результат
	$E$5	Коэффициент в ЦФ	0	27625
Изменяемые ячейки
	Ячейка	Имя	Исходно	Результат
	$B$3	значение Товар А	0	250
	$C$3	значение Товар В	0	5375
	$D$3	значение Товар С	0	0
Ограничения
	Ячейка	Имя	Значение	Формула	Статус	Разница
	$E$8	Рабочее время, чел.-час. левая часть	1100	$E$8<=$G$8	связанное	0
	$E$9	Площадь торговых залов, м^2левая часть	120	$E$9<=$G$9	связанное	0
	$E$10	Издержки обращения, ден. ед. левая часть	6125	$E$10<=$G$10	не связан.	1875
	$B$3	значение Товар А	250	$B$3>=0	не связан.	250
	$C$3	значение Товар В	5375	$C$3>=0	не связан.	5375
	$D$3	значение Товар С	0	$D$3>=0	связанное	0

Таблица 1.5 – Отчет по пределам

	Ячейка	Целевое имя	Значение
	$E$5	коэф.в ЦБ ЦФ	27625
	Ячейка	Изменяемое имя	Значение		Нижний предел	Целевое результат		Верхний предел	Целевое результат
	$B$3	значение Товар А	250		0	26875		250	27625
	$C$3	значение Товар В	5375		0	750		5375	27625
	$D$3	значение Товар С	0		0	27625		0	27625

Таблица 1.6 - Отчет по устойчивости

Изменяемые ячейки
	Ячейка	Имя	Результ. значение	Нормир. стоимость	Целевой коэффициент	Допустимое увеличение	Допустимое уменьшение
	$B$3	значение Товар А	250	0	3	9,5	0,5
	$C$3	значение Товар В	5375	0	5	1	2,555555556
	$D$3	значение Товар С	0	-5,75	4	5,75	1E+30
	Ограничения
	Ячейка	Имя	Результ. значение	Теневая цена	Ограничение Правая часть	Допустимое увеличение	Допустимое уменьшение
	$E$8	Рабочее время, чел.-час. лев.часть	1100	23,75	1100	100	860
	$E$9	Площадь торговых залов, м^2лев.часть	120	12,5	120	30	10
	$E$10	Издержки обращения, ден. ед. лев.часть	6125	0	8000	1E+30	1875

Вывод: Максимальный доход торгового предприятия составит 27625 ден. ед. при следующей структуре товарооборота: товарная группа А – 250 единиц; товарная группа В – 5375 единиц, товарная группа С – 0 единиц.

Если торговое предприятие будет продавать товар группы С, то оно снизит свой доход на 5,75 ден. ед. за единицу проданного товара группы С.

Сохраняется структура оптимального товарооборота, т.е. по-прежнему выгодно продавать товарные группы А и В, если торговое предприятие увеличит цены на товары группы А и группы В соответственно на 9,5 ден. ед. и на 1 ден. ед., или снизит цены на товары группы А и группы В соответственно на 0,5 ден. ед. и на 2,56 ден. ед.

Что касается использования ресурсов, то рабочее время и площадь торговых залов будут использованы полностью, а издержки обращения будут снижены с 8000 ден. ед. до 6125 ден. ед., т.е. экономия издержек обращения составит 1875 ден. ед.

При изменении количества рабочего времени на 1 чел.-час. и площади торговых залов на 1 м² максимальный доход изменится, соответственно, на 23,75 ден. ед. и на 12,5 ден. ед.

Оптимальная структура товарооборота сохраняется при увеличении использования рабочего времени на 100 чел.-час. или его уменьшении на 860 чел.-час., при увеличении торговой площади на 30 м² или ее уменьшении на 10 м².

Задачи для самостоятельного решения

Задача 1. Модель планирования рациональных покупок продуктов питания

Для поддержания нормальной жизнедеятельности человеку ежедневно необходимо потреблять 118 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в 1 кг имеющихся в магазине продуктов питания, а также их стоимость приведены в таблице 1.7.

Таблица 1.7 - Исходные данные

Питательные вещества	Содержание питательных веществ в 1 кг продуктов							Нормы суточной потребности, г
	мясо	рыба	молоко	масло	сыр	крупа	картофель
Белки, г	180	190	30	70	260	130	21	118
Жиры, г	20	3	40	865	310	30	2	56
Углеводы, г	0	0	50	6	2	650	200	500
Минеральные соли, г	9	10	7	12	60	20	70	8
Стоимость 1 кг продукта, у. е.	1,8	1,0	0,28	3,4	2,9	0,5	0,1
Количество продукта в рационе, кг	х1=?	х2=?	х3=?	х4=?	х5=?	х6=?	х7=?

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

Задача 2. Модель рационального распределения материальных ресурсов

На молочном комбинате для производства двух видов сливочного мороженого и двух видов пломбира требуется молоко натуральное, молоко сухое, молоко сухое обезжиренное, масло сливочное, сахар, молоко сгущенное, молоко сгущенное обезжиренное. Используется оборудование для расфасовки и упаковки мороженого. Нормы затрат указанных ресурсов на производство 1 т мороженого приведены в таблице 1.8.

Таблица 1.8 – Исходные данные

Ресурсы (кг)	Норма расхода ресурса на 1 т мороженого				Общее количество ресурсов
	сливочного I вида	сливочного II вида	пломбира I вида	пломбира II вида
Молоко натуральное	550	-	620	-	64100
Молоко сухое	40	30	20	20	4800
Молоко сухое обезжиренное	30	40	30	30	5200
Масло сливочное	86	110	150	52	22360
Сахар	160	92	158	128	26240
Молоко сгущенное	-	-	-	50	800
Молоко сгущенное обезжиренное	-	158	30	50	7910
Производительность оборудования (маш.-час.)	4,5	4,5	4,5	4,5	720
Прибыль от реализации 1 т мороженого, ден. ед.	315	278	573	370	-
Выпуск (т): минимальный максимальный	- -	40 -	- 120	- -	- -

В этой же таблице указана прибыль от реализации 1 т мороженого каждого вида, приведено общее количество ресурсов данного вида, имеющееся в распоряжении молочного комбината, а также указаны минимально возможный выпуск сливочного мороженого II вида и максимально возможный – пломбира I вида (эти границы определены на основе установившегося спроса на мороженое).

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

Задача 3. Модель оптимального составления смесей

Пусть в баре «Эдем» требуется приготовить 1 л алкогольного коктейля, содержащего 15 % рома, 55 % сока и 30 % ликера. Данные об имеющихся в баре алкогольных коктейлях заданы в таблице 1.9.

Таблица 1.9 - Исходные данные

Показатель	Исходные алкогольные коктейли
	1	2	3	4	5
Содержание ликера, % Содержание сока, % Содержание рома, % Стоимость 1 л коктейля, у.е.	40 40 20 5	30 60 10 4	25 45 30 7	15 65 20 5	35 60 5 3

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

Задача 4. Модель планирования оптимального объема рекламного бюджета

Фирма рекламирует свою продукцию с использованием четырех средств массовой информации: телевидения, радио, газет и афиш. Из данных прошлых периодов известно, что эти средства приводят к увеличению прибыли соответственно на 10, 3, 7 и 4 единицы в расчете на 1 единицу затраченных средств.

Распределение рекламного бюджета подчинено следующим ограничениям:

- полный бюджет не должен превосходить 500000 единиц;

- на телевидение следует расходовать не более 40 % бюджета;

- на радио целесообразно расходовать не менее половины той суммы, которая планируется на телевидение.

- на афиши следует расходовать не более 20 % бюджета.

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

Задача 5. Оптимизация деятельности торгового предприятия

Торговое предприятие (предприятие оптовой торгов­ли), исходя из специализации, может реализовать n групп товаров Т_j (j = 1,2, ..., n). Пусть общая площадь торговых залов Р, Р_j — норматив складских площадей на содержание товаров j-й группы; R - фонд рабочего времени ра­ботников, r_j - плановый норматив затрат времени работников на единицу то­варооборота j-й товарной группы. Пусть В - допустимые издержки обраще­ния, b_j - плановый норматив издержек обращения на единицу товарооборота j-й товарной группы. S - общий объем товарных запасов; s_j - норматив то­варных запасов на единицу товарооборота j-й товарной группы. Q - плановый показатель товарооборота; q_j - параметр товарооборота (средняя цена реали­зации) по j-й товарной группе. G_j - минимально допустимые значения плана товарооборота по j-й товарной группе. С_j - торговая прибыль в расчете на единицу товарооборота j-й группы.

Требуется:

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

2) сделать содержательный анализ полученного решения;

3) выявить «узкие места» в работе торгового предприятия и дать рекомен­дации по их «расшивке».

При расчетах используйте данные, приведенные в таблице 1.10.

Таблица 1.10 – Исходные данные по вариантам

	Вариант
	1	2	3	4	5	6	7	8	9	10
С1	120	40	60	50	100	80	130	90	110	70
С2	50	15	25	70	30	40	30	35	50	60
С3	30	10	15	20	80	20	10	20	10	15
С4	100	35	50	80	50	120	80	100	40	60
Р	110000	60000	50000	65000	75000	80000	100000	160000	95000	110000
R	950000	400000	350000	480000	550000	500000	650000	250000	320000	640000
В	120000	600000	720000	850000	800000	850000	1100000	330000	770000	900000
S	180000	90000	110000	150000	180000	180000	220000	96000	160000	220000
Q	150000	300000	510000	500000	450000	420000	710000	320000	350000	330000
Р1	18	9	15	12	13	15	20	10	14	25
P2	28	13	16	20	21	20	27	30	20	32
Р3	16	8	10	10	11	13	18	20	10	23
Р4	10	5	1	12	14	11	12	15	15	15
r1	150	75	100	120	115	110	160	25	35	165
r2	140	70	90	100	95	90	150	70	80	155
r3	50	25	30	40	45	40	50	30	40	65
r4	80	40	60	50	60	55	90	40	50	85
b1	170	85	120	150	140	130	170	58	135	176
b2	230	115	200	190	180	170	200	92	185	205
b3	280	140	220	200	190	185	270	96	190	275
b4	120	60	90	110	100	105	130	55	110	134
S1	31	15	20	18	20	19	33	14	10	35
S2	42	21	35	30	30	32	45	20	30	48
S3	60	15	16	20	15	17	31	10	20	33
S4	20	10	18	12	10	11	22	16	15	24
q1	200	100	160	120	115	117	210	70	75	120
q2	150	75	110	90	85	80	165	80	85	90
q3	170	85	100	130	125	120	180	120	125	60

Продолжение таблицы 1.10

	Вариант
	1	2	3	4	5	6	7	8	9	10
q4	50	25	80	60	50	45	60	50	50	45
G1	1200	600	1000	1100	1050	1000	1000	800	1020	500
G2	1000	500	800	850	800	900	1100	950	850	700
G3	1500	750	1200	1050	1000	750	1400	800	950	450
G4	1200	1100	1300	950	900	1100	1600	1000	800	600