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

Размещено на http://www.allbest.ru/

21

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ БЮДЖЕТНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ»

КАЛУЖСКИЙ ФИЛИАЛ

Контрольная работа

ПО ДИСЦИПЛИНЕ: МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ

Студента (ки) Астаховой Ольги Николаевны

Группы 2ЭБФКз8

Факультет: Финансово-учетный

Специальность: «Экономика», профиль «Финансы и кредит»

Отделение Заочное

Научный руководитель Зайчикова И.В.

Калуга, 2014

Задача 1

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

Дивиденды по акциям А составляют 8% в год, по акциям В - 10%. Какую максимальную прибыль можно получить в первый год?

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум, и почему?

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

Пусть xi - стоимость акций i-го предприятия, тогда целевая функция задачи линейного программирования будет иметь вид:

f(x) = 0,08х1 + 0,10х2 max.

Ограничения задачи имеют вид:

х1 + х2 300 -- ограничение по суммарной стоимости акций;

2х2 х1 -- ограничение по количеству акций;

х2 100 - ограничение на покупку акций В.

По экономическому смыслу задачи х1,2 0.

Задача линейного программирования имеет вид:

Геометрически задача линейного программирования (ЗЛП) представляет собой отыскание такой точки многоугольника допустимых решений (ОДР), координаты которой доставляют целевой функции максимальное значение. Все точки ОДР являются допустимыми. Построим ОДР целевой функции, для чего найдем уравнения ограничивающих прямых.

х1 + х2 = 300

х1 = 0; х2 = 300

х2 = 0; х1 = 300

2х2 = х1

х1 = 0; х2 = 0;

х1 = 200; х2 = 100

х2 = 100 горизонталь, параллельная оси Ох

На рис.1 построим эти прямые и выделим ОДР внутренней штриховкой.

Рис.1. Графическое решение задачи линейного программирования

Получили многоугольник ОАВ, угловые точки которого имеют следующие координаты: О(0, 0), A(200; 100); B(300; 0). Координаты вершины А(200, 100) найдены путем подстановки в уравнение 2х2 = х1 значения х2 = 100.

Построим вектор-градиент целевой функции, соединив его вершину (0,08; 0,10) с началом координат О(0, 0) и проведем через начало координат линию уровня целевой функции f(X) = 0 перпендикулярно вектору-градиенту. Смещая эту линию параллельно самой себе вправо-вверх до крайней точки ОДР т.(А), найдем значение целевой функции в этой точке (максимальное):

F(А) = 0,08*200 + 0,1*100 = 26 (тыс.ден.ед.)

Х* = (200, 100)

Таким образом, оптимальный план покупки акций будет следующим: необходимо купить на 200 тыс.руб. акций А и на 100 тыс.руб. акций В, при этом все условия будут выполнены и максимальная прибыль равна 26,0 тыс.ден.ед.

При решении данной задачи на минимум оптимальный план был бы равен Xmin = (0, 0) и Fmin = 0, т.е. минимальное значение целевая функция принимает при отсутствии купленных акций, при этом линия уровня целевой функции F(X) касается начальной точки ОДР - точки О(0, 0).

Задача 2

Решить графическим методом задачу с n переменными.

Для графического решения ЗЛП с 5-ю переменными надо вначале проверить условие n - r ? 2, где

n - число неизвестных (равно 5);

r - ранг системы векторов условий (равен 3).

Следовательно, условие n - r ? 2 соблюдается.

Как видим, система ограничений не имеет разрешенных переменных, поэтому методом Жордана-Гаусса приведем ее к равносильной разрешенной (табл.1).

Таблица 1

х1	х2	х3	х4	х5	b
1	-4	1	-1	-1	-22
-6	3	1	1	0	6
2	2	-1	0	1	17
3	-8	-2	2	-4	0
1	-4	1	-1	-1	-22
0	-21	7	-5	-6	-126
0	10	-3	2	3	61
0	4	-5	5	-1	66
Разделим 2-ю строку на 7
1	-4	1	-1	-1	-22
0	-3	1	-5/7	-6/7	-18
0	10	-3	2	3	61
0	4	-5	5	-1	66
1	-1	0	-2/7	-1/7	-4
0	-3	1	-5/7	-6/7	-18
0	1	0	-1/7	3/7	7
0	-11	0	10/7	-37/7	-24
1	0	0	-3/7	2/7	3
0	0	1	-8/7	3/7	3
0	1	0	-1/7	3/7	7
0	0	0	-1/7	-4/7	53

Используя последнюю часть табл.1, запишем ЗЛП в преобразованном виде:

Отбросим в уравнениях-ограничениях неотрицательные разрешенные переменные х1, х3 и х2 и заменим знаки равенства знаками «», получим вспомогательную ЗЛП с двумя переменными х2 и х5.

Эту задачу решим графическим методом, (умножив каждое ограничение на 7).

-3х4 + 2х5 = 21 х4 = 0; х5 = 21/2 х5 = 0; х4 = -7

-8х4 + 3х5 = 21 х4 = 0; х5 = 7 х5 = 0; х4 = -21/8

-х4 + 3х5 = 49 х4 = 0; х5 = 49/3 х5 = 0; х4 = -49

Построим ОДР (рис.2). Чтобы не загромождать чертеж, начертим только прямую -8х4 + 3х5 = 21, положительная часть этой прямой является частью ОДР, двумя другими границами ОДР являются оси Ох и Оу. (Две другие прямые ограничений лежат левее, поэтому не входят в ОДР).



Рис. 2 Графическое решение задачи линейного программирования

Как видим, ОДР открыта сверху (с учетом ограничений xi 0), но т.к. вектор-градиент целевой функции направлен влево-вниз, то т.О(0, 0) является точкой, соответствующей максимальному значению целевой функции Z(О) = -1/7*0 - 4/7*0 - 53 = -53.

Чтобы найти оптимальное решение исходной задачи, используем систему ограничений в разрешенном виде:

Таким образом, Х* =(3, 7, 3, 0, 0).

max Z(X*) = 3*0 + 7*0 + 3*0 + 0 + 0 - 53 = - 53

Задача 3

Решить ЗЛП симплексным методом:

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

Задача имеет начальное опорное решение Х1 =(0,0,0,1,1) с базисом Б1 = (А4, А5 ). Вычислим оценки разложений векторов условий и дополним таблицу строкой оценок.

Таблица 1

			-4	-2	1	0	0
Б	Сб	А0	А1	А2	А3	А4	А5	1	2	3	4	5
А4	0	6	3	-2	4	1	0	2
А5	0	18	2	1	3	0	1	9
k	0	4	2	1	0	0

Данное решение не является оптимальным, т.к. векторам А1, А2 и А3 соответствуют положительные оценки, а по признаку оптимальности в задаче на минимум все оценки должны быть неположительными. Выбираем столбец вектора А1 с наибольшей положительной оценкой и строку вектора А4 (1 = min{2, 9} = 2). Вектор А4 выведем из базиса, а на его место введем в базис вектор А1. Его строку найдем, разделив строку вектора А4 на разрешающий элемент (3) столбца вектора А1.

			-4	-2	1	0	0
Б	Сб	А0	А1	А2	А3	А4	А5	1	2	3	4	5
А1	-4	2	1	-2/3	4/3	1/3	0		-
А5	0	14	0	7/3	1/3	-2/3	1		6
k	-8	0	14/3	-13/3	-4/3	0

Строку вектора А5 в этой таблице находим, вычитая из каждого элемента этой строки в предыдущей таблице соответствующий элемент строки вектора А1 в новой таблице, умноженный на ее элемент направляющего столбца (А1) в предыдущей таблице (т.е. на 2). Далее считаем оценки k. Данное решение опять не является оптимальным, т.к. вектору А2 соответствует положительная оценка (14/3). Вектор А5 выведем из базиса, а на его место введем в базис вектор А2. Его строку найдем, разделив строку вектора А4 на разрешающий элемент (3) столбца вектора А1. Строку вектора А1 в этой таблице находим, вычитая из каждого элемента этой строки в предыдущей таблице соответствующий элемент строки вектора А1 в новой таблице, умноженный на ее элемент направляющего столбца А2 (т.е. на -2/3).

			-4	-2	1	0	0
Б	Сб	А0	А1	А2	А3	А4	А5	1	2	3	4	5
А1	-4	6	1	0	10/7	1/7	2/7				42
А2	-2	6	0	1	1/7	-2/7	3/7				-
k	-36	0	0	-7	0	-13/7

Данное опорное решение является оптимальным, т.к. все оценки неположительные. Х1*=(6, 6, 0). Zmin = 6*(-4) + 6*(-2) + 0 = -36. Однако это решение не является единственным, т.к. вектор А4, не входящий в базис, имеет нулевую оценку. Вектор А1 выведем из базиса, а на его место введем в базис вектор А4. Его строку найдем, разделив строку вектора А1 на разрешающий элемент (1/7) столбца вектора А4. Строку вектора А2 в этой таблице находим, вычитая из каждого элемента этой строки в предыдущей таблице соответствующий элемент строки вектора А4 в новой таблице, умноженный на ее элемент направляющего столбца А4 (т.е. на -2/7). Далее считаем оценки k.

			-4	-2	1	0	0
Б	Сб	А0	А1	А2	А3	А4	А5	1	2	3	4	5
А4	0	42	7	0	10	1	2
А2	-2	18	2	1	3	0	1
k	-36	0	0	-7	0	-2

Данное решение также является оптимальным, т.к. не имеет положительных оценок. Х2*=(0, 18, 0). Zmin = 0 + 18*(-2) + 0 = -36. Ответ можно записать в такой форме: Zmin = -36. Х* = (1-t)X1* + tX2*, 0t1.

Задача 4

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

Двойственная задача имеет вид:



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

Решим эту задачу графически.

Построим ОДР (рис.3). На рисунке ОДР выделена заливкой. Она ограничена точками А(0, 2), В(1, 4), С(3, 4), D(4, 2), Е(2, 0). (Точки пересечения прямых найдены решением систем соответствующих уравнений).



Рисунок 3 Построение ОДР

Построим вектор-градиент (2, 3) из начала координат и перпендикулярно ему линию F(0) = 0. Перемещая эту линию параллельно самой себе по направлению вектора-градиента (вверх-вправо) до последней угловой точки ОДР, видим, что максимальное значение целевая функция принимает в т. С(3, 4). Отсюда, max F(Y) = 2*3 + 3*4 = 18; y1 = 3; y2 = 4.

Подставим решение задачи в систему ограничений:

Согласно второй теореме двойственности, в тех ограничениях, которые выполняются как строгие неравенства (1, 2 и 5), соответствующие координаты исходной задачи равны нулю, т.е. х1* = х2* = х5* = 0. Учитывая это, из системы ограничений исходной задачи получим:

Из 1-й строки получим: х3 = 1, откуда: х4 = 3 - 1 = 2. Таким образом, Х* = (0, 0, 1, 2, 0) и min Z(X) = 0 + 0 + 10*1 + 4*2 + 0 = 18.

Как видим, min Z(X) = max F(Y) = 18. Решение исходной задачи найдено.

Задача 5

Предприятие может выпускать несколько видов продукции: А1, А2, А3, получая при этом прибыль. Величина прибыли определяется состоянием спроса («природой рынка»), который может находиться в одном из нескольких возможных состояний: В1, В2, В3.

Зависимость величины прибыли от вида выпускаемой продукции и состояния рынка представлена в платежной матрице:

Рассмотрим эту таблицу как матричную игру «предприятие (игрок А) против «природы» рынка (игрок В)».

Для заданной платежной матрицы:

1. найдите нижнюю и верхнюю цены игры;

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

3. интерпретируйте полученные результаты применительно к рассматриваемой экономической задаче.

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

Составим таблицу для определения цены игры (табл. 2):

Таблица 2

Определение цены игры

Спрос Вид продукции	В1	В2	В3	i
A1	5	1	4	1
A2	6	8	1	1
A3	2	8	3	2
j	6	8	4	2 4

Как видим, , следовательно, игра не имеет седловой точки и оптимальное решение будем искать в смешанных стратегиях игроков:



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

Задача 1

Задача 2

Решение обеих задач можно найдем с помощью надстройки Поиск решения MS Excel. Начнем с задачи 1.

Откроем лист MS Excel, создадим шаблон для решения задачи (рис.4).

Рисунок 4 Шаблон для решения задачи

В ячейках В3:D3 будут рассчитываться значения переменных в оптимальном плане. В ячейки В4:D4 внесем значения коэффициентов целевой функции (1, 1, 1).

В ячейки В7:D9 внесем коэффициенты уравнений-ограничений. В ячейку G7 впишем формулу: =СУММПРОИЗВ($В$3:$D$3;B7:D7) и размножим ее на ячейки G8:G9. В ячейки I7:I9 введем свободные члены ограничений (1, 1, 1). В ячейку G4 впишем формулу: =СУММПРОИЗВ($B$3:$D$3;B4:D4) - это значение целевой функции (вначале равно 0).

Далее, установим курсор в ячейку G4 и выберем Сервис - Поиск решения и в открывшемся окне Поиск решения отметим минимальному значению, Изменяя ячейки - введем $B$3:$B$D3, введем ограничения (рис.4) для ячеек G7:G9 >= I7:I9, (рис.5).

Рисунок 5 Ввод ограничения

Рисунок 6 Ввод диапазона изменения и ограничений

модель графический симплекс матрица

Далее, нажмем кнопку Параметры, установим флажки в окошках Линейная модель и Неотрицательные значения (рис.7), нажмем ОК.

Рисунок 7 Установка параметров

В окне Поиск решения нажмем кнопку Выполнить, появится окно Результаты поиска решения с сообщением Решение найдено (рис.8).

Рисунок 8 Сообщение о выполнении решения

На рис.9 показаны результаты оптимального решения.

Рисунок 9 Оптимальное решение задачи 1

Было получено оптимальное решение: Х1 = 0,172414, Х2 = 0, Х3 = 0,103448.

Минимальное значение целевой функции составило: min Z = 0,275862.

Аналогичным образом решим задачу 2, результат решения показан на рис.10.

Рисунок 10 Оптимальное решение задачи 2

Было получено оптимальное решение: Y1 = 0, Y2 = 0,034483, Y3 = 0,241379.

Максимальное значение целевой функции составило: max Z = 0,275862.

Как видим, min Z = max Z, что говорит о правильности решения.

Найдем цену игры по формуле:

Оптимальную стратегию найдем по формуле:

Из этого следует, что для получения максимальной прибыли предприятие должно выпускать 62,5% продукции А1, 37,5% продукции А3, а продукцию А2 - не выпускать.

Аналогично определим оптимальную стратегию спроса , учитывая, что четвертый столбец исходной матрицы был отброшен как невыгодный:

Из этого следует, что оптимальный спрос в 12,5% находится в состоянии В2, а в 87,5% - в состоянии В3..

Задача 6

Цветочный магазин использует 600 глиняных цветочных горшков в месяц. Стоимость одного заказа - 150 руб. Годовая стоимость хранения одного горшка составляет 1 руб. 50 коп. Доставка заказа осуществляется в течение одного дня. Магазин работает 365 дней в году.

Определите:

а) экономичный объем заказа;

б) годовые расходы на хранение запасов;

в) период поставок;

г) точку заказа.

Для определения оптимального объема заказа используем формулу Уилсона:

 где

QW - оптимальный объем заказа, шт.;

K - затраты на размещение заказа, равные 150 руб.;

V - объем использования горшков, равный 600*12 = 7200 горш./год;

S - годовая стоимость хранения одного горшка, равная 1 руб. 50 коп. в год.

(шт.)

Годовые затраты на заказ и хранение запасов найдем по формуле:

(руб.)

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

(года)

Поскольку известно, что магазин работает 365 дней в году, то период поставок составит:

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

 (горшков), где

h0 - остаток горшков на складе, шт. (округлено в сторону увеличения);

t - время доставки заказа, дн.

Это количество называется точкой заказа.

Литература

1. Сборник задач по высшей математике для экономистов: учеб. пособие/ Под ред. В.И. Ермакова. - М.: ИНФРА-М, 2003

2. Исследование операций в экономике: учеб. пособие для вузов/ Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2003

3. Экономико-математические методы и прикладные модели: учеб.пособие для вузов / В.В. Федосеев, А.Н. Гармаш, И.В. Орлова и др.; под ред. В.В. Федосеева. - М.: ЮНИТИ-ДАНА, 2005

Размещено на Allbest.ru