Методические указания к заданию 1.1

Введение

Методы линейного программирования – необходимый инструмент современного инженера, экономиста, программиста.

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

Нередко на практике встречаются задачи оптимальных перевозок товаров от предприятий-производителей к предприятиям-потребителям (транспортные задачи).

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

В процессе выполнения заданий студенты осваивают графический и аналитический способы планирования производства. Кроме того, они получают навыки работы с математическими пакетами MATLAB, Mathcad и электронными таблицами MS Excel.

При проведении лабораторных работ преподаватели могут по своему усмотрению делать акцент на любой математической системе или на электронных таблицах.

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

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

Линейное программирование

 

Подготовка к работе

По указанной литературе и Приложению изучить основные понятия математического программирования (МП), ознакомиться с методами решения задач линейного программирования (ЛПР), математическими системами Mathcad, MATLAB и приложением MS Excel. Ответить на контрольные вопросы.

 

2. Контрольные вопросы

2.1. Сформулируйте в общем виде задачу математического программирования.

2.2. Чем отличаются задачи линейного программирования и задачи нелинейного программирования?

2.3. Приведите примеры целевых функций.

2.4. Какова наибольшая размерность задачи ЛПР, которую можно решить графически?

2.5. С помощью каких математических систем можно решать задачи ЛПР?

2.6. Как перейти от задачи минимизации целевой функции к задаче её максимизации?

2.7. Перечислите основные этапы решения задачи ЛПР графическим способом.

2.8. Каков порядок решения задач ЛПР с помощью электронных таблиц MS Excel?

2.9. Каковы недостатки решения задач ЛПР при помощи MS Excel?

2.10. Как построить двухмерные и трехмерные графики с помощью математической системы Mathcad?

2.11. Что такое область допустимых решений?

2.12. Сколько точек соприкосновения может иметь график ЦФ с полигоном допустимых решений при оптимальном решении задачи ЛПР?

2.13. Перечислите методы решения задач ЛПР.

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

2.15. Перечислите сферы использования теории математического программирования.

2.16. Почему задачи линейного программирования порой называют оптимизационными задачами?

2.17. Опишите порядок решения задач ЛПР с помощью симплекс-метода.

 

Задания на выполнение лабораторной работы

 

3.1. Задание 1

1.1. Графически и аналитически решить задачу максимизации целевой функции Z. Исходные данные необходимо выбрать из таблицы 1 в соответствии со своим вариантом.

Таблица 1

Вар.	ЦФ	Ограничения	Вар.	ЦФ	Ограничения
	Z=4х1+4,5х2	х1 ≥ 0, х2 ≥ 0 3х1+2х2 ≤ 15 х1+2х2 ≤ 9		Z=х1+х2	х1 ≥ 0, х2 ≥ 0 4х1+13х2 ≤ 84,5 3х1+х2 ≤ 24
	Z=3х1+5х2	х1 ≥ 0, х2 ≥ 0 3х1+8х2 ≤ 40 7х1+4х2 ≤ 42		Z=3х1+1,5х2	х1 ≥ 0, х2 ≥ 0 3х1+4х2 ≤ 14 8х1+х2 ≤ 18
	Z=2х1+2х2	х1 ≥ 0, х2 ≥ 0 х1+3х2 ≤ 12 7х1+х2 ≤ 34		Z=3х1+4х2	х1 ≥ 0, х2 ≥ 0 х1+3х2 ≤ 13,5 8х1+3х2 ≤ 24
	Z=4х1+3х2	х1 ≥ 0, х2 ≥ 0 4х1+9х2 ≤ 54 4х1+х2 ≤ 22		Z=5х1+6х2	х1 ≥ 0, х2 ≥ 0 х1+2х2 ≤ 13 6х1+х2 ≤ 34
	Z=5х1+3х2	х1 ≥ 0, х2 ≥ 0 5х1+4х2 ≤ 28 4х1+х2 ≤ 18		Z=1,5х1+х2	х1 ≥ 0, х2 ≥ 0 х1+5х2 ≤ 12,5 8х1+3х2 ≤ 26
	Z=х1+х2	х1 ≥ 0, х2 ≥ 0 х1+6х2 ≤ 36 11х1+3х2 ≤ 49,5		Z=5х1+2х2	х1 ≥ 0, х2 ≥ 0 5х1+3х2 ≤ 10,5 4х1+х2 ≤ 7
	Z=2,8х1+5х2	х1 ≥ 0, х2 ≥ 0 х1+4х2 ≤ 16 х1+х2 ≤ 7		Z=4х1+5,7х2	х1 ≥ 0, х2 ≥ 0 2х1+7х2 ≤ 40 х1+х2 ≤ 7,5
	Z=1,5х1+1,5х2	х1 ≥ 0, х2 ≥ 0 5х1+6х2 ≤ 27 4х1+3х2 ≤ 18		Z=х1+х2	х1 ≥ 0, х2 ≥ 0 3х1+5х2 ≤ 20 5х1+2х2 ≤ 17,5

 

1.2. Выполнить предыдущий пункт, используя приложение MS Excel. Сравнить полученные в пунктах 1.1 и 1.2 результаты, сделать выводы.

 

Задание 2

2.1. Графически и аналитически решить задачу максимизации целевой функции Z согласно варианту. Исходные данные приведены в таблице 2.

Таблица 2

Вар.	ЦФ	Ограничения	Вар.	ЦФ	Ограничения
	Z=6х1+2х2	х1 ≥ 0, х2 ≥ 0 х1+10х2 ≤ 35 3х1+х2 ≤ 18		Z=4х1+1,5х2	х1 ≥ 0, х2 ≥ 0 4х1+5х2 ≤ 30 8х1+3х2 ≤ 32
	Z=0,6х1+х2	х1 ≥ 0, х2 ≥ 0 3х1+5х2 ≤ 25 7х1+х2 ≤ 21		Z=х1+1,6х2	х1 ≥ 0, х2 ≥ 0 5х1+8х2 ≤ 52 5х1+2х2 ≤ 28
	Z=2,5х1+х2	х1 ≥ 0, х2 ≥ 0 х1+3х2 ≤ 10,5 5х1+2х2 ≤ 33		Z=7,4х1+3,7х2	х1 ≥ 0, х2 ≥ 0 2х1+3х2 ≤ 9 2х1+х2 ≤ 7
	Z=18х1+14х2	х1 ≥ 0, х2 ≥ 0 9х1+7х2 ≤ 49 3х1+х2 ≤ 13		Z=1,5х1+6х2	х1 ≥ 0, х2 ≥ 0 х1+4х2 ≤ 18 8х1+5х2 ≤ 36
	Z=6х1+2х2	х1 ≥ 0, х2 ≥ 0 5х1+6х2 ≤ 33 3х1+х2 ≤ 12		Z=х1+0,8х2	х1 ≥ 0, х2 ≥ 0 4х1+9х2 ≤ 40,5 5х1+4х2 ≤ 32,5
	Z=0,5х1+2х2	х1 ≥ 0, х2 ≥ 0 х1+4х2 ≤ 12 6х1+7х2 ≤ 38		Z=5х1+15х2	х1≥ 0, х2≥ 0 х1+3х2 ≤ 10,5 8х1+3х2 ≤ 42
	Z=6х1+2х2	х1≥ 0, х2≥ 0 х1+9х2 ≤ 56,5 3х1+х2 ≤ 13,5		Z=2х1+0,4х2	х1 ≥ 0, х2 ≥ 0 5х1+6х2 ≤ 25 5х1+х2 ≤ 12,5
	Z=3,5х1+7х2	х1 ≥ 0, х2 ≥ 0 х1+2х2 ≤ 12 8х1+7х2 ≤ 60		Z=1,5х1+12х2	х1 ≥ 0, х2 ≥ 0 х1+8х2 ≤ 56 3х1+х2 ≤ 18,5

 

2.2. Выполнить первый пункт задания, используя приложение MS Excel. По полученным результатам сделать выводы.

 

Задание 3

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

 

Таблица 3

Вар.	ЦФ	Ограничения
	Z1=0,2х1+1,6х2	х1≥ 0, х2≥ 0 х1+8х2≤ 36 2х1+3х2≤ 20
Z2=х1+1,5х2
Z3=х1+3х2
	Z1=6х1+22х2	х1≥ 0, х2≥ 0 3х1+11х2≤ 44 5х1+6х2≤ 42,5
Z2=х1+1,2х2
Z3=4х1+7х2
	Z1=1,2х1+2х2	х1≥ 0, х2≥ 0 3х1+5х2≤ 22,5 2х1+х2≤ 8
Z2=6х1+3х2
Z3=18х1+13,5х2
	Z1=1,5х1+2х2	х1≥ 0, х2≥ 0 3х1+4х2≤ 28 11х1+3х2≤ 38,5
Z2=22х1+6х2
Z3=3х1+2х2
	Z1=4х1+12х2	х1≥ 0, х2≥ 0 х1+3х2≤ 19,5 3х1+х2≤ 22,5
Z2=51х1+17х2
Z3=12х1+10х2
	Z1=0,6х1+х2	х1≥ 0, х2≥ 0 3х1+5х2≤ 35 11х1+2х2≤ 38,5
Z2=22х1+4х2
Z3=8х1+5х2
	Z1=5,5х1+11х2	х1≥ 0, х2≥ 0 х1+2х2≤ 15 8х1+5х2≤ 76
Z2=4х1+2,5х2
Z3=5х1+7х2
	Z1=3х1+10,5х2	х1≥ 0, х2≥ 0 2х1+7х2≤ 56 7х1+5х2≤ 59,5
Z2=14х1+10х2
Z3=5х1+6х2
	Z1=2х1+22х2	х1≥ 0, х2≥ 0 х1+11х2≤ 71,5 2х1+х2≤ 17
Z2=17х1+8,5х2
Z3=4х1+7х2
	Z1=10х1+18х2	х1≥ 0, х2≥ 0 5х1+9х2≤ 67,5 5х1+х2≤ 47,5
Z2=х1+0,2х2
Z3=6х1+3х2
	Z1=4,5х1+13,5х2	х1≥ 0, х2≥ 0 х1+3х2≤ 18 9х1+2х2 ≤ 49,5
Z2=18х1+4х2
Z3=6х1+11х2
	Z1=7х1+21х2	х1≥ 0, х2≥ 0 х1+3х2≤ 10,5 6х1+5х2≤ 24
Z2=1,2х1+х2
Z3=6х1+13х2
	Z1=3,5х1+3х2	х1≥ 0, х2≥ 0 7х1+6х2≤ 45 8х1+х2≤ 28
Z2=4х1+0,5х2
Z3=7х1+3х2
	Z1=х1+1,8х2	х1≥ 0, х2≥ 0 5х1+9х2≤ 54 7х1+2х2≤ 38,5
Z2=14х1+4х2
Z3=4х1+5х2
	Z1=1,5х1+2х2	х1≥ 0, х2≥ 0 3х1+4х2≤ 34 4х1+х2≤ 28
Z2=6х1+1,5х2
Z3=13,5х1+4,5х2
	Z1=10х1+15х2	х1≥ 0, х2≥ 0 2х1+3х2≤ 25,5 11х1+2х2≤ 60,5
Z2=22х1+4х2
Z3=5х1+5х2

 

 

3.2. Выполнить предыдущий пункт, используя приложение MS Excel. Сравнить полученные результаты, на основании чего сделать выводы.

 

 

Задание 4

4.1. Графически и аналитически решить задачу максимизации целевой функции Z. Найти оптимальное решение с учетом стоимости ресурсов. Исходные данные для каждого варианта приведены в таблице 4.

Таблица 4

Вар.	ЦФ	Ограничения	Стоимость ресурсов
	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
	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
	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
	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
	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
	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
	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
	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
	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
	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
	Z=22х1+14х2	х1≥ 0, х2≥ 0 3х1+8х2≤ 76 5х1+х2≤ 40 11х1+7х2≤ 100	c1 = 2 c2 = 6,4 c3 = 12,7
	Z=14х1+8х2	х1≥ 0, х2≥ 0 2х1+5х2≤ 45 9х1+2х2≤ 49,5 7х1+4х2≤ 49,5	c1 = 10 c2 = 14 c3 = 9
	Z=1,4х1+х2	х1≥ 0, х2≥ 0 х1+3х2≤ 27 3х1+х2≤ 33 7х1+5х2≤ 85	c1 = 10,5 c2 = 10,5 c3 = 18
	Z=х1+0,6х2	х1≥ 0, х2≥ 0 х1+4х2≤ 25 6х1+х2≤ 30 5х1+3х2≤ 31,5	c1 = 9 c2 = 11 c3 = 2
	Z=18х1+9х2	х1≥ 0, х2≥ 0 3х1+4х2≤ 34 7х1+х2≤ 41 2х1+х2≤ 13,5	c1 = 16 c2 = 18 c3 = 12,5
	Z=2х1+1,2х2	х1≥ 0, х2≥ 0 2х1+5х2≤ 32,5 5х1+х2≤ 46 5х1+3х2≤ 48	c1 = 8 c2 = 15,1 c3 = 17

 

 

Примечание.

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

 

4.2. Выполнить предыдущий пункт, используя приложение MS Excel. По полученным в двух пунктах результатам сделать выводы.

 

 

Задание 5

С помощью математической системы Mathcad максимизировать целевую функцию Z, приведенную в таблице 5. По результатам расчета построить трехмерный график, на котором изобразить плоскости ограничений и плоскость рассчитанной ЦФ. На графике показать точку оптимума.

 

Таблица 5

Вар.	ЦФ	Ограничения
	Z=9х1+10х2+16х3	18х1+15х2+12х3≤ 360 6х1+4х2+8х3≤ 192 -10х1+3х2+3х3≤ 30 х1≥ 0, х2≥ 0, х3≥ 0
	Z=7х1+12х2+14 х3	28х1+25х2+22х3≤ 560 4х1-40х2+6х3≤ 100 -10х1+30х2+5х3≤ 50 х1≥ 0, х2≥ 0, х3≥ 0
	Z=2х1+3х2+4х3	-5х1+6х2+7х3≤ 20 8х1-9х2+10х3≤ 30 11х1+12х2-13х3≤ 40 х1≥ 0, х2≥ 0, х3≥ 0
	Z=3х1+4х2+2х3	15х1-16х2+17х3≤ 120 -18х1+19х2+20х3≤ 130 21х1+22х2-23х3≤ 140 х1≥ 0, х2≥ 0, х3≥ 0
	Z=3х1+4х2+2х3	15х1+16х2-17х3≤ 120 18х1-19х2+20х3≤ 130 -21х1+22х2+23х3≤ 140 х1≥ 0, х2≥ 0, х3≥ 0
	Z=7х1+12х2+14х3	48х1+25х2+22х3≤ 500 4х1-20х2+6х3≤ 20 -10х1+10х2+5х3≤ 50 х1≥ 0, х2≥ 0, х3≥ 0
	Z=8х1+11х2+15х3	50х1+26х2-20х3≤ 30 4х1-20х2+6х3≤ 20 -10х1+10х2+5х3≤ 50 х1≥ 0, х2≥ 0, х3≥ 0
	Z=10х1+20х2+30х3	-30х1+40х2+50х3≤ 70 10х1-20х2+20х3≤ 30 20х1+30х2-40х3≤ 50 х1≥ 0, х2≥ 0, х3≥ 0
	Z=15х1+25х2+35х3	30х1+40х2-50х3≤ 70 10х1-20х2+20х3≤ 30 -20х1+30х2+40х3≤ 50 х1≥0, х2≥0, х3≥0
	Z=10х1+5х2+45х3	30х1+40х2-50х3≤ 70 10х1-20х2+20х3≤ 30 -20х1+30х2+40х3≤ 50 х1≥ 0, х2≥ 0, х3≥ 0
	Z=5х1+5х2+5х3	20х1+20х2-20х3≤ 120 30х1-30х2+30х3≤ 80 -40х1+40х2+40х3≤ 90 х1≥ 0, х2≥ 0, х3≥ 0
	Z=12х1+12х2+12х3	12х1+13х2-14х3≤ 12 24х1-25х2+24х3≤ 24 -48х1+48х2+49х3≤ 48 х1≥ 0, х2≥ 0, х3≥ 0
	Z=13х1+12х2+14х3	13х1+18х2-19х3≤ 120 24х1-25х2+24х3≤ 240 -48х1+30х2+49х3≤ 480 х1≥ 0, х2≥ 0, х3≥ 0
	Z=14х1+12х2+14х3	14х1+18х2-19х3≤ 150 21х1-25х2+24х3≤ 240 -48х1+30х2+56х3≤ 180 х1≥ 0, х2≥ 0, х3≥ 0
	Z=15х1+12х2+14х3	15х1+18х2-31х3≤ 150 21х1-25х2+28х3≤ 24 -48х1+30х2+56х3≤ 18 х1≥ 0, х2≥ 0, х3≥ 0
	Z=16х1+22х2+11х3	18х1+2х2-20х3≤ 204 16х1-2х2+77х3≤ 31 -48х1+10х2+11х3≤ 204 х1≥ 0, х2≥ 0, х3≥ 0

 

 

Задание 6

С помощью математической системы Mathcad решить транспортную задачу. Исходные данные приведены в таблице 6.

Таблица 6

Вар.	Матрица стоимости перевозок	Матрицы предложения (а) и спроса (b)

 

 

Задание 7

С помощью математической системы MATLAB повторно решить задачу 1 (табл.1). Сопоставить результаты с результатами, полученными в п.п. 1.1 и 1.2.

 

Задание 8

Составить программу для решения задачи ЛПР с помощью симплекс-метода. Произвести расчет задачи ЛПР (табл.1). Программу и результат поместить в отчет.

 

 

Методические указания

 

Пример графического и аналитического решения задачи ЛПР

Пусть дана целевая функция (ЦФ) Z=5х₁+7х₂, а также ограничения:

х₁+4х₂≤ 16,

5х₁+х₂≤ 23,

х₁≥ 0,

х₂≥ 0.

Требуется максимизировать ЦФ.

Чтобы найти решение графически, вначале следует изобразить многоугольник (полигон) допустимых решений. Для этого, используя первое ограничение, вначале запишем уравнение х₁+4х₂=16. Оно получено из неравенства заменой знака «≤» на знак «=».

Для построения прямой линии х₁+4х₂=16 достаточно двух точек. Первую точку удобно взять при х₁ = 0, а вторую точку при х₂ = 0.

Используя второе ограничение, аналогично строят прямую линию 5х₁+х₂=23.

Нетрудно заметить, что прямые х₁=0 и х₂=0 (третье и четвертое ограничения) являются осями координат х₁ и х₂.

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

Теперь построим график ЦФ, приравняв Z к нулю (можно взять любое число). Обозначим этот график символами Z₀.

Для максимизации ЦФ будем перемещать прямую линию в направлении градиента возрастания ЦФ до тех пор, пока прямая линия не достигнет границы полигона допустимых решений. Из рисунка 1 видно, что оптимум находится в точке A. Запишем приблизительные координаты этой точки: х₁ = 4, х₂ = 3.

На основании приближенного графического решения задачи ЛПР найдём точный ответ аналитически. Для этого используем метод подстановок. Из рисунка 1 видно, что точка оптимума находится на пересечении двух прямых:

х₁+4х₂=16,

5х₁+х₂=23.

Для точного определения координат выразим в первом уравнении х₁ через х₂:

х₁=16-4х₂.

Подставим значение х₁ во второе уравнение и определим неизвестные величины:

5·(16-4х₂)+х₂=23.

80-20х₂+х₂=23.

19х₂=57.

х₂=3.

х₁=16-4х₂=16-4·3.

х₁=4.

 

Полученные значения х₁ и х₂ подставляем в ЦФ:

Z=5х₁+7х₂=5·4+7·3

Таким образом, максимальное значение ЦФ Z=41.

 

 

Рис. 1. Полигон допустимых решений

 

В ответ записываем значения х₁ = 4, х₂ = 3 и Z = 41.

 

Пример решения задачи ЛПР с использованием приложения MS Excel

Решим предыдущую задачу с помощью приложения MS Excel. Для этого создадим таблицу, в которую запишем формулы, начальные значения и пояснения:

 

 

Примечание.

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

В ячейках B1 и B2 находятся исходные (начальные) значения х₁ и х₂ соответственно. Эти числа могут быть практически любыми.

В ячейку B3 записана формула данной ЦФ (целевая функция определена в исходных данных).

В ячейки D2 и D3 занесены ограничения (только левая их часть, до знака «≤»). Условия неотрицательности (х₁≥ 0, х₂≥ 0) в таблицу не заносятся – они будут указаны при поиске решения.

Теперь в меню Сервис выбираем пункт Поиск решения… Появляется диалоговое окно, которое заполняем следующим образом:

 

 

В поле Установить целевую ячейку указываем ячейку B3, содержащую формулу ЦФ. Так как необходимо максимизировать ЦФ, то переключатель Равной следует установить в положение максимальному значению.

В поле Изменяя ячейки указываем ячейки с начальными значениями х₁ и х₂. В поле Ограничения заносим условия неотрицательности (х₁≥ 0, х₂≥ 0). Также здесь указываем ячейки с ограничениями, вписывая их значение после знака «≤».

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

После этого в электронной таблице в соответствующих полях появятся координаты х₁ и х₂ точки оптимума и значение ЦФ:

 

 

Как видим, в данном случае аналитическое решение задачи и ее решение с помощью Ms Excel дали одинаковый ответ.

 

Начало блока вычислений

Given

Опишем ограничения:

x1 ≥ 0

x2 ≥ 0

x3 ≥ 0

19x1 + 20x2 – 21x3 ≤ 125

31x1 - 29x2 + 32x3 ≤ 85

-42x1 + 40x2 + 38x3 ≤ 80

Выполним операцию максимизации:

P:= Maximize(Z,x1,x2,x3)

Выведем на экран значения найденных переменных:

Вычислим целевую функцию:

Z(P₀, P₁,P₂) = 61.132

 

Итак, оптимальные значения переменных: х1 = 4,485, х2 = 4,467, x3 = 2,36. Максимальное значение ЦФ Z = 61,132.

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

Присвоим значение ЦФ переменной R:

R:= Z(P₀, P₁,P₂)

Создадим циклы для изменения переменных х₁ и х₂:

x1:=0..P₀ + 5

x2:=0..P₁ + 5

Выразим переменную х₃ из трех ограничений и целевой функции:

 

 

 

 

 

Организованы циклы

t_j:= 1 s_i:= 1

 

Введен вектор запасов

 

Введен вектор спроса

 

Введена целевая функция

x_m,n:=0

Given

В двух последних выражениях следует обратить внимание на форму знаков равенства (жирный знак равенства)

x ≥ 0

x:=Minimize(Z,x)

 

 

Приложение

 

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

В общем виде задачу МП можно сформулировать следующим образом: требуется максимизировать (или минимизировать) целевую функцию (ЦФ)

Z = f(x₁, x₂,…,x_n) (1)

при наличии ограничений на допустимые значения переменных (аргументов) x₁, x₂,…,x_n:

g_i(x₁, x₂,…,x_n) ≤ b_i , (2)

где b_i – некоторые действительные числа (ресурсы, лимиты); выражение в скобках означает, что индекс i изменяется от 1 до m. Величина m показывает, сколько ограничений имеется в данной задаче. Величина n определяет число переменных в задаче (например, число видов выпускаемой продукции).

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

Результат решения задачи МП должен оцениваться количественной мерой – критерием оптимальности. Критерием оптимальности называется количественная оценка качества решения задачи МП (качества планирования производства).

На основании выбранного критерия оптимальности составляется целевая функция, которая представляет собой зависимость критерия оптимальности от оптимизируемых переменных (аргументов). Например, доход (критерий оптимальности) зависит от числа производимых заводом радиоприемников (первая переменная х₁), числа производимых телефонных аппаратов (вторая переменная х₂) и числа компьютеров (третья переменная х₃).

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

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

 

 

Рис. П1. Переход от максимизации к минимизации

 

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

В зависимости от вида целевой функции Z и функций ограничений g_i, математическое программирование можно рассматривать как ряд достаточно самостоятельных дисциплин (разделов математического программирования).

Так, если целевая функция и функции имеющихся ограничений линейны, то такая задача является задачей линейного программирования (ЛПР).

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

В задачах целочисленного программирования неизвестные (аргументы) могут принимать только целые значения.

В задачах параметрического программирования целевая функция или функции ограничений зависят от параметров.

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

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

Наконец, задача, процесс решения которой является многоэтапным (многошаговым), относится к задачам динамического программирования.

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

Термин «линейное программирование» сходен по звучанию с термином «программирование», то есть составление программ (кодирование) для ЭВМ. Однако это разные понятия.

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

Заметим, что первые постановки задач линейного программирования были сделаны известным советским математиком Л.В.Канторовичем.

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

Рассмотрим порядок построения области допустимых решений