Курсовая работа по "Теории принятия решений"

Задание на курсовую работу

Решить три задачи:

1.51. Решить задачу линейного программирования симплекс методом

 

 

 

 

2.4. Решить транспортную задачу

 

          

 

4.32. Решить игровую задачу (игры с природой)

 

λ=0.7

 

Содержание

Задание на курсовую работу	2
Решение задачи линейного программирования симплекс методом	4
Физическая интерпретация задачи	4
Краткое описание метода решения задачи	4
Блок-схема решения ЗЛП симплекс-методом	6
Аналитическое решение задачи	7
Транспортная задача	9
Физическая интерпретация задачи	9
Краткое описание метода решения задачи	9
Блок-схема решения транспортной задачи	11
Аналитическое решение задачи	12
Статистические игры (игры с природой)	18
Физическая интерпретация задачи	18
Краткие теоретические сведения	18
Блок-схема алгоритма решения задачи	19
Аналитическое решение задачи	20
Список использованной литературы	24

 

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

Физическая интерпретация задачи

Для изготовления бетона трех марок, предприятие использует четыре вида сырья. Запасы сырья известны и равны 6, 8, 1, 2 тонн.  Количество сырья каждого вида, необходимое для производства единицы бетона первой марки соответственно равны:  1, 2, -1, 0.  Для бетона второго вида: 2, 1, 1, 1. Для бетона третьего вида: 1,3/4, -1, 0. Отрицательные значения сырья свидетельствуют об отрицательном его воздействии на марку бетона. Прибыль от реализации бетона первого вида составляет 3 у.е., от бетона второго вида 2 у.е., третьего 2 у.е. Составить план, обеспечивающий наибольшую прибыль производству. 

Тогда определим максимальное значение целевой функции

 

при следующих условиях-ограничениях:

 

 

.

Краткое описание метода решения задачи

Симплекс-метод (метод последовательного улучшения плана) — алгоритм решения оптимизационной задачи линейного программирования (ЗЛП). Задача линейного программирования состоит в том, что необходимо максимизировать или минимизировать некоторый линейный функционал на многомерном пространстве при заданных линейных ограничениях.

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

Симплекс-метод  предполагает следующие этапы:

1. Определение опорного (начального) плана,
2. Определение наличия признака оптимальности опорного плана,
3. Переход к не худшему (оптимальному) опорному плану.

 

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

при ограничениях:

 

где с_j, а_ij, b_j – заданные действительные числа; (1.1) – целевая функция; (1.2) – (1.6) – ограничения;  х = (х₁; ...; х_n) – план задачи.

 

Канонической  формой записи ЗЛП называют задачу:

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

Блок-схема решения ЗЛП симплекс-методом

Аналитическое решение задачи

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

 

 

 

Начальный опорный план следующий:

X₀ = (0, 0, 6, 8, 1, 2, 0)

Z(X₀) = 0

Определим оптимальность опорного плана.

Симплексная таблица 1

Бп	Сб	А0	x1	x2	x3	x4	x5	x6	x7
			3	2	0	0	0	0	2
x3	0	6	1	2	1	0	0	0	1
x4	0	8	2	1	0	1	0	0	3/4
x5	0	1	-1	1	0	0	1	0	-1
x6	0	2	0	1	0	0	0	1	-
Zj-Cj		0	-3	-2	0	0	0	0	-2

 

Так как  все оценки ∆_ϳ ≤ 0, и задача решается на максимум, то начальный опорный план не является оптимальным (в индексной строке находятся отрицательные и нулевые коэффициенты).

Переходим к не худшему опорному плану. Для  этого найдем разрешающий элемент в первой таблице, что бы перейти к новой симплекс таблице. Разрешающим столбцом является ϳ=1, так как |-3| из всех отрицательных значений больший по абсолютной величине. Для определения разрешающей строки рассмотрим элементы > 0.

ϴ = min {6/1; 8/2} = 4, i=2 – разрешающая строка.

Элемент – разрешающий элемент первой таблицы. Переменную x₄ выведем из базиса, а x₁ введем в базис. Разрешающую строку делим на , остальные элементы в разрешающем столбце заполняем нулями. Остальное рассчитывается по методу прямоугольника.

 

Аналогичным способом вычисляем остальные  элементы, включая элементы индексной  строки.

Симплексная таблица 2

Бп	Сб	А0	x1	x2	x3	x4	x5	x6	x7
			3	2	0	0	0	0	2
x3	0	2	0	3/2	1	-1/2	0	0	5/8
x1	3	4	1	1/2	0	1/2	0	0	3/8
x5	0	5	0	3/2	0	1/2	1	0	-5/8
x6	0	2	0	1	0	0	0	1	0
Zj-Cj		12	0	-1/2	0	3/2	0	0	-7/8

 

Так не все оценки ∆_j ≥ 0, то план не является оптимальным, тогда переходим к другому не худшему. Разрешающим элементом второй таблицы является . Переменную x₃ выведем из базиса, x₇ введем. Получаем новую симплекс-таблицу.

Симплексная таблица 3

Бп	Сб	А0	x1	x2	x3	x4	x5	x6	x7
			3	2	0	0	0	0	2
x7	2	3 1/5	0	2 2/5	1 3/5	-4/5	0	0	1
x1	3	2 4/5	1	-2/5	-3/5	4/5	0	0	0
x5	0	7	0	3	1	0	1	0	0
x6	0	2	0	1	0	0	0	1	0
Zj-Cj		14 4/5	0	1 3/5	1 2/5	4/5	0	0	0

 

Индексная строка таблицы 3 не содержит отрицательных элементов (все оценки ∆_ϳ ≥ 0, ), следовательно, найденный опорный план оптимален.

 

Оптимальный план:

X* =

Z(X*) =

Ответ: максимальное значение целевой функции Z(X*) . 

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

Физическая интерпретация задачи

У поставщиков A1 , A2 , A3 , находится соответственно 50 , 100 , 130 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 в количестве 70 , 100 , 110 единиц соответственно. Стоимость доставки единицы продукции от поставщика A1 к указанным потребителям равна 1 , 3 , 2 ден.ед. Стоимость доставки единицы продукции от поставщика A2 к указанным потребителям равна 4 , 5 , 7 ден.ед. Стоимость доставки единицы продукции от поставщика A3 к указанным потребителям равна 6 , 2 , 4 ден.ед.

Требуется найти оптимальное решение  доставки продукции от поставщиков  к потребителям, минимизирующие стоимость доставки.

Краткое описание метода решения задачи

Транспортная  задача — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки.

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

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

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

 

Метод потенциалов. Пусть имеется транспортная задача с условием: . Требуется найти план перевозки , который удовлетворял бы балансным условиям, и при этом стоимость всех перевозок была бы минимальна: .

Идея  метода потенциалов сводится к следующему: представим, что каждый из пунктов  отправления A_i вносит за перевозку единицы груза какую-либо сумму. В свою очередь, каждый из пунктов назначения B_j также вносит сумму и передает ее перевозчику. Обозначим – псевдостоимость перевозки единицы груза из A_i в B_j. Признаком оптимальности плана будет служить выполнение двух условий: