Набор клеток матрицы перевозок в виде многоугольника в котором только две находятся в одной строке или столбце, а последняя лежит в том же ряду, что и первая. Для каждой свободной клетки можно составить только один цикл, который будет проходить сначала через свободную клетку, а затем его вершины располагаются в занятых клетках. 1.Сост-тся опорный план. Опор. план провер. на вырожденность. Кол-во занятых клеток должно быть равно m+n-1. Если меньше, то в любую другую свободную клетку заносится 0 ед. груза и клетка считается занятой. 2. Для всех свободных клеток составляются циклы во всех клетках цикла начиная со свободной поочередно ставятся знаки «+» «-». 3.Для всех циклов подсчитывается сумма. S_ij=C_ij-C_ik+⋯+C_ij Если хотя бы для одного цикла она отрицательна, то план можно улучшить. 4.Улучшение опорного плана происходит переброской груза. Кол-во груза определяется по наименьшему из чисел в отрицательных клетках цикла.
10.Транспортная задача с открытой моделью. Если суммарная производная мощность поставщика превышает спрос потребителей или спрос потребителей больше мощностей поставщиков, то имеется трансп. задача с откр. моделью. Если сумма ∑_(i=1)^m▒〖a_i>∑_(j=1)^m▒b_i 〗, то в мат. модель вводится фиктивный n+1 пункт потребления. Тогда в матрице задачи добавл. столбец потребность кот. равна числу превыш. груза, при этом все тарифы на доставку груза пункт B_(n+1)=0. Очевидно, что с помощью введения доп. столбца задача преобразуется в закрытую. Для новой задачи функц. остается неизменным, т.к. цены на доп перевозки равны 0. Если же ∑_(i=1)^m▒〖a_i<∑_(j=1)^m▒b_j 〗, то ввод. фиктивный m+1 пункт призв-ва для кот. запас равен кол-ву нехватающего груза. Тарифы на доставку груза от фикт. A_(m+1)=0. В матрицу добав. A_(m+1) и задача становится закрытой.
1.Транспортная задача на min времени. Среди всевозможных значений 〖{x〗_1^i 〖,x〗_2^i…x_k^i} i=1k. Найти такое соотв-е, которое будет min среди max значений tmin[maxtmax]. Это решение будем называть оптимальным и также задачи наз-ся на минимакс. Для определения t-опт. надо: 1.Построить начальное неотрицательное решение системы уравнений. 2.Среди базисных переменных xij найти такую которой соответствует наибольшее значение времени. 3.Исключить из дальнейшего рассмотрения свободные переменные для которых tj≥timax. 4.В i-ой строке найти положительный коэффициент Cij и определить в этом столбце разрешающий элемент Aij какой-нибудь, после этого сделать один шаг Жордановых исключений. 5.Повторим, если необходимо этап 4 несколько раз вывести переменную xij из совокупности базисных переменных и исключить ее из дальнейшего рассмотрения. Этапы 2,5 повторять до тех пор, пока на некотором шаге в соотв. строке преобразованы системы все коэф-ты при переменных станут своб. переменная. Базисное решение полученное на этом шаге яв-ся оптимальным.
2.Транспортная задача на max целевой функции. Во многих задачах целевого типа максимизируется, поэтому при составлении начального опорного плана в первую очередь стараются заполнить клетки с наиболее высокими показателями, выбор клетки подлежащий заполнению при переходе от одного опорного плана к другому производится по положительной оценке. Опт. будет опорн. план, кот. в табл. соответствует свободные клетки с не положит. клетками все Sij≤0.
Сост. мат. модель задачи, обозначаем через xij-кол-во товара i-го сорта на j-ом станке,f(x11x12..х34)-общая прибыль, тогда реш. задачи сведется к максимизации. Довольно часто транспортная задача представлена бывает в так называемом несбалансированном виде. В этом случае для приведения транспортной задачи к сбалансированному виду, следует добавить в табл. фиктивный пункт пр-ва или потребления. Тарифы по строке или столбцу будут равны 0. В табл. содержится опорный план. Так же встречается, что клетку приходится блокировать, приписав ей показатель n равный очень большому по абсолютной величине отрицательному числу. Если все оценки будут отрицательны, то новый план оказался отрицательным.
Классификация ЗУЗ.
По кол-ву управляемых периодов на однопериодные и многопериодные. Если пополнение запасов произв-ся один раз-однопериодная, если много-многопериодная. 2.по характеру пополнения запасов, мгновенная после подачи заявки и с задержки. 3.по учету хар-ра спроса: на детерминированные и вероятность. 4.по кол-ву типов ресурсов-на однопродуктовые и многопродуктовые. Если запас включает несколько видов продукции, то имеем многопродуктовую задачу, в противном случае однопродуктувую. Если в задаче помимо базиса будем учитывать расход масла, то это многопродуктовая задача. 5.По виду целевой функции на задачу с пропорционными и не пропорциональными затратами. Так затраты не 1км. Машины могут быть пропорциональными.
5.Однопродуктовая детерминация ЗУЗ. Постановка задачи и выбор критерия оптимизации. Декадная потребность предприятия в каком либо материале составляет Q условных единиц. Расход происходит равномерно, определить размер поставки материала, чтобы суммарные затраты на создание и хранение запасов.Выявление основных особенностей взаимосвязей и кол-ых закономерностей. Обозначим через Сх затраты на хранение единицы запаса на единицу времени, а через Сд затраты на доставку материалов. Пусть затраты Сд не зависят от кол-ва материала поставляемой партии. Предполагается, что все партии состоят из одинакового числа единиц материала. Кол-во необходимых поставок для удовлетворения потребностей в материале: n=Q/S=T/t