Метод Северо-западного угла. Метод минимального элемента. Метод потенциалов. Симплекс-метод

Фрагмент работы:

Метод Северо-западного угла. Метод минимального элемента. Метод по…

I раздел

Метод Северо-западного угла

Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причём максимально возможным числом: либо полностью вывозится груз из Ai, либо полностью удовлетворяется потребность Bj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы Ai и не удовлетворяются потребности Bj. В заключении проверяют, что найденные компоненты плана Xij удовлетворяют горизонтальным и вертикальным уравнениям и что выполняется условие невырожденности плана.

Перед заполнением проверяем задачу на правильность баланса.

…

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

Ищем минимальную стоимость перевозок и ставим максимально возможное количество груза.

…

Метод потенциалов

За основу берем метод минимального элемента. Расставляем потенциалы ui и vi. Для нахождения потенциалов у оставшихся строк (столбцов) используется формула…

II раздел

Симплекс-метод

Бригада осмотрщиков обрабатывает грузовые и пассажирские поезда. На обработку одного грузового поезда заняты 6 человек, одного пассажирского – 3 человека. Всего в бригаде 36 человек. За смену бригада может обработать не более 4 грузовых и не более 6 пассажирских поездов. За обработку одного грузового поезда бригада получает 10 рублей прибыли, одного пассажирского – 15 рублей. Определить, какое количество грузовых и пассажирских поездов должна обработать бригада, чтобы получить максимальную прибыль?

Математическая постановка задачи

…

Графический метод

Построим граничные прямые в одной системе координат и определим область допустимы решений (ОДР).

…

Исходя из рисунка видно, что все возможные планы заключены в многоугольнике OABCD. Для нахождения оптимального плана отобразим на графике целевую функцию Z в виде линий уровня. При этом нулевому значению целевой функции будет соответствовать точка (0;0). Будем перемещать линию уровня параллельно самой себе в направлении перпендикулярного вектора (10;15), насколько это возможно. При этом видно, что точкой выхода из области допустимых решений будет точка B. Найдем координаты точки B. Для этого нужно найти точку пересечения граничных прямых 1 и 3:

…

Симплекс-метод (прямая задача)

…

Двойственный симплекс-метод (двойственная задача)

…

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

Исходная задача: найти количество грузовых и пассажирских поездов, которое должна обработать бригада осмотрщиков, дающее максимальную прибыль.

Решение исходной задачи: для максимизации прибыли в размере 120 руб. бригаде следует обработать 3 грузовых и 6 пассажирских поездов.

Решение двойственной задачи:

…