Навигация
Методы определения первоначального опорного плана
15346
знаков
5
таблиц
0
изображений
4. Методы определения первоначального опорного плана
4.1. Метод минимального элемента
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел 
и 
. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Пример
Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:
| 2 | 3 | 4 | 15 |
| 11 | 6 | 10 | 1 |
| 8 | 9 | 3 | 3 |
| 4 | 1 | 2 | 21 |
| 10 | 20 | 10 |
Решение:
Задача сбалансирована.
Строим первоначальный опорный план методом минимального элемента.
Выясним минимальную стоимость перевозок.
Первая перевозка будет осуществляться с пункта производства 
в пункт потребления и она составит максимально возможное число единиц продукта 
:. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки 
.Выясним минимальную стоимость перевозок (без учета столбца № 2).
Вторая и третья перевозки будут осуществляться с пункта производства 
и 
в пункт потребления 
и 
соответственно и составят максимально возможное число единиц продукта : 
, 
; 
Четвертая перевозка осуществляется с пункта 
в пункт потребления , т.к. 
(без учета первого, второго столбца и четвертой строки). 
. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. 
(без учета первого, второго столбца, третьей и четвертой строки). 
.
6. Шестая перевозка осуществляется с пункта 
в пункт потребления т.к. 
(без учета первого, второго столбца, первой, третьей и четвертой строки). 
Опорный план имеет вид;
| 10 | 5 | 0 |
| 0 | 1 | 0 |
| 0 | 3 | 0 |
| 0 | 11 | 10 |
Похожие работы
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... , является линейной функцией переменных : (2.4) Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4). Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без ...
... задачи линейного программирования, они очень сложны и решаются специальными, обычно многостадийными приемами с использованием эвристических элементов. 3. Решение задач 3.1. Решение задачи линейного программирования 3.1.1.Постановка задачи Сформулируем задачу: Определить значения переменных, обеспечивающие минимизацию целевой функции. Составим целевую функцию и зададим ограничения. ...
... . Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи , i=1,2,…,m; j=1,2,…,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла. Метод вычеркивания. Для проверки возможности ...
0 комментариев