Методы оптимальных решений

- ...

Задание 1. Задача о выпуске продукции при ограниченных ресурсах.
Предположим, что для производства двух видов продукции А и В используются сырье трех сортов. При этом на изготовление единицы изделия вида А расходуется a1 кг сырья первого сорта, a2 кг сырья второго сорта, a3 кг сырья третьего сорта. На изготовление единицы изделия вида В расходуется b1 кг сырья первого сорта, b2 кг сырья второго сорта, b3 кг сырья третьего сорта. На складе фабрики имеется всего c1 кг сырья первого сорта, c2 кг сырья второго сорта, c3 кг сырья третьего сорта. От реализации единицы готовой продукции вида А фабрика имеет прибыль α руб., а от продукции вида В прибыль составляет β руб. Определить объемы выпуска продукций вида А и вида В, при которых фабрика получит максимальную прибыль.
Записать задачу в видезадачи линейного программирования и решить ее графическим методом. Дать экономическую интерпретацию полученного решения.

Вариант

1 6 3 1 10 9 5 735 765 455 4 8
Задание 2. Транспортная задача.
Имеются три (четыре) пункта А1, А2, А3, (А4) поставки однородного груза и четыре (три) пункта В1, В2, В3, (В4) потребления этого груза. На пунктах находится груз соответственно в количестве а1, а2, а3, (а4) тонн. В пункты В1, В2, В3, (В4) требуется доставить соответственно b1, b2, b3,( b4) тонн груза. Цены перевозок (стоимости провоза единицы груза) в условных единицах между пунктами поставки и пунктами потребления приведены в матрице-таблице C.
Найти такой план перевозки груза к потребителям от поставщиков, чтобы общие затраты по перевозкам были минимальными.

Вариант 1

Начальный план перевозок составить методом «северо-западного» угла.
а1=150, а2=130, а3=100, а4=160; b1=220, b2=200, b3=120;
С=(■(■()&■()&■()@10&26&&12&12))

-

Вариант 1Начальный план перевозок составить методом «северо-западного» угла.а1=150, а2=130, а3=100, а4=160; b1=220, b2=200, b3=120;С=121112231512102618161212Решение: Математическая модель транспортной задачи: F = ∑∑cijxij, (1) при условиях: ∑xij = ai, i = 1,2,…, m, (2) ∑xij = bj, j = 1,2,…, n, (3) Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов 123Запасы1121215150211231213031026181004161212160Потребности220200120Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 150 + 130 + 100 + 160 = 540 ∑b = 220 + 200 + 120 = 540 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу. 123Запасы1121215150211231213031026181004161212160Потребности220200120Этап I. Поиск первого опорного плана. 1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается заполняться с верхнего левого угла. Искомый элемент равен 12 Для этого элемента запасы равны 150, потребности 220. Поскольку минимальным является 150, то вычитаем его. x11 = min(150,220) = 150. 12xx150 - 150 = 0112312130102618100161212160220 - 150 = 702001200 Искомый элемент равен 11 Для этого элемента запасы равны 130, потребности 70. Поскольку минимальным является 70, то вычитаем его. x21 = min(130,70) = 70. 12xx0112312130 - 70 = 60x261810016121216070 - 70 = 02001200 Искомый элемент равен 23 Для этого элемента запасы равны 60, потребности 200. Поскольку минимальным является 60, то вычитаем его. x22 = min(60,200) = 60. 12xx01123x60 - 60 = 0x26181001612121600200 - 60 = 1401200 Искомый элемент равен 26 Для этого элемента запасы равны 100, потребности 140. Поскольку минимальным является 100, то вычитаем его. x32 = min(100,140) = 100. 12xx01123x0x26x100 - 100 = 01612121600140 - 100 = 401200 Искомый элемент равен 12 Для этого элемента запасы равны 160, потребности 40. Поскольку минимальным является 40, то вычитаем его. x42 = min(160,40) = 40. 12xx01123x0x26x0161212160 - 40 = 120040 - 40 = 01200 Искомый элемент равен 12 Для этого элемента запасы равны 120, потребности 120. Поскольку минимальным является 120, то вычитаем его. x43 = min(120,120) = 120. 12xx01123x0x26x0161212120 - 120 = 000120 - 120 = 00 123Запасы112[150]1215150211[70]23[60]1213031026[100]1810041612[40]12[120]160Потребности220200120В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 6. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 12*150 + 11*70 + 23*60 + 26*100 + 12*40 + 12*120 = 8470 Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0. u1 + v1 = 12; 0 + v1 = 12; v1 = 12 u2 + v1 = 11; 12 + u2 = 11; u2 = -1 u2 + v2 = 23; -1 + v2 = 23; v2 = 24 u3 + v2 = 26; 24 + u3 = 26; u3 = 2 u4 + v2 = 12; 24 + u4 = 12; u4 = -12 u4 + v3 = 12; -12 + v3 = 12; v3 = 24 v1=12v2=24v3=24u1=012[150]1215u2=-111[70]23[60]12u3=21026[100]18u4=-121612[40]12[120]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij (1;2): 0 + 24 > 12; ∆12 = 0 + 24 - 12 = 12 (1;3): 0 + 24 > 15; ∆13 = 0 + 24 - 15 = 9 (2;3): -1 + 24 > 12; ∆23 = -1 + 24 - 12 = 11 (3;1): 2 + 12 > 10; ∆31 = 2 + 12 - 10 = 4 (3;3): 2 + 24 > 18; ∆33 = 2 + 24 - 18 = 8 max(12,9,11,4,8) = 12 Выбираем максимальную оценку свободной клетки (1;2): 12 Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 123Запасы112[150][-]12[+]15150211[70][+]23[60][-]1213031026[100]1810041612[40]12[120]160Потребности220200120Цикл приведен в таблице (1,2; 1,1; 2,1; 2,2; ). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 60. Прибавляем 60 к объемам грузов, стоящих в плюсовых клетках и вычитаем 60 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 123Запасы112[90]12[60]15150211[130]231213031026[100]1810041612[40]12[120]160Потребности220200120Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.