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

Размещено на 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 ПОСТАНОВКА ЗАДАЧИ

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

Тесто - 24 единицы;

Сыр - 3 единицы;

Куриное мясо - 30 единиц;

Помидоры - 24 единицы;

Огурцы - 7 единиц;

Для приготовления итальянской пиццы требуется:

Тесто - 2 единицы;

Сыр - 1 единица;

Куриное мясо - 6 единиц;

Огурцы - 1 единица;

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

Для приготовления римской пиццы требуется:

Тесто - 3 единицы;

Помидоры - 4 единица;

Сыр - 2 единицы;

Экономия: куриное мясо - 6 единиц;

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

Стоимость одной итальянской пиццы - 2$, римской - 5$.

Ресурсы	Количество единиц ресурсов, необходимых для приготовления блюд	Количество ресурсов
	Пицца «Итальянская»	Пицца «Римская»
Тесто	2	3	24
Сыр	1	2	3
Куриное мясо	6	-6	30
Помидоры	-1	4	24
Огурцы	1	0	7
Стоимость одного блюда ($)	2	5

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

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

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

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

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

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

1) 2x1+3x2<=24;

2) 1x1-3x2<=3;

3) 6x1-6x2<=30;

4) -1x1+4x2<=24;

5) 1x1+0x2<=7.

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

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

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

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

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

y1 = 24 - 2x1 - 3x2;

y2 = 3 -1x1 + 3x2;

y3 = 30 - 6x1 + 6x2;

y4 = 24 + 1x1 - 4x2;

y5 = 7 - 1x1 - 0x2;

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

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

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

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

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

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

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

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

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

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

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

	-x1	-y4	B
y1	11/4	-3/4	24/4
y2	1/4	3/4	84/4
y3	18/4	6/4	264/4
x2	-0.25	0.25	24/4
y5	1	0	28/4
Fmax	-13/4	5/4	120/4

	-x1	-y4	B
y1	2.8	-0.75	6
y2	0.25	0.75	21
y3	4.5	1.5	66
x2	-0.25	0.25	6
y5	1	0	7
Fmax	-3.3	1.3	30

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

	-y1	-y4	B
x1	4/11	-3/11	24/11
y2	-1/11	9/11	225/11
y3	-18/11	30/11	618/11
x2	1/11	2/11	71/11
y5	-4/11	3/11	52/11
Fmax	13/11	4/11	37.1
	-y1	-y4	B
x1	0.36	-0.27	2.2
y2	-0.09	0.82	20.5
y3	-1.6	2.7	56.2
x2	0.09	0.18	6.5
y5	-0.36	0.27	4.8
Fmax	1.2	0.36	37.1

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

Функция максимальна в точке (2.2,6.5). Fmax(2.2,6.5)=37.09

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

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

Три компьютерных фирмы с объемами запасов продукции 30, 40 и 40 единиц соответственно получили заявки от четырех сотрудничающих с ними магазинов на поставку компьютерной техники в количестве 10, 30, 40 и 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	10	20			30
A1		10	30		40
A1			10	30	40
bj	10	30	40	30	110

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Технология	Цена реализации единицы продукции, д.е.	Полная себестоимость единицы продукции, д.е.
		Предприятие А	Предприятие В
1	12	8	10
2	8	5	4
3	4	2	1

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

Y = 10 - 0,6*X,

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

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

Цена реализации 1 ед. продукции, д.е.	Доля продукции предприятия А, купленной населением
Предприятие А	Предприятие В
12	12	0,31
12	8	0,33
12	4	0,18
8	12	0,7
8	8	0,3
8	4	0,2
4	12	0,92
4	8	0,85
4	4	0,72

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значит, Y = 10 - 0,6 * 12 = 2.8 (тыс. ед.)

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

2.8 тыс. ед. * 31% =2800 ед. * 0,31 = 868 ед.

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

2,8 тыс. ед. * 69% =2800 ед. * 0,69 = 1932 ед.

Значит:

Прибыль А = 868 * 12 - 868 * 8 = 868 * (12 - 8) = 3472 д.е.

Прибыль В = 1932 * (12 - 10) = 3864 д.е.

а₁₁ = 3472 - 3864 = - 392 (ед.) = - 0,392 (тыс.ед.)

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

a_ij = (10 - 0,3 * (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₂.

а₁₁ = (10 - 0,3 * 24) * 1000 * (0,31* 4 - 0,69 * 2) = -392

а₁₂ = (10 - 0,3 * 20) * 1000 * (0,33* 4 - 0,67 * 4) = -5440

а₁₃ = (10 - 0,3 * 16) * 1000 * (0,18* 4 - 0,82 * 3) = -9048

а₂₁ = (10 - 0,3 * 20) * 1000 * (0,7* 3 - 0,3 * 2) = 6000

а₂₂ = (10 - 0,3 * 16) * 1000 * (0,3* 3 - 0,7 * 4) = -9880

а₂₃ = (10 - 0,3 * 12) * 1000 * (0,2* 3 - 0,8 * 3) = -11520

а₃₁ = (10 - 0,3 * 16) * 1000 * (0,92* 2 - 0,08 * 2) = 8736

а₃₂ = (10 - 0,3 * 12) * 1000 * (0,85* 2 - 0,15 * 4) = 7040

а₃₃ = (10 - 0,3 * 8) * 1000 * (0,72* 2 - 0,28 * 3) = 4560

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

	B1	B2	B3
А1	-392	-5440	-9048
А2	6000	-9880	-11520
А3	8736	7040	4560

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

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

	B1	B2	B3	MIN
А1	-392	-5440	-9048	-9048
А2	6000	-9880	-11520	-11520
А3	8736	7040	4560	4560
MAX	8736	7040	4560

a = 4560 b = 4560

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

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

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

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

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

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

В ситуации равновесия будет реализовано 7600 единиц продукции (Y = 10 - 0,6 * (4 + 4)/2 = 7600). У первого предприятия купят 5472 ед. продукции (доход составит 10944 д.э.), а у второго 2128 ед. продукции (доход составит 6384 д.э.). В выигрышном положении будет предприятие А.

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