Решение транспортной задачи закрытого типа методом «наименьшей стоимости»

2. Строим базисное решение методом «Минимальной стоимости». Проверяем полученное базисное решение на вырожденность:

количество базисных клеток в начальном решении должно быть равным числу М+N-1, если базисная клетка меньше, то решение – вырожденное. И для его исправления вводим любую клетку, лучше с наименьшей удельной стоимостью, в которой задает значение равное нулю: Xij=0

3. Оцениваем полученное решение, используем метод потенциала:

 Для этого решают систему уравнений

a_i+b_j=c_ij    при x_ij>0.

Для того чтобы найти  частное решение системы, одному из потенциалов (обычно тому, которому соответствует большее число  занятых клеток) задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам

a_i=c_ij-b_j    при x_ij>0,

известен потенциал b_j, и

b_j= c_ij - a_i    при x_ij>0,

Если известен потенциал a_i.

Проверяют, выполняется  ли условие оптимальности для  свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формулам

D_ij=a_i+b_j-c_ij

и те оценки, которые >0, записывают в левые нижние углы клеток  , если среди оценок нет отрицательных, то решение оптимально, находим значение целевой функции и записываем ответ. Если хотя бы 1 оценка отрицательная, то переходим к следующему пункту.

4. Находим новое базисное решение с помощью распределительного метода: Выбираем какую-нибудь свободную клетку с отрицательной оценкой, и строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочерёдно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину Х₀=min{x_ij}. Клетка со знаком «-», в которой достигается min{x_ij}, остаётся пустой. Если минимум достигается в нескольких клетках, то одна из них остаётся пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m+n-1.
5. Получив новое базисное решение, переходим к 3 пункту[9].

Пример 2: составим математическую модель транспортной задачи, исходные данные которой приведены в таблице 8 [10]

Таблица 8 – исходные данные

Bj Ai	30	40	25	85	15
105	5	4	3	2	1
50	3	2	6	8	2
40	4	1	4	4	6

 

Решение. Проверяем сбалансированность задачи: А=30+40+25+85+15=195.

В=105+50+40=195.

А=В, т.е. задача закрытого  типа (сбалансированная)

Находим минимальную  оценку и рассматриваем соответствующего поставщика и потребителя, С_min=a₁b₅=1. Записываем суда 15 и исключаем четвёртого потребителя, запасы первого поставщика=105-15=90.

 

 

Таблица 9 – нахождение минимальной оценки

Bj Ai	30	40	25	85	15
105	5	4	3	2	1   min 15
50	3	2	6	8	2      ——
40	4	1	4	4	6      ——

 

 

 

 

 

 

 

 

 

 

Ищем следующую минимальную  оценку: С_min=а₃b₂=1. Записываем 40, исключаем третьего поставщика и второго потребителя.

 

Таблица 10 - нахождение минимальной оценки

Bj Ai	30	40	25	85	15
105	5	4      ——	3	2	1   15
50	3	2      ——	6	8	2      ——
40	4      ——	1    min 40	4     ——	4      ——	6      ——

 

 

 

 

 

 

 

 

 

Следующая минимальная  оценка C_min=a₁b₄=2. Записываем 85, исключаем четвёртого потребителя. Запасы первого поставщика=90-85=5.

 

 

 

 

Таблица 11 - нахождение минимальной оценки

Bj Ai	30	40	25	85	15
105	5	4      ——	3	2   min 85	1   15
50	3	2      ——	6	8      ——	2      ——
40	4      ——	1    40	4     ——	4      ——	6      ——

 

 

 

 

 

 

 

 

Ищем далее, C_min=a₁b₃и a₂b₁=3. Записываем сюда 5 и 30 соответственно. Исключаем из рассмотрения первого поставщика и первого потребителя. Запросы третьего потребителя составят 25-5=20, а запасы второго поставщика=50-30=20.

    Таблица 12 - нахождение минимальной оценки

Bj Ai	30	40	25	85	15
105	5      ——	4      ——	3    min 5	2   85	1   15
50	3   min 30	2      ——	6	8      ——	2      ——
40	4      ——	1    40	4     ——	4      ——	6      ——

 

 

 

 

 

 

 

 

 

Следующая минимальная  оценка C_min=a₂b₃=6. Записываем 20, Запасы всех поставщиков израсходованы, а потребности потребителей удовлетворенны.

 

 

 

 

Таблица 13 - нахождение минимальной оценки

Bj Ai	30	40	25	85	15
105	5      ——	4      ——	3   5	2   85	1   15
50	3   30	2      ——	6    min     20	8        ——	2        ——
40	4      ——	1    40	4     ——	4      ——	6      ——

 

 

 

 

 

 

 

 

Проверяем правильность построения опорного решения. Число  занятых клеток равно N=m+n-1=5+3-1=7. Т.к. в нашем случае число занятых клеток=6, т.е. вырожденное, то добавляем дополнительное базисное решение C_min=a₂b₂=0.

Таблица 14 – опорное решение

Bj Ai	30	40	25	85	15
105	5      ——	4      ——	3   5	2   85	1   15
50	3   30	2 0	6        20	8      ——	2      ——
40	4      ——	1    40	4     ——	4     ——	6      ——

 

 

 

 

 

 

 

 

Решение является опорным.

 

3 БЛОК-СХЕМА

3.1 Транспортная задача

 

 

 

 

 

 

 

 

                              НЕТ                              ДА

       НЕТ                            ДА

 

  

 

 

 

 

 

                                                           Нахождение нач.

                                                            базисного

                                                           решения

                                                          методом наименьшей стоимости

 

                                                        

 

                                           ДА

 

                             НЕТ

 
3.2 Минимальная стоимость

 

4 ФОРМЫ ВХОДНОЙ ИНФОРМАЦИИ

Информация вводится с помощью клавиатуры.

Пользователь вводит необходимые  начальные значения. Для решения  задачи пользователю необходимо ввести следующие данные:

      Na - количество поставщиков (от 2 до 5);

      Nb - количество потребителей(от 2 до 5);                                                                                                                                                                                                                                                                                                                                                                                                                                                                            

      A[i] - количество поставляемой продукции каждым поставщиком.

      B[j] - количество требуемой продукции каждым потребителем.

      A [i, j] – расстояние перевозки от i-го поставщика j-ому потребителю.

После ввода  каждого значения нужно нажать «Enter».

 

5 ФОРМЫ ВЫХОДНОЙ ИНФОРМАЦИИ

Выходной информацией  программы являются:

1. Таблица с данными распределения запаса между потребителями и поставщиками.
2. F – Значение целевой функции, которое представляет собой суммарные затраты на перевозки.

 

6 ИНСТРУКЦИЯ ДЛЯ ПОЛЬЗОВАТЕЛЯ

Аппаратные и программные  требования:

 

1. Техническое обеспечение:

Для нормальной работы программы  необходимо персональный компьютер  совместимый с IBM PC, с процессором не ниже 486, оперативной памятью не менее 8 МБ, тактовой частотой 120 МГц занимаемое место на диске после инсталляции 5 МБ[4].

2. Информационные средства:

Операционная система Windows 95,98, NT и DOS.

3. Общие сведения

Данная программа предназначена  для составления опорного решения  транспортной задачи методом “наименьшего расстояния”. Программа также определяет значение целевой функции, которое представляет собой суммарные затраты на перевозки.

4. Управление

Для запуска программы  необходимо скопировать файл с названием TZ.pas с дискеты в каталог BP7, расположенный на диске С. Запустить Pascal и открыть файл TZ.pas. При запуске программы (Alt+F5) необходимо заполнить таблицу входной информации.

Ввод начальных значений

Ввод данных осуществляется с клавиатуры.

Программа запрашивает  сначала:

1. количество поставщиков;
2. количество потребителей;
3. количество продукции в пунктах А и В;
4. расстояние от пункта А до пункта В.

5. Выход

Выход из программы осуществляется как из обычного Windows приложения.

 

7 ИНСТРУКЦИЯ ДЛЯ ПРОГРАММИСТА

Данная программа реализована  с помощью среды программирования Borland Pascal.

 

Требуемые информационно-вычислительные средства:

• Оперативная память – не менее 8 Мб.
• Центральный процессор – процессор не ниже 486 с тактовой частотой 120 МГц.
• Свободное место на жестком диске – не менее 20 КБ.
• Видеокарта и монитор с разрешением 800x600
• Для нормального функционирования программы достаточно иметь оперативную систему DOS.