Метод минимального элемента.

Шаг1. Находим самый дешевый маршрут. Их тут два (X₃₂ и X₃₄), я выбираю первый попавшийся – это X₃₂. Теперь по этому маршруту я заполняю по максимому кол-во перевозимых ед:

Потребность B2 полностью удовлетворена, поэтому X12 и X22 обнулены. У производителя осталось нераспределено 10 ед. ресурсов. Таблица после шага №1 имеет вид:

Шаг2. Снова ищем самый дешёвый маршрут в незаполненных ячейках. Теперь определен единственный - это X₃₄. Заполняем его по максимуму с производителя А3:

Производитель А3 исчерпан, поэтому X₃₁, X₃₃, X₃₅ не пригодятся – обнулены. Потребитель B4 удовлетворен не полностью – осталось 70 ед. ресурсов. Таблица имеет вид:

Шаг3. Ищем самый дешевый маршрут в незаполненных ячейках. Их два – X₂₄ и X₁₅. Выбираю первый попавшийся – X₂₄ и заполняю его максимально возможным кол-вом ресурсов:

Производитель А2 исчерпан, потребителю B4 осталось определить 10 ед ресурсов, маруруты X₂₁, X₂₃, X₂₅ не пригодятся – обнулены:

Шаг4. Ищем самый дешевый маршрут из незаполненных – это X₁₅. Загружаем его по максимуму:

Потребитель B5 удовлетворен, у производителя А1 осталось 70 ед. ресурсов:

Шаг5. Ищем самый дешевый маршрут – это X₁₄. Заполняем максимально возможным ресурсом:

Потребитель B4 удовлетворен полностью, у производителя А1 осталось 60 ед:

Шаг6. Ищем самый дешёвый маршрут из незаполненных – это X₁₁. Заполняем его по максимуму:

Потребитель B1 удовлетворен, у производителя А1 осталось 20 ед. ресурса. План имеет вид:

Шаг7. Ищем самый дешевый маршрут из незаполненных. Это маршрут X₁₃. Заполняем его оставшимся ресурсом от производителя А1:

Потребитель B3 удовлетворен, производитель А1 истощен:

Все производители истощены, потребители удовлетворены, значит задача решена. Посчитаем затраты по решению метода минимума:

Метод аппроксимации Фогеля.

Шаг1. Вычисляем разность стоимости двух элементов с минимальной стоимостью:

Максимальная разность определена однозначно =6. Заполняем Маршрут с минимальным тарифом:

Шаг2. Просчитывает разности незаполненных элементов:

Однозначно определена максимальная разность = 3 в столбце B4. Заполняем маршрут X₃₄ максимально возможным кол-вом ресурсов:

Шаг3. Ищем максимальную разность минимальных элементов в строках и в столбцах:

Однозначно определен столбец B5 с разностью =8. Заполняем минимальный элемент X₁₅:

Шаг4. Ищем максимальную разность минимальных элементов в строках и в столбцах:

Однозначно максимальная разность = 5 в столбце B1. Заполняем маршрут с минимальным тарифом в этом столбце X₁₁:

Шаг5. Ищем максимальную разность минимальных элементов в строках и в столбцах:

Определена максимальная разность 4 в столбце B3 и строке A1. Стоимость минимальных тарфиов одинакова, выбираю любой – X₂₃ и заполняю его:

Шаг6. Ищем максимальную разность минимальных элементов в строках и в столбцах:

В таблице осталось два маршрута, очевидно, что в X24 пойдет оставшийся в A2 40ед. ресурса, а в X14 оставшиеся в А1 30 ед. ресурса:

В результате получился вот такой план:

Посчитаем кол-во ед. затрат:

Итого у меня получилось три плана:

1. План северо-западного угла с 1380 ед. затрат
2. План минимального элемента с 1230 ед. затрат
3. План аппроксимации Фогеля с 1170 ед. затрат.

Самый эффективный метод – это план аппроксимации Фогеля:

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

симплекс-методом) методами.

Для изготовления двух видов продукции используется три вида сырья. При производстве единицы продукции первого вида затрачивается А1 кг сырья первого вида, А2 кг сырья второго вида и А3 кг сырья третьего вида. При производстве единицы продукции второго вида затрачивается Б1 кг сырья первого вида, Б2 кг сырья второго вида и Б3 кг сырья третьего вида. Запасы сырья первого вида составляют Запасы 1 кг, второго – Запасы 2 кг, третьего – Запасы 3 кг. Прибыль от реализации единицы продукции первого вида составляет С1 ден. ед., прибыль от реализации единицы продукции второго вида составляет С2 ден. ед. Определить оптимальный план выпуска продукции, чтобы прибыль от реализации была максимальной.

Решение.

Пусть х₁ и х₂ - это количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется

(15х₁ +7, 5 х₂) единиц ресурса 1,

(22, 5х₁ +30х₂) единиц ресурса II,

(25х₁ +20х₂) единиц ресурса III.

Так как, потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

15х₁ +7, 5х₂ ≤ 575;

22, 5х₁ +30х₂ ≤ 525;

25х₁ +20х₂ ≤ 625.

По смыслу задачи переменные х₁ ≥ 0, х₂ ≥ 0.

Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х₁ и х₂.

Суммарная прибыль А составит 45х₁ от реализации продукции А и 50х ₂ от реализации продукции В, то есть: F = 45х₁ +50х _2.

Изобразим многоугольник решений данной задачи.

В ограничениях задачи поменяем знаки неравенства на знаки равенства.

Проведем оси: на горизонтальной будут указываться значения переменной х₁, а на вертикальной — х₂.Далее рассмотрим условие неотрицательности переменных: x₁ ≥ 0 и х₂ ≥ 0. Эти два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте (т.е выше оси x₁ и правее оси х₂).

Чтобы учесть оставшиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получится система уравнений прямых:

15х₁ +7, 5х₂ = 575; y1

22, 5х₁ +30х₂ = 525; y2

25х₁ +20х₂ = 625. y3

а затем на плоскости провести эти прямые.

Теперь добавим вектор f = 45х₁ +50х₂à max

По графику видно, что вектор f пересекается с функцией y1 в самом верхнем правом углу, значит для максимума необходимо найти x1 и x2 при пересечении вектора и этой функции.

15х₁ +7, 5х₂ = 575

45х₁ +50х ₂=0

максимальное значение линейной функции равно:

F_max = 30*16, 09 + 40*19, 64 = 1232, 80.

Итак, F_max = 1232, 80 при оптимальном решении х₁ = 16, 09, х₂ = 19, 64, т. е. максимальная прибыль в 1232, 80 ден. ед. может быть достигнута при производстве 16, 09 единиц продукции А и 19, 64 единиц продукции В.

Ответ: F_max = 1232, 80 при х₁ = 16, 09, х₂ = 19, 64.