4 Примеры решения некоторых типовых задач

Пример 1: Решить графически ЗЛП:

Решение: Сначала проведем оси: на горизонтальной будем откладывать значения переменной x₁ , а на вертикальной x₂ . Далее рассмотрим условия неотрицательности переменных .

X1	0	-2
X2	2	0

X1	0	2
X2	-3	0

Рисунок 1. Иллюстрация решения задачи

Э ти два ограничения показывают, что ОДР будет находиться в 1-ой четверти. Чтобы учесть оставшиеся ограничения, заменим неравенства на равенства, а затем на плоскости проведем эти прямые. Например, неравенство заменяем на равенство , которое проходит через точки (0; 2) и (-2; 0). Обозначим эту прямую 1 . Определим полуплоскость, выбрав контрольную точку (0; 0). Так как - верное неравенство, то точки полуплоскости, содержащей (0; 0) удовлетворяют первому ограничению. Аналогично рассматриваем оставшиеся ограничения. Получена область допустимых решений – многоугольник ABCDE. Строим вектор и линию уровня . Перемещаем линию уровня вдоль вектора до опорной прямой (обозначены пунктирными линиями). Эта прямая проходит через точки А и С, причем в точке А определяется Min Z, а в точке С - Max Z. Определим координаты точки A как пересечение прямой 3 и прямой x₂⁼0:

Значит,

Определим координаты точки С как пересечение прямых 2 и 4 :

Значит,

Графическим методом решаются задачи линейного программирования, записанные в каноническом виде и удовлетворяющие условию , где n – число неизвестных системы ограничений; r – ранг системы векторов условий. Если уравнения системы ограничений линейно независимы, то ранг r равен числу уравнений системы m.

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

Таблица 10. Нормы расходы сырья и получаемая прибыль

	А	В	С	Запасы сырья, ед.
І	-	1	1	12
ІІ	1	3	2	18
ІІІ	-	1	2	16
Прибыль, ден.ед.	2	7	6

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

Решение:

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

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

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

2. Приведем задачу к каноническому виду

3. В ыразим базисные переменные и целевую функцию через свободные переменные:

4. Найдем начальный опорный план задачи

5. Занесем коэффициенты целевой функции и системы ограничений в симплексную таблицу

Таблица 11. Исходная симплекс-таблица

БП	СЧ	х1	х2	х3	х4	х5	Q
х4	12	0	1	1	1	0	12
х1	18	1	3	2	0	0	9
х5	16	0	1	2	0	1	8
Z	36	0	-1	-2	0	0

В Z- строке есть отрицательные элементы. Следовательно, начальный опорный план не является оптимальным. Найдем минимальный отрицательный элемент Z- строки: (-2) в столбце «х₃». За ведущий столбец выбираем «х₃», значит, переменная х₃ будет включена в базис.

Так как среди элементов ведущего столбца есть положительные, то существует новый опорный план, более близкий к оптимальному. Подсчитаем симплексные отношения (отношения свободных членов к соответствующим положительным элементам ведущего столбца) и найдем среди них минимальное: . Значит, 3-я строка является ведущей, а элемент а₃₃ = 2 – разрешающим. Следовательно, переменная х₅ выйдет из базиса.

6. Методом Жордана – Гаусса проведем одну итерацию замещения.

Таблица 12. Одно из оптимальных решений

БП	СЧ	х1	х2	х3	х4	х5	Q
х4	4	0	½	0	1	-½	8
х1	2	1	2	0	0	0	1
х3	8	0	½	1	0	½	16
Z	52	0	0	0	0	1

Так как в Z- строке все элементы больше или равны нулю, то найден оптимальный план: .

Он не единственный, так как существует нулевой элемент Z- строки, соответствующий свободной переменной х₂.

7. Найдем второе оптимальное решение. Столбец «х₂» принимаем за ведущий и находим минимальное симплексное отношение: . Тогда вторая строка станет ведущей.

Таблица 13. Второе оптимальное решение

БП	СЧ	х1	х2	х3	х4	х5	Q
х4	3,5	-½	0	0	1	-½
х2	1	½	1	0	0	0
х3	7,5	-½	0	1	0	½
Z	52	0	0	0	0	1

Из последней таблицы 13

Значит, следует выпускать 1 ед. продукции 2 типа, 7,5 ед. продукции 3 типа, а продукцию 1 типа не выпускать вообще, при этом будет достигнута наибольшая прибыль в размере 5 ден. ед. Переменные являлись вспомогательными и показывали остатки сырья І и ІІІ вида, значит сырье І типа останется в количестве 3,5 ед., а сырье ІІІ вида израсходуется полностью.

Приложение 1

№.1	№ 2	№.3
№.4	№.5	№.6
№7	№.8	№9
№.10	№.11	№.12
№.13	№14	№.15
№16	№.17	№.18
№.19	№20	№.21

Приложение 2.

№1	№2	№3
№.4	№.5	№6
№7	№.8	№9
№.10	№.11	№ .12
№13	№14	№15
№16	№17	№18
№19	№.20	№21
№22	№23	№24
№25	№.26	№27
№28	№29	№30
№.31	№.32	№ .33
№34	№35	№36
№37	№38	№39
№.40	№41	№42

Рекомендованная литература

Основная

1. Сборник задач и упражнений по высшей математике. Математическое программирование: Учебное пособие/Под общ. ред. А.В. Кузнецова и Р.А. Рутковского. 3-е изд., стер.–СПб.: Издательство "Лань", 2010.–448 с.:ил.–(Учебники для вузов. Специальная литература).

2. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование/ под общ. ред. А.В. Кузнецова: Учебник. 3-е изд., стер.–СПб.: Издательство "Лань", 2010.–352 с.:ил.–(Учебники для вузов. Специальная литература).

3. Федосеев В.В., Гармаш А.Н., Орлова И.В. Экономико-математические методы и прикладные модели: учебное пособие для вузов.-3-е изд. –М.: Юрайт-издат: Высшее образование, 2012.- Режим доступа: http:// http://znanium.com/catalog.php?bookinfo=389717

Дополнительная

4. Математические методы и модели исследования операций: учебник для студентов, обучающихся по специальности 080116 "Математические методы в экономике" и другим экономическим специальностям/ под ред. В.А. Колемаева.-М.:ЮНИТИ-ДАНА, .-592 с.

5. Эконометрика [Электронный ресурс]: учебник для студентов вузов /Н.Ш. Кремер, Б.А. Путко; под ред. Н.Ш. Кремера. -–3-е изд., перераб. и доп. –М.: ЮНИТИ-ДАНА, 2012.–328с.- Режим доступа: http://znanium.com/catalog.php?bookinfo=395801.

6. Практикум по эконометрике (+CD): учебное пособие /И.И. Елисеева, С.В. Курышева, Н.М. Гордиеенко и др.; по ред. И.И. Елисеевой. – 2-е изд., перераб. и доп.–М.: Финансы и статистика, 2008.–344с.

7. Орлова И.В., Половников В.А. Экономико-математические методы и модели: компьютерное моделирование: учебное посо­бие. — М.: Вузовский учебник: НИЦ ИНФА-М, 2014.-389 с.- Режим доступа: http://znanium.com/catalog.php?bookinfo=424033.

ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

СОЦИАЛЬНО-ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ

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

Составитель: Половченко Светлана Васильевна,

Колпакова Евгения Владимировна

Авторская верстка

Компьютерная верстка С.В. Половченко

_________________________________________________________________________________________

Подписано в печать __.__.2017г.			Формат 60х84 1/16
Бумага офсетная			Офсетная печать
Печ. л. _____			Изд.№ ____
Усл. печ. л. ____			Тираж 30 экз.
Уч.-изд. л. ____			Заказ №

2