русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Нахождение опорного плана транспортной задачи


Дата добавления: 2013-12-24; просмотров: 1416; Нарушение авторских прав


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

Лекция 4

КОНТРОЛЬНЫЕ ВОПРОСЫ

  1. Объясните сущность М-метода, при решении каких задач применяется метод искусственного базиса?
  2. Каким образом в М-методе идет выбор разрешающего столбца?
  3. Назовите теорему, устанавливающую связь между оптимальными решениями М-задачи и Z-задачи.

 

Транспортная задача - задача определения оптимального плана перевозок груза из данных пунктов отправления в заданные пункты потребления.

Исходные данные транспортной задачи задаются в распределительной таблице, где по строкам отражают запасы груза у каждого поставщика, а по столбцам – потребность в данном грузе каждого потребителя. В правом верхнем углу каждой клетки - стоимость перевозки единицы груза от каждого поставщика каждому потребителю. Причем, для того, чтобы решить транспортную задачу, сумма запасов однородного груза у поставщиков должна быть равна сумме потребностей в этом грузе потребителей (закрытая модель). В случае невыполнения этого условия (открытая модель), необходимо произвести некоторые преобразования (введение фиктивного поставщика или потребителя) и получить закрытую модель.

Алгоритм решения транспортной задачи состоит из двух шагов:

- составление первоначального опорного плана каким-либо методом (минимального элемента в таблице, северо-западного угла, аппроксимации);

- улучшение этого плана и доведение его до оптимального методом потенциалов.

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

В распределительной таблице добавляются нулевой столбец (слева) и нулевая строка (сверху).

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



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

2. Несколько одинаковых наибольших разностей. В этом случае в соответствующей строке (столбце) находим клетку, в которой стоит наименьшая стоимость, и проверяем, будет ли этот показатель наименьшим в противоположном ряду.

 

Для строки противоположным рядом будем считать столбец, а для столбца – строку.

 

Здесь возможны следующие моменты:

- условие выполнено для одной клетки. Тогда с нее начинаем заполнение таблицы;

- условие выполнено для нескольких клеток. Тогда заполняется та, которой в противоположном ряду соответствует большая разность. Если противоположные разности равны, то заполняем обе клетки;

- условие не выполняется ни для одной клетки. Тогда в строках (столбцах) с наибольшей разностью отыскивают наименьшую стоимость, из которой вычитают наименьшую стоимость противоположного рядя. В результате получают несколько положительных чисел. Заполняется клетка, для которой это число будет наименьшим, после чего разности рассчитывают заново. Если числа будут одинаковые, то заполняем любую клетку.

 

Решение транспортной задачи рассмотрим на конкретном примере (таблица 4.1.):

 

Таблица 4.1.

 
 
 
 
         

Находим разность по строкам и по столбцам (табл. 4.2.)

Таблица 4.2.

   
8 х  
4 х 10 х 8 х 3 180   180 0
220 120
  х
        250 70

Наибольших разностей две – в первом и четвертом столбце- и равны они 2. И в первом и во втором случае наименьшие стоимости (2 и 3) являются наименьшими и в противоположном ряду. Противоположные разности также равны (1 и 1), следовательно, заполняем обе клетки.

Потребность первого потребителя полностью удовлетворена, поэтому остальные клетки этого столбца заполняться не будут. Исчерпан полностью и запас груза второго поставщика. В пустые клетки первого столбца и второй строки поставим “х”. В дальнейшем первый столбец и четвертая строка не рассматриваются, и пересчитываем только разности строк и столбцов не выбывших из рассмотрения.

Таблица 4.3.

     
8 х  
    4 х 10 х 8 х 3 180  
 
х 4 100 8 х 9 х 100 0
    150 50    

 

Опять получились две наибольшие разности (4) в четвертой строке и в четвертом столбце. Проверяем являются ли их наименьшие стоимости наименьшими в противоположном ряду. Как видим, в обеих случаях это условие не выполняется. Тогда находим разности между этими стоимостями и наименьшими стоимостями противоположного ряда.

Для четвертой строки: наименьшая стоимость равна 4, а наименьшая стоимость противоположного ряда (второй столбец) равна 3. Разность между ними равна 1.

Для четвертого столбца: наименьшая стоимость равна 5, а наименьшая стоимость третьей строки равна 3. Разность между ними равна 2. Наименьшее значение имеет первая разность, поэтому заполняем клетку, расположенную в четвертой строке и во втором столбце.

Из рассмотрения выходит четвертая строка.

 

Таблица 4.4.

 

     
8 х 7 х  
    4 х 10 х 8 х 3 180  
  3 50 120 70
  х 4 100 8 х 9 х  
    50 0    

 

Вновь две одинаковые разности во втором и в четвертом столбцах. Во втором столбце наименьшая стоимость (3) является наименьшей и в противоположном ряду. А в четвертом столбце наименьшая стоимость (5) не является наименьшей в третьей строке. Поэтому заполняем клетку, расположенную в третьей строке и во втором столбце. Второй столбец выходит из рассмотрения. И вновь пересчитываем разности.

 

Таблица 4.5.

 

       
3 8 х 7 х 6 200 9 х   200 0
    4 х 10 х 8 х 3 180  
3 50 6 х 70 0
  х 4 100 8 х 9 х  
        200 0   70 0

Наибольшая разность соответствует четвертому столбцу. Поэтому заполняем клетку, расположенную в третьей строке и в четвертом столбце, так как в ней находится наименьшая стоимость. И последняя клетка, расположенная в первой строке и в третьем столбце, заполняется однозначно. Полученный опорный план представлен в таблице 4.6.

 

Таблица 4.6.

6 200
3 180
3 50 6 0
  4 100

 

 



<== предыдущая лекция | следующая лекция ==>
Метод искусственного базиса или М - метод | Нахождение оптимального плана методом потенциалов


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.