РЕШЕНИЕ Составим математическую модель задачи Пусть x1 х2 соответственно — количество (в кг) печенья «Привет» и «Шоколадное»

РЕШЕНИЕ. Составим математическую модель задачи. Пусть x1, х2 соответственно — количество (в кг) печенья «Привет» и «Шоколадное», которую производит пекарня. По смыслу задачи эти переменные неотрицательны. Тогда f(x1, x2) = 30 x1 + 45 x2 – совокупная прибыль от продажи произведенной продукции, которую требуется максимизировать. Подсчитаем затраты сырья (в кг): Сырье «мука»: 0.4 х1 + 0.3 х2, по условию на складе 110 кг муки. Сырье «маргарин»: 0.2 х1 + 0.3 х2, по условию на складе 30 кг маргарина. Сырье «сахар»: 0.1 х1 + 0.15 х2, по условию на складе 50 кг сахара. Сырье «какао»: 0.05 х2, по условию на складе 2 кг какао.
Пришли к задаче линейного программирования:
f(x1, x2) = 30 x1 +45 x2 → max,
0.4 х1 + 0.3 х2 ≤ 110,
0.2 х1 + 0.3 х2 ≤ 30,
0.1 х1 + 0.15 х2 ≤ 50
0.05 х2 ≤ 2
x1 ≥ 0, x2 ≥ 0
Решим задачу линейного программирования графическим методом.
Построим область допустимых решений, т.е. решим графически систему неравенств.
 Рассмотрим целевую функцию задачи F = 30 x1+45 x2 → max. Построим прямую, отвечающую значению функции F = 0: F = 30 x1+45 x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (30; 45). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. 

Прямая F(x) = const пересекает область на отрезке АВ.
Найдем координаты точки А. Так как точка А получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:
Найдем координаты точки В. Так как точка В получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:
Откуда найдем максимальное значение целевой функции:

Решение:

максимальная прибыль составит 4500 рублей.

РЕШЕНИЕ. Составим математическую модель задачи. Пусть x1, х2, х3 соответственно — количество единиц продуктов I, II, III. По смыслу задачи эти переменные неотрицательны. Тогда f(x1, x2, x3) = 2 x1 + 3 x2 + 2.5 x3 – совокупные затраты от покупки продуктов, которые требуется минимизировать. Подсчитаем содержание веществ в продуктах: Вещество А : 2 х1 + 1 х2 + 3 х3, по условию должно быть не менее 3 ед. Вещество В: 1 х1 + 2 х2 + 1,5 х3, по условию должно быть не менее 4 ед. Вещество С : 3 х1 + 4 х2 + 2 х3, по условию должно быть не менее 6 ед.
Пришли к задаче линейного программирования:
f(x1, x2, x3) = 2 x1 + 3 x2 + 2.5 x3 → min,
2 х1 + х2 + 3 х3≥ 3,
х1 + 2 х2 + 1.5 х3≥ 4,
3 х1 + 4 х2 + 2 х3≥ 6
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0
Решим задачу линейного программирования симплекс методом.
Переходим к канонической форме.2×1+x2+3×3-x4 = 3×1+2×2+1.5×3-x5 = 43×1+4×2+2×3-x6 = 6Приведем систему к единичной матрице методом жордановских преобразований.В качестве базовой переменной можно выбрать x4, х5, х6.
-2 -1 -3 1 0 0 -3
-1 -2 -1.5 0 1 0 -4
-3 -4 -2 0 0 1 -6
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,5,6).Выразим базисные переменные через остальные:x4 = 2×1+x2+3×3-3×5 = x1+2×2+1.5×3-4×6 = 3×1+4×2+2×3-6Подставим их в целевую функцию:F(X) = 2×1+3×2+2.5×3Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.Вместо переменной x6 следует ввести переменную x3.
Базис B x1 x2 x3 x4 x5 x6
x4 6 5/2 5 0 1 0 -3/2
x5 1/2 1.25 1 0 0 1 -0.75
x3 3 3/2 2 1 0 0 -1/2
F(X0) -15/2 -1.75 -2 0 0 0 1.25
Выразим базисные переменные через остальные:x4 = -5/2×1-5×2+3/2×6+6×5 = -1.25×1-x2+0.75×6+1/2×3 = -3/2×1-2×2+1/2×6+3Подставим их в целевую функцию:F(X) = 2×1+3×2+2.5(-3/2×1-2×2+1/2×6+3) = -1.75×1-2×2+1.25×6+7.55/2×1+5×2+x4-3/2×6=61.25×1+x2+x5-0.75×6=1/23/2×1+2×2+x3-1/2×6=3При вычислениях значение Fc = 7.5 временно не учитываем.Решим систему уравнений относительно базисных переменных: x4, x5, x3Полагая, что свободные переменные равны 0, получим первый опорный план: X0 = (0,0,3,6,1/2,0)
Базис B x1 x2 x3 x4 x5 x6
x4 6 5/2 5 0 1 0 -3/2
x5 1/2 1.25 1 0 0 1 -0.75
x3 3 3/2 2 1 0 0 -1/2
F(X0) 0 1.75 2 0 0 0 -1.25
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент.2-ая строка является ведущей.Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x2.Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x4 7/2 -3.75 0 0 1 -5 2.25
x2 1/2 1.25 1 0 0 1 -0.75
x3 2 -1 0 1 0 -2 1
F(X1) -1 -0.75 0 0 0 -2 0.25
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент.1-ая строка является ведущей.Разрешающий элемент равен (2.25) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x6.Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6
x6 1.56 -1.67 0 0 0.44 -2.22 1
x2 1.67 0 1 0 0.33 -0.67 0
x3 0.44 0.67 0 1 -0.44 0.22 0
F(X2) -1.39 -0.33 0 0 -0.11 -1.44 0
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.Оптимальный план: x1 = 0, x2 = 1.667, x3 = 0.444F(X) = 2•0 + 3•1.667 + 2.5•0.444 = 6.111Построим двойственную задачу.
Z(y1, y2, y3) = 3 y1 + 4 y2 + 6 y3 → max,
2 y1+y2+3 y3 ≤ 2
y1+2y2+4 y3 ≤ 3
3 y1+1.5y2+2 y3 ≤ 2.5
По теореме двойственности выполняется равенство , где . Тогда

Читайте также:  Определите средний процент брака в целом по предприятию.

Метод ветвей и границ
Решаем задачу (1) графическим методом.
Построим область допустимых решений, т.е. решим графически систему неравенств.
 
Рассмотрим точку А. Так как точка А получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:
Откуда найдем значение целевой функции:
 
x2=3.5→исключаем полосу 3<x2≤4
Получаем задачу (2):

Решаем задачу (2) графическим методом.
Построим область допустимых решений, т.е. решим графически систему неравенств.

Рассмотрим точку C. Так как точка C получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:
Откуда найдем значение целевой функции:
 
x1=4.25→исключаем полосу x1>4
Получаем задачу (3):

Решаем задачу (3) графическим методом.
Построим область допустимых решений, т.е. решим графически систему неравенств.

Так как функция достигает экстремального значения на границе области, найдем координаты вершин многоугольника.
Рассмотрим точку А1. Так как точка А1 получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых
Откуда найдем значение целевой функции:
 
Рассмотрим точку А2. Так как точка А2 получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:
Откуда найдем значение целевой функции:
 
Рассмотрим точку В. Так как точка В получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим:
Откуда найдем значение целевой функции:
 
Рассмотрим точку C1. Так как точка C1 получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых.
Откуда найдем значение целевой функции:
 
Рассмотрим точку D. Так как точка D получена в результате пересечения прямых , то ее координаты удовлетворяют уравнениям этих прямых.
Откуда найдем значение целевой функции:
 
Максимальному значению функции Fmax = 32 соответствует точка В(4;2).

Проверим необходимое и достаточное условие разрешимости задачи.∑a = 100 + 100 + 100 = 300∑b = 30 + 60 + 80 + 80 + 20 = 270Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 30 (300—270). Тарифы перевозки единицы груза к этому магазину полагаем равны нулю.Занесем исходные данные в распределительную таблицу.

B1 B2 B3 B4 B5 B6 Запасы
A1 4 4 6 8 0 0 100
A2 0 7 4 7 4 0 100
A3 6 7 0 3 5 0 100
Потребности 30 60 80 80 20 30

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

Пункты В1
В2
В3 В4
В5 В6
Запасы
А1
4 4 4
6 2 8 1 0

100 α1=0

60

20
20

А2

7 3 4 0 7
4 4 0
100 α2=0

30

60

10

А3 6 10 7 7 0
3
5 9 0 4 100 α3=-4

80
20

Заявки 30 60 80 80 20 30

β1=0 β2=4 β3=4 β4=7 β5=0 β6=0

Значение целевой функции для этого опорного плана равно:F(x) = 4*60 + 0*20 + 0*20 + 0*30 + 7*60 + 0*10 + 0*80 + 3*20 = 720
2. Найдем потенциалы, составляя для каждой базисной клетки уравнение

Читайте также:  Непрерывная случайная величина X задана функцией распределения F(x)

З. Для каждой свободной клетки вычислим относительные оценки:

(Помещаем эти оценки в правые верхние углы соответствующих клеток.)
4. Поскольку все QUOTE , задача решена. Оптимальный план перевозок:
x12=60, x15=20, x21=30, x24=60, x33=80, x34=20
имеет суммарную стоимость
F(Х) = 4*60 + 0*20 + 0*20 + 0*30 + 7*60 + 0*10 + 0*80 + 3*20 = 720.
От 1-го поставщика необходимо направить 60 единиц груза 2-му потребителю и 20 единиц груза 5-му потребителю.
От 2-го поставщика необходимо направить 30 единиц груза 1-му потребителю и 60 единиц груза 4-му потребителю.
От 3-го поставщика необходимо направить 80 единиц груза 3-му потребителю и 20 единиц груза 4-му потребителю.У 1-ого поставщика остался невостребованным груз в количестве 20 ед.У 2-ого поставщика остался невостребованным груз в количестве 10 ед.

1). Составим обобщенную функцию Лагранжа:

2). Выпишем необходимые условия экстремума первого порядка

3). Решим систему для двух случаев.
В первом случае . Поэтому из первых двух уравнений следует . Однако, это противоречит требованию о существовании ненулевого вектора .
Во втором случае . Перепишем систему, поделив уравнения на с заменой на :

Из условия следует:
а)
Тогда система не имеет решений.
б)
Тогда получим систему
Из второго уравнения , из третьего уравнения .
Получим новую систему

Находим решения системы:
x1=-1.979, x2=-3.476
x1=-1.979, x2=3.476
x1=2.021, x2=-3.452
x1=2.021, x2=3.452
x1=3.979, x2=-0.410
x1=3.979, x2=0.410
Решая исходную систему, находим значения для стационарных точек.
А1(-1.979, -3.476)
А2 (-1.979, 3.476)
А3 (2.021, -3.452)
А4 (2.021, 3.452)
А5 (3.979, 0.410)
А6 (3.979, -0.410)
В точках А2, А4, А6 выполняется необходимое условие минимума.
В точках А1, А3, А5 выполняется необходимое условие максимума.
4). Проверим достаточные условия экстремума:
В точках Аi ограничение является активным, так как , но число активных ограничений в каждой точке меньше числа переменных (х1, х2), поэтому достаточное условие первого порядка не выполняется. Проверим достаточное условие второго порядка.

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

Критерий Байеса.
По критерию Байеса за оптимальные принимается та стратегия (чистая) Ai, при которой максимизируется средний выигрыш a или минимизируется средний риск r.
Считаем значения ∑(hijqj)
∑(h1,jqj) = 5*0.25 + 6*0.25 + 4*0.25 + 9*0.25 = 6∑(h2,jqj) = 5*0.25 + 5*0.25 + 5*0.25 + 5*0.25 = 5∑(h3,jqj) = 1*0.25 + 10*0.25 + 2*0.25 + 14*0.25 = 6.75
B=max(6; 5; 6.75)=6.75Вывод: выбираем стратегию A3.
Критерий Вальда.По критерию Вальда за оптимальную принимается чистая стратегия, которая в наихудших условиях гарантирует максимальный выигрыш, т.е.

Aj
Пj

П1
П2
П3 П4

A1 5 6 4 9 4
A2 5 5 5 5 5
A3 1 10 2 14 1
W=max(4; 5; 1)=5Вывод: выбираем стратегию A2.

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...