Решение отимезированых задачь ленейных моделей с помощбю excel

В результате получим новый опорный план. 12345Запасы1871214[23]52322101218[64]6[42]1063854[44]1334442[11]1[10]8[68]9[31]13120Потребности111011211842Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v4 = 14; 0 + v4 = 14; v4 = 14 u2 + v4 = 18; 14 + u2 = 18; u2 = 4 u2 + v5 = 6; 4 + v5 = 6; v5 = 2 u4 + v4 = 9; 14 + u4 = 9; u4 = -5 u4 + v1 = 2; -5 + v1 = 2; v1 = 7 u4 + v2 = 1; -5 + v2 = 1; v2 = 6 u4 + v3 = 8; -5 + v3 = 8; v3 = 13 u3 + v3 = 4; 13 + u3 = 4; u3 = -9 v1=7v2=6v3=13v4=14v5=2u1=0871214[23]5u2=42101218[64]6[42]u3=-9854[44]133u4=-52[11]1[10]8[68]9[31]13Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(1;3): 0 + 13 > 12; ∆13 = 0 + 13 - 12 = 1 (2;1): 4 + 7 > 2; ∆21 = 4 + 7 - 2 = 9 (2;3): 4 + 13 > 12; ∆23 = 4 + 13 - 12 = 5 max(1,9,5) = 9 Выбираем максимальную оценку свободной клетки (2;1): 2 Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы1871214[23]52322[+]101218[64][-]6[42]1063854[44]1334442[11][-]1[10]8[68]9[31][+]13120Потребности111011211842Цикл приведен в таблице (2,1 → 2,4 → 4,4 → 4,1). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 1) = 11. Прибавляем 11 к объемам грузов, стоящих в плюсовых клетках и вычитаем 11 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 12345Запасы1871214[23]52322[11]101218[53]6[42]1063854[44]13344421[10]8[68]9[42]13120Потребности111011211842Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v4 = 14; 0 + v4 = 14; v4 = 14 u2 + v4 = 18; 14 + u2 = 18; u2 = 4 u2 + v1 = 2; 4 + v1 = 2; v1 = -2 u2 + v5 = 6; 4 + v5 = 6; v5 = 2 u4 + v4 = 9; 14 + u4 = 9; u4 = -5 u4 + v2 = 1; -5 + v2 = 1; v2 = 6 u4 + v3 = 8; -5 + v3 = 8; v3 = 13 u3 + v3 = 4; 13 + u3 = 4; u3 = -9 v1=-2v2=6v3=13v4=14v5=2u1=0871214[23]5u2=42[11]101218[53]6[42]u3=-9854[44]133u4=-521[10]8[68]9[42]13Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(1;3): 0 + 13 > 12; ∆13 = 0 + 13 - 12 = 1 (2;3): 4 + 13 > 12; ∆23 = 4 + 13 - 12 = 5 max(1,5) = 5 Выбираем максимальную оценку свободной клетки (2;3): 12 Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы1871214[23]52322[11]1012[+]18[53][-]6[42]1063854[44]13344421[10]8[68][-]9[42][+]13120Потребности111011211842Цикл приведен в таблице (2,3 → 2,4 → 4,4 → 4,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 53. Прибавляем 53 к объемам грузов, стоящих в плюсовых клетках и вычитаем 53 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 12345Запасы1871214[23]52322[11]1012[53]186[42]1063854[44]13344421[10]8[15]9[95]13120Потребности111011211842Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v4 = 14; 0 + v4 = 14; v4 = 14 u4 + v4 = 9; 14 + u4 = 9; u4 = -5 u4 + v2 = 1; -5 + v2 = 1; v2 = 6 u4 + v3 = 8; -5 + v3 = 8; v3 = 13 u2 + v3 = 12; 13 + u2 = 12; u2 = -1 u2 + v1 = 2; -1 + v1 = 2; v1 = 3 u2 + v5 = 6; -1 + v5 = 6; v5 = 7 u3 + v3 = 4; 13 + u3 = 4; u3 = -9 v1=3v2=6v3=13v4=14v5=7u1=0871214[23]5u2=-12[11]1012[53]186[42]u3=-9854[44]133u4=-521[10]8[15]9[95]13Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(1;3): 0 + 13 > 12; ∆13 = 0 + 13 - 12 = 1 (1;5): 0 + 7 > 5; ∆15 = 0 + 7 - 5 = 2 max(1,2) = 2 Выбираем максимальную оценку свободной клетки (1;5): 5 Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы1871214[23][-]5[+]2322[11]1012[53][+]186[42][-]1063854[44]13344421[10]8[15][-]9[95][+]13120Потребности111011211842Цикл приведен в таблице (1,5 → 1,4 → 4,4 → 4,3 → 2,3 → 2,5). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 12345Запасы1871214[8]5[15]2322[11]1012[68]186[27]1063854[44]13344421[10]89[110]13120Потребности111011211842Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v4 = 14; 0 + v4 = 14; v4 = 14 u4 + v4 = 9; 14 + u4 = 9; u4 = -5 u4 + v2 = 1; -5 + v2 = 1; v2 = 6 u1 + v5 = 5; 0 + v5 = 5; v5 = 5 u2 + v5 = 6; 5 + u2 = 6; u2 = 1 u2 + v1 = 2; 1 + v1 = 2; v1 = 1 u2 + v3 = 12; 1 + v3 = 12; v3 = 11 u3 + v3 = 4; 11 + u3 = 4; u3 = -7 v1=1v2=6v3=11v4=14v5=5u1=0871214[8]5[15]u2=12[11]1012[68]186[27]u3=-7854[44]133u4=-521[10]89[110]13Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 14∙8 + 5∙15 + 2∙11 + 12∙68 + 6∙27 + 4∙44 + 1∙10 + 9∙110 = 2363 Анализ оптимального плана. Из 1-го склада необходимо груз направить в 4-й магазин (8), в 5-й магазин (15).Из 2-го склада необходимо груз направить в 1-й магазин (11), в 3-й магазин (68), в 5-й магазин (27).Из 3-го склада необходимо весь груз направить в 3-й магазин. Из 4-го склада необходимо груз направить в 2-й магазин (10), в 4-й магазин (110) Проверим средствами Excel2 ) Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов 1234Запасы12814121092691628243319234484146815Потребности2210910423 Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 109 + 24 + 48 + 15 = 196 ∑b = 22 + 109 + 104 + 23 = 258 Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 62 (258—196). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю. Занесем исходные данные в распределительную таблицу. 1234Запасы128141210926916282433192344841468155000062Потребности2210910423 Этап I. Поиск первого опорного плана. 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Искомый элемент равен 1 Для этого элемента запасы равны 15, потребности 22. Поскольку минимальным является 15, то вычитаем его. x41 = min(15,22) = 15. 28141210969162824319234481xxx15 - 15 = 000006222 - 15 = 7109104230 Искомый элемент равен 2 Для этого элемента запасы равны 109, потребности 7. Поскольку минимальным является 7, то вычитаем его. x11 = min(109,7) = 7. 281412109 - 7 = 102x9162824x19234481xxx00000627 - 7 = 0109104230 Искомый элемент равен 2 Для этого элемента запасы равны 48, потребности 104. Поскольку минимальным является 48, то вычитаем его. x33 = min(48,104) = 48. 281412102x9162824xx2x48 - 48 = 01xxx00000620109104 - 48 = 56230 Искомый элемент равен 8 Для этого элемента запасы равны 102, потребности 109. Поскольку минимальным является 102, то вычитаем его. x12= min(102,109) = 102. 28xx102 - 102 = 0x9162824xx2x01xxx00000620109 - 102 = 756230Искомый элемент равен 9 Для этого элемента запасы равны 24, потребности 7. Поскольку минимальным является 7, то вычитаем его. x22 = min(24,7) = 7. 28xx0x9162824 - 7 = 17xx2x01xxx000006207 - 7 = 056230 Искомый элемент равен 16 Для этого элемента запасы равны 17, потребности 56. Поскольку минимальным является 17, то вычитаем его. x23 = min(17,56) = 17. 28xx0x916x17 - 17 = 0xx2x01xxx00000620056 - 17 = 39230 Искомый элемент равен 0 Для этого элемента запасы равны 62, потребности 39. Поскольку минимальным является 39, то вычитаем его. x53 = min(62,39) = 39. 28xx0x916x0xx2x01xxx0000062 - 39 = 230039 - 39 = 0230 Искомый элемент равен 0 Для этого элемента запасы равны 23, потребности 23. Поскольку минимальным является 23, то вычитаем его. x54 = min(23,23) = 23. 28xx0x916x0xx2x01xxx0000023 - 23 = 000023 - 23 = 001234Запасы12[7]8[102]1412109269[7]16[17]282433192[48]344841[15]468155000[39]0[23]62Потребности2210910423В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 2∙7 + 8∙102 + 9∙7 + 16∙17 + 2∙48 + 1∙15 + 0∙39 + 0∙23 = 1276 Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 2; 0 + v1 = 2; v1 = 2 u4 + v1 = 1; 2 + u4 = 1; u4 = -1 u1 + v2 = 8; 0 + v2 = 8; v2 = 8 u2 + v2 = 9; 8 + u2 = 9; u2 = 1 u2 + v3 = 16; 1 + v3 = 16; v3 = 15 u3 + v3 = 2; 15 + u3 = 2; u3 = -13 u5 + v3 = 0; 15 + u5 = 0; u5 = -15 u5 + v4 = 0; -15 + v4 = 0; v4 = 15 v1=2v2=8v3=15v4=15u1=02[7]8[102]1412u2=169[7]16[17]28u3=-133192[48]34u4=-11[15]468u5=-15000[39]0[23]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(1;3): 0 + 15 > 14; ∆13 = 0 + 15 - 14 = 1 (1;4): 0 + 15 > 12; ∆14 = 0 + 15 - 12 = 3 (4;2): -1 + 8 > 4; ∆42 = -1 + 8 - 4 = 3 (4;3): -1 + 15 > 6; ∆43 = -1 + 15 - 6 = 8 (4;4): -1 + 15 > 8; ∆44 = -1 + 15 - 8 = 6 max(1,3,3,8,6) = 8 Выбираем максимальную оценку свободной клетки (4;3): 6 Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 1234Запасы12[7][+]8[102][-]1412109269[7][+]16[17][-]282433192[48]344841[15][-]46[+]8155000[39]0[23]62Потребности2210910423Цикл приведен в таблице (4,3 → 4,1 → 1,1 → 1,2 → 2,2 → 2,3). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 1) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 1234Запасы12[22]8[87]1412109269[22]16[2]282433192[48]34484146[15]8155000[39]0[23]62Потребности2210910423Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 2; 0 + v1 = 2; v1 = 2 u1 + v2 = 8; 0 + v2 = 8; v2 = 8 u2 + v2 = 9; 8 + u2 = 9; u2 = 1 u2 + v3 = 16; 1 + v3 = 16; v3 = 15 u3 + v3 = 2; 15 + u3 = 2; u3 = -13 u4 + v3 = 6; 15 + u4 = 6; u4 = -9 u5 + v3 = 0; 15 + u5 = 0; u5 = -15 u5 + v4 = 0; -15 + v4 = 0; v4 = 15 v1=2v2=8v3=15v4=15u1=02[22]8[87]1412u2=169[22]16[2]28u3=-133192[48]34u4=-9146[15]8u5=-15000[39]0[23]Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij(1;3): 0 + 15 > 14; ∆13 = 0 + 15 - 14 = 1 (1;4): 0 + 15 > 12; ∆14 = 0 + 15 - 12 = 3 max(1,3) = 3 Выбираем максимальную оценку свободной клетки (1;4): 12 Для этого в перспективную клетку (1;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 1234Запасы12[22]8[87][-]1412[+]109269[22][+]16[2][-]282433192[48]34484146[15]8155000[39][+]0[23][-]62Потребности2210910423Цикл приведен в таблице (1,4 → 1,2 → 2,2 → 2,3 → 5,3 → 5,4). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках и вычитаем 2 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 1234Запасы12[22]8[85]1412[2]109269[24]16282433192[48]34484146[15]8155000[41]0[21]62Потребности2210910423Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v1 = 2; 0 + v1 = 2; v1 = 2 u1 + v2 = 8; 0 + v2 = 8; v2 = 8 u2 + v2 = 9; 8 + u2 = 9; u2 = 1 u1 + v4 = 12; 0 + v4 = 12; v4 = 12 u5 + v4 = 0; 12 + u5 = 0; u5 = -12 u5 + v3 = 0; -12 + v3 = 0; v3 = 12 u3 + v3 = 2; 12 + u3 = 2; u3 = -10 u4 + v3 = 6; 12 + u4 = 6; u4 = -6 v1=2v2=8v3=12v4=12u1=02[22]8[85]1412[2]u2=169[24]1628u3=-103192[48]34u4=-6146[15]8u5=-12000[41]0[21]Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij. Минимальные затраты составят: F(x) = 2∙22 + 8∙85 + 12∙2 + 9∙24 + 2∙48 + 6∙15 + 0∙41 + 0∙21 = 1150 Анализ оптимального плана. Из 1-го склада необходимо груз направить в 1-й магазин (22), в 2-й магазин (85), в 4-й магазин (2) Из 2-го склада необходимо весь груз направить в 2-й магазин Из 3-го склада необходимо весь груз направить в 3-й магазин Из 4-го склада необходимо весь груз направить в 3-й магазин Потребность 3-го магазина остается неудовлетворенной на 41 ед. Оптимальный план является вырожденным, так как базисная переменная x53=0. Потребность 4-го магазина остается неудовлетворенной на 21 ед. Оптимальный план является вырожденным, так как базисная переменная x54=0.Проверим решение средствами ExcelЗаключениеВ данной работе применены различные способы решения задач линейного программирования: графический, симплексный. Также решены транспортные задачи с помощью метода потенциалов. Все эти методы достаточно трудоемки и могут привести к вычмслительным ошибкам и неверным результатамОблегчить решение можно, применяя пакет анализа Excel. В результате применения инструмента «Поиск решения» результат каждой задачи был проверен.Список использованной литературыБагриновский К.А. Экономико-математические методы и модели (микроэкономика): Учеб.пособие для вузов / К.А. Багриновский, В.М. Матюшок. – М.: Изд-во Российского университета дружбы народов, 2009. – 183 с.Исследование операций в экономике: Учеб. пособие для вузов / Под ред. Н.Ш. Кремера. – М.: Банки и биржи/ЮНИТИ, 2007. – 407 с.Карасев А.И. Математические методы и модели в планировании / А.И. Карасев, Н.Ш. Кремер, Т.И. Савельев. – М.: Экономика, 2008. – 240 с.