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

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

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

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

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

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

λ=0.7

Содержание

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

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

Для изготовления бетона трех марок, предприятие использует четыре вида сырья. Запасы сырья известны и равны 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, и задача решается на максимум, то начальный опорный план не является оптимальным (в индексной строке находятся отрицательные и нулевые коэффициенты).

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

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

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

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

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

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

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

Индексная строка таблицы 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. Признаком оптимальности плана будет служить выполнение двух условий:

1. - для всех базисных клеток
2. - для всех свободных клеток

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

Блок-схема решения транспортной задачи

Рис. 2. Блок-схема алгоритма решения задачи

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

Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись  суммарной потребности потребителей. Проверим это условие. В нашем случае, потребность всех потребителей - 280 единиц продукции равна запасам всех поставщиков.

Математическая модель транспортной задачи:

F = ∑∑cijxij,

при условиях:

∑xij = ai, i = 1,2,…, m,

∑xij = bj, j = 1,2,…, n,

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

Таблица 1

1. Поиск первого опорного плана.

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

Минимальный элемент матрицы тарифов  находится в ячейке A₁B₁ и равен 1, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₁ к потребителю B₁ наиболее рентабельный. Запасы поставщика A₁ составляют 50 единиц продукции. Потребность потребителя B₁ составляет 70 единиц продукции. От поставщика A₁ к потребителю B₁ будем доставлять min = { 50 , 70 } = 50 единиц продукции. Разместим в ячейку A₁B₁ значение равное 50. Мы полностью израсходoвали запасы поставщика A₁. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения (Таблица 2).

Минимальный элемент матрицы тарифов находится  в ячейке A₃B₂ и равен 2, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика A₃ к потребителю B₂ наиболее рентабельный. Запасы поставщика A₃ составляют 130 единиц продукции. Потребность потребителя B₂ составляет 100 единиц продукции. От поставщика A₃ к потребителю B₂ будем доставлять min = { 130 , 100 } = 100 единиц продукции. Разместим в ячейку A₃B₂ значение равное 100. Мы полностью удовлетворили потребность потребителя B₂. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения (Таблица 2).

Продолжая вычисления, получаем первый опорный план (Таблица 3).

Таблица 2

Таблица 3

Заполненные нами ячейки будем называть базисными, остальные - свободными. Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.  Количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.

Мы нашли  начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Значение  целевой функции для этого  опорного плана равно:

S₀ = 1 * 50 + 4 * 20 + 7 * 80 + 2 * 100 + 4 * 30 = 1010 ден. ед.

Общие затраты на доставку всей продукции, для начального решения, составляют 1010 ден. ед.

2. Оценка полученного решения.

Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика. Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя. Для базисной ячейки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута.

u_i + v_j = c_ij, где c_ij - тариф клетки A_iB_j

Поскольку, число базисных клеток - 5, а общее количество потенциалов  равно 6, то для однозначного определения  потенциалов, значение одного из них  можно выбрать произвольно.

Таблица 4

Найдем  оценки свободных ячеек следующим  образом (в таблице 5 они располагаются  в нижнем левом углу ячейки):

Таблица 5

Оценка  свободной ячейки A₁B₃ (незадействованного маршрута) отрицательная ( ₁₃ = -2), следовательно, решение не является оптимальным.

Построим  цикл для выбранной ячейки A₁B₃. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Он единственный. Направление обхода не имеет значения.

Ячейки, образующие цикл для свободной ячейки A₁B₃:

A₁B₃, A₁B₁, A₂B₁, A₂B₃

Пусть ячейка A₁B₃, для которой мы строили цикл, имеет порядковый номер один (Таблица 6).

Среди ячеек  цикла A₁B₁ , A₂B₃ , номера которых четные, найдем ячейку, обладающую наименьшим значением.

min = {50, 80} = 50

В данном случае, это ячейка A₁B₁.

Другими словами, из маршрутов доставки продукции, номера которых нечетные в данном цикле, выберем маршрут от поставщика A₁ к потребителю B₁, по которому доставляется меньше всего (50) единиц продукции. Данный маршрут мы исключим из схемы доставки продукции.

Таблица 6

От ячеек  цикла с четными номерами отнимает 50. К ячейкам с нечетными номерами прибавляем 50.

Мы вводим новый маршрут доставки продукции  от поставщика A₁ к потребителю B₃. По данному маршруту доставим 50 единиц продукции, по цене доставки 2 за единицу продукции. Общие затраты увеличатся на 2 * 50 ден. ед.

По маршруту от поставщика A₁ к потребителю B₁ мы полностью перестаем доставлять продукцию. Общие затраты уменьшатся на 1 * 50 ден. ед. От поставщика A₂ к потребителю B₁ дополнительно поставим 50 единиц продукции, по цене доставки 4 за единицу продукции. Общие затраты увеличатся на 4 * 50 ден. ед. Сократим поставку от поставщика A₂ к потребителю B₃ на 50 единиц продукции, по цене доставки 7 за единицу продукции. Общие затраты уменьшатся на 7 * 50 ден. ед.

Данные  преобразования не изменят баланс между  поставщиками и потребителями. Все  поставщики израсходуют все свои запасы, а все потребители получат  необходимое им количество продукции.

Таблица 7