Составление математической модели двойственной задачи

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

1. Найти графическим способом максимум и минимум функции при следующих ограничениях:

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

Строим в системе координат х₁ох₂ прямые

(1)

(2)

(3)

(4)

Находим полуплоскости, определяемые системой. Так как неравенства системы выполняется для любой точки из соответствующей полуплоскости, то их достаточно проверить для какой-либо одной точки. Используем точку (0;0). Подставим её координаты в первое неравенство системы. Т.к. , то неравенство определяет полуплоскость, не содержащую точку (0;0). Аналогично определяем остальные полуплоскости. Находим множество допустимых решений как общую часть полученных полуплоскостей - это заштрихованная область.

Строим вектор и перпендикулярно к нему прямую нулевого уровня.

Рис. 1

(5)

Перемещая прямую (5) в направлении вектора и видим, что у области максимальная точка будет в точке А пересечения прямой (3) и прямой (2). Находим решение системы уравнений:

Значит, получили точку (13;11) и .

Перемещая прямую (5) в направлении вектора и видим, что у области минимальная точка будет в точке В пересечения прямой (1) и прямой (4). Находим решение системы уравнений:

Значит, получили точку (6;6) и .

2. Мебельная фирма производит комбинированные шкафы и компьютерные столики. Их производство ограничено наличием сырья (высококачественных досок, фурнитуры) и временем работы обрабатывающих их станков. Для каждого шкафа требуется 5 м² досок, для стола - 2 м². На один шкаф расходуется фурнитуры на 10$, на один столик также на 8$. Фирма может получать от своих поставщиков до 600 м² досок в месяц и фурнитуры на 2000$. Для каждого шкафа требуется 7 часов работы станков, для стола - 3 часа. В месяц возможно использовать всего 840 часов работы станков.

Сколько комбинированных шкафов и компьютерных столиков фирме следует выпускать в месяц для получения максимальной прибыли, если один шкаф приносит 100$ прибыли, а каждый стол - 50$?

1. Составить математическую модель задачи и решить её симплексным методом.

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

3. Установить степень дефицитности используемых ресурсов и обосновать рентабельность оптимального плана.

4. Исследовать возможности дальнейшего увеличения выпуска продукции в зависимости от использования каждого вида ресурсов.

5. Оценить целесообразность введения нового вида продукции - книжных полок, если на изготовление одной полки расходуется 1 м² досок и фурнитуры на 5$,и требуется затратить 0,25 часа работы станков и прибыль от реализации одной полки составляет 20$.

1. Построим математическую модель для данной задачи:

Обозначим через x₁ - объём производства шкафов, а х₂ - объём производства столиков. Составим систему ограничений и функцию цели:

Задачу решаем симплекс-методом. Запишем её в каноническом виде:

Запишем данные задачи в виде таблицы:

Таблица 1

Т.к. теперь все дельта больше нуля, то дальнейшее увеличение значения функции цели f невозможно и мы получили оптимальный план:

Х=(27,69;215,38;30,77;0;0)

2. Составим двойственную задачу.

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

По экономическому смыслу искомые цены неотрицательны у_i?0 (i=1,2,3).

Двойственную задачу можно решить, используя последнюю симплекс-таблицу. В её столбцах записана исходная задача, а в строках - двойственная. Найдём оптимальный план двойственной задачи. Решением задачи будет: у₁=0, у₂=1,92, у₃=11,54. Тогда .

3. Укажем наиболее дефицитный ресурс. Из решения исходной задачи определим потребность ресурсов при оптимальном плане: первый ресурс избыточен, поэтому его увеличение ни к чему не приведёт (у₁=0), увеличение второго ресурса на единицу ведёт к увеличению целевой функции на1,92; увеличение третьего ресурса на единицу ведёт к увеличению целевой функции на 11,54. Значит, дефицитными являются второй и третий ресурсы (фурнитура и время работы станков).

Рентабельность всей продукции находится по формуле

,

где Р_п- рентабельность продукции,

П - прибыть от реализации,

С - себестоимость.

4. Раскроем состав двойственных переменных:

Экономически это означает, что при увеличении количества досок на единицу выпуск шкафов и столов не изменится, остаток избыточного ресурса (досок) увеличится на 1. Целевая функция изменится на 11.54.

Экономически это означает, что при увеличении количества фурнитуры на единицу выпуск шкафов увеличится на 0,04, столов увеличится на 0,272, остаток избыточного ресурса уменьшится на 0,12. Целевая функция изменится на 0.98.

Экономически это означает, что при увеличении времени работы на единицу выпуск шкафов уменьшится на 0,77, столов уменьшится на 0,38, остаток избыточного ресурса увеличится на 0.31. Целевая функция изменится на -13.04.

5. Оценим эффективность выпуска новой продукции - книжных полок. Стоимость ресурсов, расходуемых на единицу этой продукции, составит

Выручка же за каждую единицу равна 20$. Значит, выпускать эту продукцию целесообразно.

3. Решить матричную игру с платёжной матрицей

Составим двойственные задачи. Прежде всего проверим, не имеет ли игра седловой точки. Находим: .

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

Решим вторую задачу. Приведём задачу к каноническому виду:

Переменные у₅, у₆, у₇ ,у₈- базисные. Составим симплекс-таблицу:

Таблица 2

Оптимальный план у^*=, , получаем цену игры и компоненты q_j^* оптимальной смешанной стратегии q^* игрока В: q₁^*=vy₁^*= , q₂^*=, q₃^*=0, q₄^*=0.

Их симплекс -таблицы выпишем решение двойственной задачи: х^*=.

Теперь находим компоненты р_j^* оптимальной смешанной стратегии р^* игрока А: р₁^*=vх₁^*=, р₂^*=0, р₃^*=, р₄^*=0.

Итак, решение игры: р^*=, q^*=, .

4. На участках климатических зон I, II и III предполагается выращивать культуры: пшеницы, картофель, сою, кукурузу. Урожайность культур зависит от погодных условий летом. Вероятности наступления тех или иных погодных условий для зон I и II известны. Для зоны III их спрогнозировать невозможно. Значения прибыли, рассчитанные на основе накопившегося опыта для различных погодных условий, приведены в таблице. Используя различные критерии статистических игр (Байеса, Лапласа, Вальда, Сэвиджа и Гурвица(для и для )) дать рекомендации по выращиванию культур в различных зонах

Таблица 3

В качестве оптимальной по критерию Байеса принимается чистая стратегия А_i, при которой максимизируется средний выигрыш = = = 393,75 для I зоны и для II зоны = = = 383.33.

Таблица 4

Оптимальная стратегия в данном случае для первой и второй зоны вторая.

Для критерия Лапласа q_i = . Тогда = = = 283,33. Тогда оптимальная стратегия в данном случае первая или четвертая для двух зон.

Найдем оптимальную стратегию по Вальду

Значит, по Вальду оптимальная стратегия для двух зон вторая.

По критерию Гурвица находим

Для

функция матрица статистический

Таблица 5

max{425; 4700;550;450}= 550. Тогда оптимальная стратегия в данном случае третья.

Для

Таблица 6

max{250; 260;200;100}= 260. Тогда оптимальная стратегия в данном случае вторая.

Для критерия Сэвиджа найдем риски r_ij.

Таблица 7

Тогда находим = min{400;450;350;250} = 250 = r₄. Тогда оптимальной стратегией является четвертая.

5. Составить оптимальный план перевозок зерна из четырёх районов А₁, А₂, А₃, А₄ республики, к которых запасы составляют соответственно 100, 50, 50 и 100 тыс. ц., на пять элеваторов В₁, В₂, В₃, В₄, В₅, мощности которых равны соответственно 50, 30, 20, 100 и 50 тыс. ц. Затраты на перевозку одного ц. зерна из районов на элеваторы приводятся в следующей таблице. Составить оптимальный план перевозок зерна и найти его стоимость. Решить задачу методом потенциалов, составить первоначальный план по методу наименьших тарифов.

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

Поскольку запасы грузов превышают мощности элеваторов, вводится фиктивный потребитель, спрос которого b₆==300-250=50. Все тарифы фиктивного потребителя равны нулю: с_5i=0. Имеем транспортную задачу закрытого типа, которую решаем методом потенциалов.

Запишем условие в таблице:

Таблица 8

Загрузка начинается с клетки, которой соответствует наименьший тариф с_ij из всей матрицы тарифов. Возьмём клетку (5;2) х₅₂=0. В клетку (5;2) вписываем число с₅₂=min(40;120)=40 и исключаем из дальнейшего рассмотрения пятую строку. Из оставшихся тарифов наименьший возьмём для клетки (1;5) х₁₅ =1.В клетку (1;5) вписываем число с₁₅ =min(50;100)=50 и исключаем из дальнейшего рассмотрения пятый столбец. Из оставшихся тарифов наименьший для клетки (4;1), х₄₁=1. В клетку (4;1) вписываем min(50;100)=50. Исключаем из дальнейшего рассмотрения первый столбец. Из оставшихся тарифов наименьший для клетки (2;2), х₂₂=1. В клетку (2;2) вписываем min(120;50)=50. Исключаем из дальнейшего рассмотрения вторую строку. Из оставшихся тарифов наименьший для клетки (4;3), х₄₃=2. В клетку (4;3) вписываем min(20;100-50)=20. Исключаем из дальнейшего рассмотрения третий столбец. Из оставшихся тарифов наименьший для клетки (3;4), х₃₄ =2 вписываем min(100;50)=50. Исключаем из дальнейшего рассмотрения третью строку. Из оставшихся тарифов наименьший для клетки (4;2), х₄₂ =3 вписываем min(120-50-40;100-50-20)=30. Исключаем из дальнейшего рассмотрения четвертую строку. Из оставшихся тарифов наименьший для клетки (1;4), х₁₄ =3 вписываем min(100-50;100-50)=50. Исключаем из дальнейшего рассмотрения четвертый столбец и первую строку. В результате полного распределения грузов получаем исходное опорное решение. В таблице получен вырожденный план, т.к. число загруженных клеток не удовлетворяет условию m+n-1=4+6-1=9. Добавим клетку с нулевой перевозкой х₃₆ =0. Для определения потенциалов поставщиков и потребителей имеем систему уравнений:

Поскольку число уравнений системы на единицу меньше числа потенциалов (система неопределённая), для её решения одному из потенциалов придаётся произвольное значение. Положим u₁=0. Все остальные потенциалы определяются однозначно. Найденные потенциалы поставщиков и потребителей указаны справа и внизу в клетках таблицы:

Таблица 9

Определяем оценки свободных клеток: д₁₁ = 4-(0+1)=3, д₁₂=5-(0+3)=2, д₁₃=4-(2+0)=2, д₂₁=4-(1-2)=5, д₂₃=6-(2-2)=6, д₂₄=2-(3-2)=1, д₂₅=2-(1-2)=3, д₃₁=5-(1-1)=5, д₃₂=5-(3-1)=3, д₃₃=3-(2-1)=2, д₃₅=1-(1-1)=1, д₄₄=3-(3+0)=0, д₄₅=1-(0+1)=0, д₅₁=0-(1-3)=2, д₅₃=0-(2-3)=1, д₅₅=0-(1-3)=2.

F(X₁ )=50*3+50*1+50*1+50*2+50*1+30*3+20*2+40*0+0*0=530

Полученный план оптимален и единственный. Среди оценок не имеется отрицательных.

Для этого плана значение целевой функции

F(X^*)=50*3+50*1+50*1+50*2+50*1+30*3+20*2+40*0+0*0=530

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