Практическое занятие №4

Наименование занятия: Решение задачи об оптимальном использовании ограниченных ресурсов

Цель занятия: Научиться решать задачи линейного программирования с учетом стоимости ресурсов.

Подготовка к занятию: Повторить теоретический материал по теме «Линейное программирование».

Литература:

1. Лобачева М.Е. Конспект лекций «Математические методы», 2013г.

2. Агальцов В.П. Математические методы в программировании, 2010г.

Перечень необходимых приборов, инструментов, материалов:ПЭВМ

Задание на занятие:

1. Графически и аналитически решить задачу максимизации целевой функции Z. Найти оптимальное решение с учетом стоимости ресурсов. Исходные данные для каждого варианта приведены в таблице. Символами с₁, с₂и с₃обозначены стоимости соответственно первого, второго и третьего ресурсовb₁,b₂иb₃.

2. Решить задачу, используя приложение MSExcel.

3. По полученным результатам сделать выводы.

Вариант	Целевая функция	Ограничения	Стоимость ресурсов
1	Z=2,4х1+2х2	2х1+5х2≤ 35 6х1+х2≤ 33 6х1+5х2≤ 45 х1≥ 0, х2≥ 0	c1 = 7,2 c2 = 5,5 c3 = 8
2	Z=1,8х1+х2	х1≥ 0, х2≥ 0 5х1+11х2≤ 99 4х1+х2≤ 34 9х1+5х2≤ 82	c1 = 2,5 c2 = 24 c3 = 8,7
3	Z=6х1+8х2	х1≥ 0, х2≥ 0 3х1+8х2≤ 80 14х1+5х2≤ 119 3х1+4х2≤ 46	c1 = 19 c2 = 7 c3 = 6,1
4	Z=0,8х1+х2	х1≥ 0, х2≥ 0 х1+3х2≤ 19,5 4х1+х2≤ 20 4х1+5х2≤ 36	c1 = 17 c2 = 6,2 c3 = 5
5	Z=9х1+13,5х2	х1≥ 0, х2≥ 0 х1+7х2≤ 52,5 2х1+х2≤ 20 2х1+3х2≤ 28	c1 = 12 c2 = 10,4 c3 = 3
6	Z=36х1+30х2	х1≥ 0, х2≥ 0 5х1+9х2≤ 51 2х1+х2≤ 12 6х1+5х2≤ 38	c1 = 3 c2 = 28,5 c3 = 11
7	Z=6х1+9х2	х1≥ 0, х2≥ 0 2х1+9х2≤ 68 7х1+2х2≤ 48,5 2х1+3х2≤ 26	c1 = 7,5 c2 = 4 c3 = 5,8
8	Z=13,4х1+6,7х2	х1≥ 0, х2≥ 0 2х1+3х2≤ 27 8х1+х2≤ 59 2х1+х2≤ 17	c1 = 22 c2 = 14,5 c3 = 10,2
9	Z=2х1+6х2	х1≥ 0, х2≥ 0 х1+9х2≤ 71 13х1+6х2≤ 123,5 х1+3х2≤ 26	c1 = 8,8 c2 = 9,5 c3 = 6
10	Z=1,6х1+2х2	х1≥ 0, х2≥ 0 6х1+13х2≤ 91 3х1+х2≤ 29 4х1+5х2≤ 46	c1 = 9,5 c2 = 20 c3 = 12

Порядок проведения занятия:

1. Получить допуск к работе.

2. Выполнить задание в соответствии со своим вариантом.

3. Ответить на контрольные вопросы.

Содержание отчета:

1. Наименование, цель работы, задание;

2. Выполненное задание;

3. Выводы по результатам выполненного задания;

4. Ответы на контрольные вопросы.

Контрольные вопросы для зачета:

1. В чем особенность решения задач с учетом стоимости ресурсов?

ПРИЛОЖЕНИЕ

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

Пусть в качестве исходных данных дана таблица:

ЦФ	Ограничения	Стоимость ресурсов
Z=1,8х1+х2	х1≥ 0, х2≥ 0 х1+7х2≤ 49 4х1+х2≤ 26 9х1+5х2≤ 64	c1 = 11 c2 = 60 c3 = 22

Символами с₁, с₂и с₃обозначены стоимости соответственно первого, второго и третьего ресурсовb₁,b₂иb₃. Требуется максимизировать ЦФ.

Область допустимых решений показана на рисунке. Из рисунка видно, что график ЦФ параллелен графику ограничения 9х₁+5х₂≤ 64, обозначенному цифрой 3. В этом случае решением задачи без учета экономии ресурсов является любая точка отрезкаAB. На отрезкеABцелевая функция максимальна:Z=12,8. Однако необходимо узнать, в какой точке отрезкаABдостигается максимальная экономия ресурсов с учетом их стоимости (максимальная экономия денежных средств).

Так как все функции линейны, оптимальное решение может находиться только на концах отрезка AB. Определим экономию ресурсов в точкахAиB.

Подставим координаты точки Aв каждое ограничение (кроме условий неотрицательности).

Определим расход ресурса b₁:

b₁=х₁+7х₂=3,5+7·6,5=49 единиц. Экономии этого ресурса в точкеAнет.

Найдем расход ресурса b₂:

b₂=4х₁+х₂=4·3,5+6,5=20,5 единиц. Экономия составляет 26-20,5=5,5 единиц.

Оценим расход ресурса b₃:

b₃=9х₁+5х₂=9·3,5+5·6,5=64 единицы. Экономии ресурса нет.

Подсчитаем теперь расход ресурсов b₁,b₂иb₃в точкеB.

b₁=х₁+7х₂=6+7·2=20 единиц. Экономия составляет 49-20=29 единиц.

b₂=4х₁+х₂=4·6+2=26 единиц. Экономии ресурса нет.

b₃=9х₁+5х₂=9·6+5·2=64 единицы. Экономии ресурса нет.

Как мы видим, в точке Aможно сэкономить 5,5 единиц ресурсаb₂. Его стоимостьc₂согласно условию задачи равна:c₂= 60. Следовательно, экономия составит 5,5·60=330 ден.ед.

В точке Bможно сэкономить 29 единиц ресурсаb₁. Его стоимостьc₁равна:c₁= 11. Экономия составит 29·11=319 ден.ед.

В точке Aэкономия больше.

ВЫВОД: расход на ресурсы минимален при х₁=3,5 и х₂=6,5. В этой точке можно сэкономить 330 ден.ед. При этом целевая функцияZ=12,8.

Пример решения задачи с помощью приложения MS Excel.

Решение производится в два этапа. Сначала найдем максимальное значение ЦФ, а после этого – точку оптимума с учетом максимальной экономии денежных средств.

Составим таблицу:

Окно Поиск решениязаполним следующим образом:

В результате выполнения этой операции MSExcelнайдет максимальное значениеZ(Z=12,8), а также координаты х₁и х₂точки, принадлежащей отрезкуAB. Как было отмечено выше, приложениеMSExcelне учитывает экономию ресурсов при поиске решений.

После этого дополним нашу таблицу строкой «Расход денежных средств»:

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

Примечание. Перед выполнением следующей операции желательно «сбросить» значения х₁и х₂(например, записать нули) в ячейкахB1 иB2.

Теперь в окне Поиск решенияв качестве ЦФ укажем расход денежных средств, установим переключательРавнойв положениеминимальному значениюи добавим еще одно ограничение: целевая функцияZравна 12,8. Окно будет выглядеть следующим образом:

Найденные координаты точки оптимума, как видим, совпадают с аналитическими расчетами: