Линейное программирование распределения ресурсов

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

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ РОССИЙСКОЙ ФЕДЕРАЦИИ

РЯЗАНСКИЙ ГОСУДАРСТВЕННЫЙ РАДИОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АСУ

КОНТРОЛЬНАЯ РАБОТА

ПО МАТЕМАТИЧЕСКИМ ОСНОВАМ ПРИНЯТИЯ РЕШЕНИЙ

ТЕМА: «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ»

Руководитель: преподаватель кафедры АСУ

Дондик Е.М.

Студент гр. 8030 Веденяпин И.А.

Рязань, 2011 г.

Содержание

1. Задача о распределении ресурсов

1.1 Постановка задачи

1.2 Математическая модель

1.3 Решение задачи симплексным методом

2. Транспортная задача

2.1 Постановка задачи

2.2 Определение допустимого базисного решения

2.3 Распределительный метод решения

3. Матричная игра

3.1 Постановка задачи

3.2 Составление платежной матрицы

3.3 Нахождение решения игры

1. ЗАДАЧА О РАСПРЕДЕЛЕНИИ РЕСУРСОВ

1.1 ПОСТАНОВКА ЗАДАЧИ

В кафе подаются два вида салатов: летний и греческий. В наличии имеются следующие ресурсы:

Мясо - 20 единицы;

Овощи - 24 единицы;

Лук - 3 единиц;

Петрушка - 8 единицы;

Гренки - 6 единиц;

Для приготовления салата «Летнего» требуется:

Овощи - 2 единицы;

Лук - 1 единица;

Петрушка - 1 единица;

Экономия: гренки - 1 единица;

Экономия: мясо - 5 единиц;

Для приготовления салата «Греческого» требуется:

Мясо - 4 единицы;

Овощи - 3 единицы;

Гренки - 1 единица;

Экономия: лук - 3 единицы;

Экономия: петрушка - 1 единица;

Стоимость салата «Летний» - 3$, «Греческий» - 2$.

Ресурсы	Количество единиц ресурсов, необходимых для приготовления блюд	Количество ресурсов
	Салат «Летний»	Салат «Греческий»
Мясо	-5	4	20
Овощи	2	3	24
Лук	1	-3	3
Петрушка	1	0	8
Гренки	0	1	6
Стоимость одного блюда ($)	3	2

1.2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

Управляемые параметры.

Х1 - количество порций салата «Летний» за один день;

Х2 - количество порций салата «Греческий» за один день;

Х(Х1, Х2) - решение.

Система ограничений.

1) -5x1+4x2<=20;

2) 2x1+3x2<=24;

3) 1x1-3x2<=3;

4) 1x1+0x2<=8;

5) 0x1+1x2<=6.

Постановка задачи.

Найти Х, при котором достигается максимум целевой функции: Fmax=3X1+2X2.

1.3 РЕШЕНИЕ ЗАДАЧИ ЛП СИМПЛЕКСНЫМ МЕТОДОМ

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

Выразим базисные переменные через свободные:

y1 = 20 +5x1 - 4x2;

y2 = 24 -2x1 - 3x2;

y3 = 3 - 1x1 + 3x2;

y4 = 8 - 1x1 - 0x2;

y5 = 6 - 0x1 - 1x2;

Каждая строка симплекс-таблицы соответствует базисной переменной, а каждому столбцу соответствует свободная переменная x_j и выделен столбец свободных членов (правых частей ограничений) b_i. Внизу помещена строка целевой функции F.

Преобразования осуществляются в симплексной таблице по следующему алгоритму:

В таблице выделяется разрешающий элемент на пересечении i-й строки и j-го столбца (a_ij).

Разрешающий элемент заменяется на обратную величину.

Все остальные элементы разрешающей строки i делятся на разрешающий элемент.

Все элементы разрешающего столбца j делятся на разрешающий элемент и меняют знак на противоположный.

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

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

Решение задачи симплексным методом:

	-x1	-x2	B
y1	-5	4	20
y2	2	3	24
y3	1	-3	3
y4	1	0	8
y5	0	1	6
Fmax	-3	-2	0

Разрешающий элемент - А(3;1);

	-y3	-x2	B
y1	5	4-15	20+15
y2	-2	3+6	24-6
x1	1	-3	3
y4	-1	3	8-3
y5	0	1	6
Fmax	3	-2-9	9

	-y3	-x2	B
y1	5	-11	35
y2	-2	9	18
x1	1	-3	3
y4	-1	3	5
y5	0	1	6
Fmax	3	-11	9

Разрешающий элемент - А(4;2);

	-y3	-y4	B
y1	4/3	11/3	160/3
y2	1	-9/3	9/3
x1	0	3/3	24/3
x2	-1/3	1/3	5/3
y5	1/3	-1/3	13/3
Fmax	-2/3	11/3	82/3
	-y3	-y4	B
y1	1.3	3.7	53.3
y2	1	-3	3
x1	0	1	8
x2	-0.33	0.33	1.7
y5	0.33	-0.33	4.3
Fmax	-0.67	3.7	27.3

Разрешающий элемент - А(2;1);

	-y2	-y4	B
y1	-1.3	4+3.7	148/3
y3	1	-3	3
x1	0	1	8
x2	0.33	1/3-1	8/3
y5	-0.33	-1/3+1	10/3
Fmax	0.67	5/3	88/3

	-y2	-y4	B
y1	-1.3	7.7	49.3
y3	1	-3	3
x1	0	1	8
x2	0.33	-0.67	2.7
y5	-0.33	0.67	3.3
Fmax	0.67	1.7	29.3

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



Функция максимальна в точке (8.0,2.7). Fmax(8.0,2.7)=29.33.

2. ТРАНСПОРТНАЯ ЗАДАЧА

2.1 ПОСТАНОВКА ЗАДАЧИ

Три издательства с объемами запасов продукции 40, 50 и 20 единиц соответственно получили заявки от четырех сотрудничающих с ними книжных магазинов на поставку книг в количестве 20, 30, 30 и 30 единиц соответственно. В таблице указаны стоимости перевозки единицы продукции из i-го пункта отправления в j-й пункт назначения. Вводятся переменные, определяющие количество отправляемых грузов из i-го издательства в j-й книжный магазин потребления, - x_ij

	Магазин №1	Магазин №2	Магазин №3	Магазин №4
Издательство №1	2	3	2	4
Издательство №2	3	2	5	1
Издательство №3	4	3	2	6

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

.

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

.

Условие выполнения заявок каждого пункта потребления запишется в виде

.

2.2 ОПРЕДЕЛЕНИЕ ДОПУСТИМОГО БАЗИСНОГО РЕШЕНИЯ

Составим матрицу перевозок, указав запасы пунктов отправления и потребности (заявки) пунктов назначения. A₁, …,A_i, …,A_m - обозначения пунктов отправления, B₁,…,B_j,…,B_n - обозначения пунктов назначения.

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

	B1	B1	B1	B1	ai
A1	20	20			40
A1		10	30	10	50
A1				20	20
bj	20	30	30	30	110

Таким образом, получим для решения задач возможные допустимые значения базисных переменных х₁₁=20, х₁₂=10, х₂₂=10, х₂₃=30, х₂₄=10, х₃₄=20. Общая стоимость перевозок F=400. Это и есть допустимое базисное решение.

2.3 РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ РАСПРЕДЕЛИТЕЛЬНЫМ МЕТОДОМ

линейный программирование задача симплексный

Для преобразования таблицы используется понятие цикла.

Циклом в матрице называется ломаная с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удовлетворяющая требованиям:

- замкнутости;

- в каждой вершине должно встречаться два звена.

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

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

	B1	B1	B1	B1	ai
A1	20	20			40
A1		10	30	10	50
A1				20	20
bj	20	30	30	30

х_{13 13} = с₁₃ - с₂₃ + с₂₂ - с₁₂ = 2 - 5 + 2 - 3 = -4,

х_{14 14} = с₁₄ - с₂₄ +с₂₂ - с₁₂ = 4 - 1 + 2 - 3 = 2,

х_{21 21} = с₂₁ - с₁₁ + с₁₂ - с₂₂ = 3 - 2+ 3 - 2 = 2,

х_{31 31} = с₃₁ - с₁₁ + с₁₂ - с₂₂ + с₂₄ - с₃₄ = 4 - 2 + 3 - 2 + 1 - 6 = -2,

х_{32 32} = с₃₂ - с₂₂ +с₂₄ - с₃₄ = 3 - 2 + 1 - 6 = -4,

х_{33 33} = с₃₃ - с₂₃ + с₂₄ - с₃₄ = 2 - 5 + 1 - 6 = -8,

Выбираем те из свободных переменных, которые имеют отрицательное значение суммы стоимости по циклу пересчета. Для получения нового допустимого базисного решения осуществляем сдвиг по циклу пересчета выбранной свободной переменной х₁₃ на величину значений выбранной базисной переменной х₁₂=20, которая после сдвига переводится в свободные.

	B1	B1	B1	B1	ai
A1	20		20		40
A1		30	10	10	50
A1				20	20
bj	20	30	30	30

Сдвиг по циклу привел к новому допустимому базисному решению:

х₁₁=20, х₁₃=20, х₂₂=30, х₂₃=10, х₂₄=10, х₃₄=20, остальные x_ij=0. Новое решение дает значение целевой функции F=320, меньшее предыдущего, т. е. ближе к оптимальному значению.

Для нового базисного решения также подсчитываются суммы стоимостей по циклам пересчета для каждой свободной неизвестной:

₁₂= 3 - 2 + 5 - 2 = 4,

₁₄= 4 - 2 + 5 - 1 = 6,

₂₁= 3 - 2 + 2 - 5 = -2,

₃₁= 4 - 2 + 2 - 5 + 1 - 6 = - 6,

₃₂= 3 - 2 + 1 - 6 = - 4,

₃₃= 2 - 5 + 1 - 6 = -8,

Осуществляем сдвиг по циклу пересчета выбранной свободной переменной х₃₃ на величину значений выбранной базисной переменной х₂₃=10.

	B1	B1	B1	B1	ai
A1	20		20		40
A1		30		20	50
A1			10	10	20
bj	20	30	30	30

Значение целевой функции F=240.

₁₂= 3 - 2 + 1 - 6 + 2 - 2 = - 4,

₁₄= 4 - 2 + 2 - 6 = -2,

₂₁= 3 - 1 + 6 - 2 + 2 - 2 = 6,

₂₃= 5 - 1 + 6 - 2 = 8,

₃₁= 4 - 2 + 2 - 2 = 2,

₃₂= 3 - 6 + 1 - 2 = -4,

Осуществляем сдвиг по циклу пересчета выбранной свободной переменной х₃₂ на величину значений выбранной базисной переменной х₃₄=10.

	B1	B1	B1	B1	ai
A1	20		20		40
A1		20		30	50
A1		10	10		20
bj	20	30	30	30

Значение целевой функции F=200.

₁₂= 3 - 2 + 2 - 3 = 0,

₁₄= 4 - 2 + 2 - 3 + 2 - 1 = 2,

₂₁= 3 - 2 + 3 - 2 + 2 - 2 = 2,

₂₃= 5 - 2 + 3 - 2 = 4,

₃₁= 4 - 2 + 2 - 2 = 2,

₃₄= 6 - 1 + 2 - 3 = 4,

Все стоимости по циклам пересчета больше нуля (_ij > 0), что является признаком оптимальности решения, полученного распределительным методом. Оптимальным решением является следующее: х₁₁=20, х₁₃=20, х₂₂=20, х₂₄=30, х₃₂=10, х₃₃=10, остальные x_ij=0. Стоимость оптимальной перевозки F=200, и уменьшить ее дальше невозможно.

3. МАТРИЧНАЯ ИГРА

3.1 ПОСТАНОВКА ЗАДАЧИ

Два предприятия производят продукцию и поставляют её на рынок региона. Каждое из предприятий имеет возможность производить продукцию с применением одной из четырёх различных технологий. В зависимости от качества продукции, произведённой по каждой технологии, предприятия могут установить цену единицы продукции на уровне 25, 22, 19 и 16 денежных единиц (д.е.) соответственно. При этом предприятия имеют различные затраты на производство единицы продукции:

Технология	Цена реализации единицы продукции, д.е.	Полная себестоимость единицы продукции, д.е.
		Предприятие А	Предприятие В
1	25	17	20
2	22	15	11
3	19	11	10
4	16	6	5

Функция спроса на продукцию задана:

Y = 20 - 0,5*X,

где Y - количество продукции, которое приобретёт население региона (тыс. ед.), а X - средняя цена продукции предприятий, д.е.

Значения долей продукции предприятия А, приобретенной населением, зависят от соотношения цен на продукцию предприятия А и предприятия В. Зависимость установлена и значения являются табличными.

Цена реализации 1 ед. продукции, д.е.	Доля продукции предприятия А, купленной населением
Предприятие А	Предприятие В
25	25	0,31
25	22	0,33
25	19	0,25
25	16	0,2
22	25	0,4
22	22	0,35
22	19	0,32
22	16	0,28
19	25	0,52
19	22	0,48
19	19	0,4
19	16	0,35
16	25	0,6
16	22	0,58
16	19	0,55
16	16	0,5

3.2 СОСТАВЛЕНИЕ ПЛАТЕЖНОЙ МАТРИЦЫ

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

Составим платежную матрицу, определив стратегии каждого игрока:

А₁ - предприятие А выбирает технологию 1

А₂ - предприятие А выбирает технологию 2

А₃ - предприятие А выбирает технологию 3

А₄ - предприятие А выбирает технологию 4

В₁ - предприятие В выбирает технологию 1

В₂ - предприятие В выбирает технологию 2

В₃ - предприятие В выбирает технологию 3

В₄ - предприятие В выбирает технологию 4

Элементами платежной матрицы (a_ij) будет разность прибыли предприятия А и предприятия В.

Найдем а₁₁ (выбраны стратегии А₁ и В₁ - оба предприятия реализуют продукцию по 25 д.е.)

Прибыль = Доход - Затраты

И доход и затраты зависят от количества купленной населением продукции, которое определяется функцией спроса Y = 20 - 0,5*X.

Средняя цена на продукцию равна: Х = (25 +25)/2 = 25.

Значит, Y = 20 - 0,5 * 25 = 7,5 (тыс. ед.)

У предприятия А купят 31% от всей купленной населением продукции:

7,5 тыс. ед. * 31% =7500 ед. * 0,31 = 2325 ед.

Тогда у предприятия В купят 100-31=69% от всей купленной населением продукции:

7,5 тыс. ед. * 69% =7500 ед. * 0,69 = 5175 ед.

Значит:

Прибыль А = 2325 * 25 - 2325 * 17 = 2325 * (25 - 17) = 18600 д.е.

Прибыль В = 5175 * (25 - 20) = 25875 д.е.

а₁₁ = 18600 - 25875 = - 7275 (ед.) = - 7,275 (тыс.ед.)

Можно использовать следующую формулу для расчета элементов платежной матрицы:

a_ij = (10 - 0,25 * (p₁ + p₂)) * 1000 * (d * (p₁ - s₁) - (1 - d) * (p₂ - s₂)),

где p₁ - стоимость реализации единицы продукции предприятием А при выборе им стратегии A_i;

p₂ - стоимость реализации единицы продукции предприятием В при выборе им стратегии B_j;

s₁ - себестоимость единицы продукции предприятия А при выборе им стратегии A_i;

s₂ - себестоимость единицы продукции предприятия В при выборе им стратегии B_j;

d - доля продукции предприятия А, купленной населением при ценах p₁ и p₂.

а₁₁ = (20 - 0,25 * 50) * 1000 * (0,31* 8 - 0,69 * 5) = -7275

а₁₂ = (20 - 0,25 * 47) * 1000 * (0,33* 8 - 0,67 * 11) = -39022,5

а₁₃ = (20 - 0,25 * 44) * 1000 * (0,25* 8 - 0,75 * 9) = -42750

а₁₄ = (20 - 0,25 * 41) * 1000 * (0,2* 8 - 0,8 * 11) = -70200

а₂₁ = (20 - 0,25 * 47) * 1000 * (0,4* 7 - 0,6 * 5) = -1650

а₂₂ = (20 - 0,25 * 44) * 1000 * (0,35* 7 - 0,65 * 11) = -42300

а₂₃ = (20 - 0,25 * 41) * 1000 * (0,32* 7 - 0,68 * 9) = -37830

а₂₄ = (20 - 0,25 * 38) * 1000 * (0,28* 7 - 0,72 * 11) = -65580

а₃₁ = (20 - 0,25 * 44) * 1000 * (0,52* 8 - 0,48 * 5) = 15840

а₃₂ = (20 - 0,25 * 41) * 1000 * (0,48* 8 - 0,52 * 11) = -18330

а₃₃ = (20 - 0,25 * 38) * 1000 * (0,4* 8 - 0,6 * 9) = -23100

а₃₄ = (20 - 0,25 * 35) * 1000 * (0,35* 8 - 0,65 * 11) = -48937,5

а₄₁ = (20 - 0,25 * 41) * 1000 * (0,6* 10 - 0,4 * 5) = 39000

а₄₂ = (20 - 0,25 * 38) * 1000 * (0,58* 10 - 0,42 * 11) = 12390

а₄₃ = (20 - 0,25 * 35) * 1000 * (0,55* 10 - 0,45 * 9) = 16312,5

а₄₄ = (20 - 0,25 * 32) * 1000 * (0,5* 10 - 0,5 * 11) = -6000

Получаем платежную матрицу (в д. ед.):

	B1	B2	B3	B4
А1	-7275	-39022,5	-42750	-70200
А2	-1650	-42300	-37830	-65580
А3	15840	-18330	-23100	-48937,5
А4	39000	12390	16312,5	-6000

3.3 НАХОЖДЕНИЕ РЕШЕНИЯ ИГРЫ

Проверим наличие ситуации равновесия - седловой точки. Для это найдем нижнюю и верхнюю цены игры.

	B1	B2	B3	B4	MIN
А1	-7275	-39022,5	-42750	-70200	-70200
А2	-1650	-42300	-37830	-65580	-65580
А3	15840	-18330	-23100	-48937,5	-48937.5
А4	39000	12390	16312,5	-6000	-6000
MAX	39000	12390	16312.5	-6000

a = -6000 b = -6000

Так как a = b = -6000 (=v, цена игры), то в конфликтной ситуации есть точка равновесия - седловая точка, которую образуют стратегии (А₄, В₄).

Выполняется правило оптимальной игры или принцип минимакса.

Для игры с седловой точкой нахождение решения состоит в выборе максиминной и минимаксной стратегией, которые являются оптимальными (в данном случае оптимальными стратегиями являются А₄, В₄).

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

Так как элементы четвертой строки больше соответствующих элементов первой, второй и третьей строк, то стратегии А_1, А₂ и А₃ - заведомо невыгодные, так как предприятие А стремится максимизировать разницу прибылей. Для предприятия А наиболее выгодным станет выбор четвертой технологии при выборе первой технологии оппонентом (разница доходов составит 39000 д.э., а₄₁ ).

Аналогично для предприятия В. Все элементы четвертого столбца меньше соответствующих элементов первого, второго и третьего столбцов, значит стратегии В₁, В₂ и B₃ - заведомо невыгодные (доминируемые). Для предприятия B наиболее выгодным станет выбор четвертой технологии при выборе первой технологии оппонентом (разница доходов составит 70200 д.э., а₁₄ ).

В ситуации равновесия будет реализовано 12000 единиц продукции (Y = 20 - 0,5 * (16 + 16)/2 = 12000). У первого предприятия купят 6000 ед. продукции (доход составит 60000 д.э.), а у второго 6000 ед. продукции (доход составит 66000 д.э.). В выигрышном положении будет предприятие B.

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

...