🗊Презентация Транспортная задача линейного программирования

Категория: Экономика и Финансы
Нажмите для полного просмотра!
Транспортная задача линейного программирования, слайд №1Транспортная задача линейного программирования, слайд №2Транспортная задача линейного программирования, слайд №3Транспортная задача линейного программирования, слайд №4Транспортная задача линейного программирования, слайд №5Транспортная задача линейного программирования, слайд №6Транспортная задача линейного программирования, слайд №7Транспортная задача линейного программирования, слайд №8Транспортная задача линейного программирования, слайд №9Транспортная задача линейного программирования, слайд №10Транспортная задача линейного программирования, слайд №11Транспортная задача линейного программирования, слайд №12Транспортная задача линейного программирования, слайд №13Транспортная задача линейного программирования, слайд №14Транспортная задача линейного программирования, слайд №15Транспортная задача линейного программирования, слайд №16Транспортная задача линейного программирования, слайд №17Транспортная задача линейного программирования, слайд №18Транспортная задача линейного программирования, слайд №19Транспортная задача линейного программирования, слайд №20Транспортная задача линейного программирования, слайд №21Транспортная задача линейного программирования, слайд №22Транспортная задача линейного программирования, слайд №23Транспортная задача линейного программирования, слайд №24Транспортная задача линейного программирования, слайд №25Транспортная задача линейного программирования, слайд №26Транспортная задача линейного программирования, слайд №27Транспортная задача линейного программирования, слайд №28Транспортная задача линейного программирования, слайд №29Транспортная задача линейного программирования, слайд №30Транспортная задача линейного программирования, слайд №31Транспортная задача линейного программирования, слайд №32Транспортная задача линейного программирования, слайд №33Транспортная задача линейного программирования, слайд №34Транспортная задача линейного программирования, слайд №35Транспортная задача линейного программирования, слайд №36Транспортная задача линейного программирования, слайд №37Транспортная задача линейного программирования, слайд №38Транспортная задача линейного программирования, слайд №39Транспортная задача линейного программирования, слайд №40Транспортная задача линейного программирования, слайд №41Транспортная задача линейного программирования, слайд №42Транспортная задача линейного программирования, слайд №43Транспортная задача линейного программирования, слайд №44Транспортная задача линейного программирования, слайд №45Транспортная задача линейного программирования, слайд №46Транспортная задача линейного программирования, слайд №47Транспортная задача линейного программирования, слайд №48Транспортная задача линейного программирования, слайд №49Транспортная задача линейного программирования, слайд №50Транспортная задача линейного программирования, слайд №51Транспортная задача линейного программирования, слайд №52Транспортная задача линейного программирования, слайд №53Транспортная задача линейного программирования, слайд №54Транспортная задача линейного программирования, слайд №55Транспортная задача линейного программирования, слайд №56Транспортная задача линейного программирования, слайд №57Транспортная задача линейного программирования, слайд №58Транспортная задача линейного программирования, слайд №59Транспортная задача линейного программирования, слайд №60Транспортная задача линейного программирования, слайд №61Транспортная задача линейного программирования, слайд №62Транспортная задача линейного программирования, слайд №63Транспортная задача линейного программирования, слайд №64Транспортная задача линейного программирования, слайд №65Транспортная задача линейного программирования, слайд №66
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Транспортная задача линейного программирования. Доклад-сообщение содержит 66 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Транспортная задача линейного программирования Имеется m поставщиков (A1….Am) некоторого однородного продукта в количествах a1….am соответственно. Требуется доставить этот продукт n потребителям (B1….Bn) в количествах b1…bn соответственно. Известна cij стоимость перевозки единицы груза от i-го поставщика к j-му потребителю. Составить план перевозок, удовлетворяющий потребности в продукте и имеющий минимальную стоимость.
Описание слайда:
Транспортная задача линейного программирования Имеется m поставщиков (A1….Am) некоторого однородного продукта в количествах a1….am соответственно. Требуется доставить этот продукт n потребителям (B1….Bn) в количествах b1…bn соответственно. Известна cij стоимость перевозки единицы груза от i-го поставщика к j-му потребителю. Составить план перевозок, удовлетворяющий потребности в продукте и имеющий минимальную стоимость.

Слайд 2


Обозначим xij груз, перевозимый от i-го поставщика к j-му потребителю, сij – стоимость перевозки единицы груза. Обозначим xij груз, перевозимый от i-го поставщика к j-му потребителю, сij – стоимость перевозки единицы груза. Условия задачи запишем в матрицу планирования.
Описание слайда:
Обозначим xij груз, перевозимый от i-го поставщика к j-му потребителю, сij – стоимость перевозки единицы груза. Обозначим xij груз, перевозимый от i-го поставщика к j-му потребителю, сij – стоимость перевозки единицы груза. Условия задачи запишем в матрицу планирования.

Слайд 3


Составим модель задачи Составим модель задачи
Описание слайда:
Составим модель задачи Составим модель задачи

Слайд 4


Транспортная задача линейного программирования, слайд №4
Описание слайда:

Слайд 5


Построение первоначального опорного плана Система ограничений ТЗ содержит m x n неизвестных и m+n уравнений.
Описание слайда:
Построение первоначального опорного плана Система ограничений ТЗ содержит m x n неизвестных и m+n уравнений.

Слайд 6


Если сложить почленно уравнения подсистемы (1) и отдельно подсистемы (2) то получим два одинаковых уравнения. Если сложить почленно уравнения подсистемы (1) и отдельно подсистемы (2) то получим два одинаковых уравнения. Следовательно подсистема линейно зависима. Если одно из уравнений отбросить, то система ограничений должна содержать m+n-1 линейно независимых уравнений. Следовательно невырожденный опорный план ТЗ содержит m+n-1 положительных компонент (xij), а остальные равны нулю.
Описание слайда:
Если сложить почленно уравнения подсистемы (1) и отдельно подсистемы (2) то получим два одинаковых уравнения. Если сложить почленно уравнения подсистемы (1) и отдельно подсистемы (2) то получим два одинаковых уравнения. Следовательно подсистема линейно зависима. Если одно из уравнений отбросить, то система ограничений должна содержать m+n-1 линейно независимых уравнений. Следовательно невырожденный опорный план ТЗ содержит m+n-1 положительных компонент (xij), а остальные равны нулю.

Слайд 7


Транспортная задача линейного программирования, слайд №7
Описание слайда:

Слайд 8


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

Слайд 9


Всякий план ТЗ содержащий более m+n-1 занятых клеток не является опорным, т.к. ему соответствует линейно зависимая система векторов. Всякий план ТЗ содержащий более m+n-1 занятых клеток не является опорным, т.к. ему соответствует линейно зависимая система векторов. При таком плане в таблице всегда можно построить замкнутый цикл. Если к занятым клеткам, определяющим опорный план (ацикличный) добавить одну незанятую клетку, то появится единственный цикл.
Описание слайда:
Всякий план ТЗ содержащий более m+n-1 занятых клеток не является опорным, т.к. ему соответствует линейно зависимая система векторов. Всякий план ТЗ содержащий более m+n-1 занятых клеток не является опорным, т.к. ему соответствует линейно зависимая система векторов. При таком плане в таблице всегда можно построить замкнутый цикл. Если к занятым клеткам, определяющим опорный план (ацикличный) добавить одну незанятую клетку, то появится единственный цикл.

Слайд 10


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

Слайд 11


Существует несколько методов построения первоначального опорного плана. Существует несколько методов построения первоначального опорного плана.
Описание слайда:
Существует несколько методов построения первоначального опорного плана. Существует несколько методов построения первоначального опорного плана.

Слайд 12


Метод северо-западного угла Пусть условия ТЗ заданы таблицей.
Описание слайда:
Метод северо-западного угла Пусть условия ТЗ заданы таблицей.

Слайд 13


Начинаем с первого потребителя В1 и первого поставщика А1. Начинаем с первого потребителя В1 и первого поставщика А1. Сравниваем a1=100 и b1=200, a1<b1, меньший из объемов 100 записываем в левый нижний угол клетки А1В1. Запасы первого поставщика израсходованы, поэтому в клетках первой строки ставим черту.
Описание слайда:
Начинаем с первого потребителя В1 и первого поставщика А1. Начинаем с первого потребителя В1 и первого поставщика А1. Сравниваем a1=100 и b1=200, a1<b1, меньший из объемов 100 записываем в левый нижний угол клетки А1В1. Запасы первого поставщика израсходованы, поэтому в клетках первой строки ставим черту.

Слайд 14


Транспортная задача линейного программирования, слайд №14
Описание слайда:

Слайд 15


Транспортная задача линейного программирования, слайд №15
Описание слайда:

Слайд 16


Потребности В2 не удовлетворены на 50 ед. Берем их у А3 и переходим к В3 и т.д. Потребности В2 не удовлетворены на 50 ед. Берем их у А3 и переходим к В3 и т.д. Процесс продолжается пока не закончатся запасы и потребности.
Описание слайда:
Потребности В2 не удовлетворены на 50 ед. Берем их у А3 и переходим к В3 и т.д. Потребности В2 не удовлетворены на 50 ед. Берем их у А3 и переходим к В3 и т.д. Процесс продолжается пока не закончатся запасы и потребности.

Слайд 17


Начиная движение от занятой клетки А1В1 вернуться в нее, двигаясь только по занятым клеткам невозможно. Следовательно план опорный. Начиная движение от занятой клетки А1В1 вернуться в нее, двигаясь только по занятым клеткам невозможно. Следовательно план опорный. План является невырожденным, т.к. содержит m+n-1=4+5-1=8 занятых клеток. Мы не учитывали стоимость перевозок, поэтому план наверное не оптимальный. Найдем общую стоимость перевозок: Z=100·10+100·2+150·7+50·5+100·3+50·2+ +50·16+235·13=6950 ед. стоимости. Если при составлении опорного плана учитывать стоимость, то план будет ближе к оптимальному.
Описание слайда:
Начиная движение от занятой клетки А1В1 вернуться в нее, двигаясь только по занятым клеткам невозможно. Следовательно план опорный. Начиная движение от занятой клетки А1В1 вернуться в нее, двигаясь только по занятым клеткам невозможно. Следовательно план опорный. План является невырожденным, т.к. содержит m+n-1=4+5-1=8 занятых клеток. Мы не учитывали стоимость перевозок, поэтому план наверное не оптимальный. Найдем общую стоимость перевозок: Z=100·10+100·2+150·7+50·5+100·3+50·2+ +50·16+235·13=6950 ед. стоимости. Если при составлении опорного плана учитывать стоимость, то план будет ближе к оптимальному.

Слайд 18


Метод минимальной стоимости. Суть метода в том, что из всей таблицы стоимостей выбирают наименьшую и в эту клетку (ij) помещают меньшее из чисел ai или bj. Вычеркивают столбец или строку (запасы израсходованы или запрос удовлетворен) Из оставшейся таблицы снова выбирают клетку с наименьшей стоимостью и т.д. Процесс продолжается пока все запасы не будут распределены, а потребности удовлетворены.
Описание слайда:
Метод минимальной стоимости. Суть метода в том, что из всей таблицы стоимостей выбирают наименьшую и в эту клетку (ij) помещают меньшее из чисел ai или bj. Вычеркивают столбец или строку (запасы израсходованы или запрос удовлетворен) Из оставшейся таблицы снова выбирают клетку с наименьшей стоимостью и т.д. Процесс продолжается пока все запасы не будут распределены, а потребности удовлетворены.

Слайд 19


Пусть условия ТЗ заданы таблицей
Описание слайда:
Пусть условия ТЗ заданы таблицей

Слайд 20


Выбираем наименьшую стоимость, она помещена в клетке А1В4, т.к. а1=b4=100, то 100 помещаем в А1В4 и вычеркиваем первую строку и четвертый столбец. Выбираем наименьшую стоимость, она помещена в клетке А1В4, т.к. а1=b4=100, то 100 помещаем в А1В4 и вычеркиваем первую строку и четвертый столбец.
Описание слайда:
Выбираем наименьшую стоимость, она помещена в клетке А1В4, т.к. а1=b4=100, то 100 помещаем в А1В4 и вычеркиваем первую строку и четвертый столбец. Выбираем наименьшую стоимость, она помещена в клетке А1В4, т.к. а1=b4=100, то 100 помещаем в А1В4 и вычеркиваем первую строку и четвертый столбец.

Слайд 21


Наименьшей является стоимость в А2В1 и А3В5. Наименьшей является стоимость в А2В1 и А3В5. В А2В1 200<250, →200 записываем и исключаем столбец В1. В А3В5 200<250 записываем 200 и исключаем строку А3.
Описание слайда:
Наименьшей является стоимость в А2В1 и А3В5. Наименьшей является стоимость в А2В1 и А3В5. В А2В1 200<250, →200 записываем и исключаем столбец В1. В А3В5 200<250 записываем 200 и исключаем строку А3.

Слайд 22


В таблице снова выбираем наименьшую стоимость и продолжим пока все запасы не будут распределены В таблице снова выбираем наименьшую стоимость и продолжим пока все запасы не будут распределены
Описание слайда:
В таблице снова выбираем наименьшую стоимость и продолжим пока все запасы не будут распределены В таблице снова выбираем наименьшую стоимость и продолжим пока все запасы не будут распределены

Слайд 23


Метод двойного предпочтения. Если таблица большая, то перебор элементов сложен и используют этот метод. В каждом столбце и строке отмечают знаком γ клетку с наименьшей стоимостью. В результате некоторые клетки имеют отметку γγ. В эти клетки помещают максимально возможные объемы перевозок и исключают соответствующие строки и столбцы. Затем распределяют перевозки по клеткам с γ. В оставшейся таблице распределение производят по наименьшей стоимости.
Описание слайда:
Метод двойного предпочтения. Если таблица большая, то перебор элементов сложен и используют этот метод. В каждом столбце и строке отмечают знаком γ клетку с наименьшей стоимостью. В результате некоторые клетки имеют отметку γγ. В эти клетки помещают максимально возможные объемы перевозок и исключают соответствующие строки и столбцы. Затем распределяют перевозки по клеткам с γ. В оставшейся таблице распределение производят по наименьшей стоимости.

Слайд 24


Транспортная задача линейного программирования, слайд №24
Описание слайда:

Слайд 25


Отметим клетки c минимальной стоимостью по строкам Отметим клетки c минимальной стоимостью по строкам
Описание слайда:
Отметим клетки c минимальной стоимостью по строкам Отметим клетки c минимальной стоимостью по строкам

Слайд 26


Транспортная задача линейного программирования, слайд №26
Описание слайда:

Слайд 27


Сначала заполним клетки А2В1, А1В4 А3В5 а затем А4В2 Сначала заполним клетки А2В1, А1В4 А3В5 а затем А4В2
Описание слайда:
Сначала заполним клетки А2В1, А1В4 А3В5 а затем А4В2 Сначала заполним клетки А2В1, А1В4 А3В5 а затем А4В2

Слайд 28


Далее заполним клетки по минимальной стоимости А2В3, А4В3 , А4В5 Далее заполним клетки по минимальной стоимости А2В3, А4В3 , А4В5
Описание слайда:
Далее заполним клетки по минимальной стоимости А2В3, А4В3 , А4В5 Далее заполним клетки по минимальной стоимости А2В3, А4В3 , А4В5

Слайд 29


С помощью рассмотренных методов можно получить вырожденный или невырожденный опорный план. С помощью рассмотренных методов можно получить вырожденный или невырожденный опорный план. Оптимальный план можно найти с помощью симплекс метода, однако, из-за большого количества переменных обычно используют более простой метод – метод потенциалов.
Описание слайда:
С помощью рассмотренных методов можно получить вырожденный или невырожденный опорный план. С помощью рассмотренных методов можно получить вырожденный или невырожденный опорный план. Оптимальный план можно найти с помощью симплекс метода, однако, из-за большого количества переменных обычно используют более простой метод – метод потенциалов.

Слайд 30


Метод потенциалов Теорема Если план X* транспортной задачи является оптимальным, то ему соответствует система из m+n чисел U*I V*j, удовлетворяющих условиям U*i+V*j=Cij U*i+V*j≤Cij Числа U*I и V*j называются потенциалами соответственно поставщиков и потребителей.
Описание слайда:
Метод потенциалов Теорема Если план X* транспортной задачи является оптимальным, то ему соответствует система из m+n чисел U*I V*j, удовлетворяющих условиям U*i+V*j=Cij U*i+V*j≤Cij Числа U*I и V*j называются потенциалами соответственно поставщиков и потребителей.

Слайд 31


Доказательство Доказательство Транспортную задачу
Описание слайда:
Доказательство Доказательство Транспортную задачу

Слайд 32


Пусть каждому ограничению вида
Описание слайда:
Пусть каждому ограничению вида

Слайд 33


План X* является оптимальным планом двойственной задачи, поэтому план План X* является оптимальным планом двойственной задачи, поэтому план Y*=(U*I, V*j) является оптимальным планом исходной задачи и согласно теоремы двойственности
Описание слайда:
План X* является оптимальным планом двойственной задачи, поэтому план План X* является оптимальным планом двойственной задачи, поэтому план Y*=(U*I, V*j) является оптимальным планом исходной задачи и согласно теоремы двойственности

Слайд 34


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

Слайд 35


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

Слайд 36


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

Слайд 37


Построение системы потенциалов. Построение системы потенциалов. Используем условие
Описание слайда:
Построение системы потенциалов. Построение системы потенциалов. Используем условие

Слайд 38


Пусть известен потенциал Ui тогда Пусть известен потенциал Ui тогда
Описание слайда:
Пусть известен потенциал Ui тогда Пусть известен потенциал Ui тогда

Слайд 39


В таблице выбираем строку с наибольшим количеством занятых клеток (А4) и полагаем U4=0. В таблице выбираем строку с наибольшим количеством занятых клеток (А4) и полагаем U4=0. В А4 три занятых клетки А4В2 А4В3 А4В5, которые связывают потенциал U4 c потенциалами V2 , V3, ,V5
Описание слайда:
В таблице выбираем строку с наибольшим количеством занятых клеток (А4) и полагаем U4=0. В таблице выбираем строку с наибольшим количеством занятых клеток (А4) и полагаем U4=0. В А4 три занятых клетки А4В2 А4В3 А4В5, которые связывают потенциал U4 c потенциалами V2 , V3, ,V5

Слайд 40


Определим эти потенциалы Определим эти потенциалы V2= C42-U4=8-0=8 V3= C43-U4=12-0=12 V5= C45-U4=13-0=13 C помощью U4 нельзя определить больше никакой потенциал, подчеркиваем U4
Описание слайда:
Определим эти потенциалы Определим эти потенциалы V2= C42-U4=8-0=8 V3= C43-U4=12-0=12 V5= C45-U4=13-0=13 C помощью U4 нельзя определить больше никакой потенциал, подчеркиваем U4

Слайд 41


Поочередно просматриваем столбцы В2 В3 В5 , для которых потенциалы определены. Поочередно просматриваем столбцы В2 В3 В5 , для которых потенциалы определены. В столбце В2 две занятые клетки А2В2 и А4В2 , которые связывают V2 c U2 и U4(уже определен). U2= C22-V2=7-8=-1Подчеркиваем V2 В столбце В3 нет занятых клеток, связывающих V3 с неизвестными потенциалами строк, подчеркиваем V3
Описание слайда:
Поочередно просматриваем столбцы В2 В3 В5 , для которых потенциалы определены. Поочередно просматриваем столбцы В2 В3 В5 , для которых потенциалы определены. В столбце В2 две занятые клетки А2В2 и А4В2 , которые связывают V2 c U2 и U4(уже определен). U2= C22-V2=7-8=-1Подчеркиваем V2 В столбце В3 нет занятых клеток, связывающих V3 с неизвестными потенциалами строк, подчеркиваем V3

Слайд 42


Переходим к В5. В нем одна занятая клетка А3В5 , которая связывает V5 c неизвестным U3=C32-V5=2-13=-11 Подчеркиваем V5 Переходим к В5. В нем одна занятая клетка А3В5 , которая связывает V5 c неизвестным U3=C32-V5=2-13=-11 Подчеркиваем V5 Потенциал U2 занятой клетки А2В1 связан с неизвестным потенциалом V1=2-(-1)=3. Подчеркиваем U2 и U3 Подчеркиваем V 1 т.к. в В1 нет занятых клеток, связывающих его с неизвестным потенциалом строки
Описание слайда:
Переходим к В5. В нем одна занятая клетка А3В5 , которая связывает V5 c неизвестным U3=C32-V5=2-13=-11 Подчеркиваем V5 Переходим к В5. В нем одна занятая клетка А3В5 , которая связывает V5 c неизвестным U3=C32-V5=2-13=-11 Подчеркиваем V5 Потенциал U2 занятой клетки А2В1 связан с неизвестным потенциалом V1=2-(-1)=3. Подчеркиваем U2 и U3 Подчеркиваем V 1 т.к. в В1 нет занятых клеток, связывающих его с неизвестным потенциалом строки

Слайд 43


Построение системы потенциалов прервалось. Потенциалы U1 и V4 остались неопределенными, поскольку план вырожденный. Построение системы потенциалов прервалось. Потенциалы U1 и V4 остались неопределенными, поскольку план вырожденный. Добавляем фиктивно занятую клетку с нулевой перевозкой в столбце В4 или строке А1. Целесообразно найти клетку с наименьшей стоимостью, это клетка А3В4. Тогда, V4=C34-U3=2-(-11)=13 U1=C14-V4=1-13=-12
Описание слайда:
Построение системы потенциалов прервалось. Потенциалы U1 и V4 остались неопределенными, поскольку план вырожденный. Построение системы потенциалов прервалось. Потенциалы U1 и V4 остались неопределенными, поскольку план вырожденный. Добавляем фиктивно занятую клетку с нулевой перевозкой в столбце В4 или строке А1. Целесообразно найти клетку с наименьшей стоимостью, это клетка А3В4. Тогда, V4=C34-U3=2-(-11)=13 U1=C14-V4=1-13=-12

Слайд 44


Транспортная задача линейного программирования, слайд №44
Описание слайда:

Слайд 45


Проверка выполнения условия оптимальности для незанятых клеток План будет оптимальным, если для всех незанятых клеток выполняется условие
Описание слайда:
Проверка выполнения условия оптимальности для незанятых клеток План будет оптимальным, если для всех незанятых клеток выполняется условие

Слайд 46


Для строки А1: -9<10, -4<7. 0<4, -8<4. Для строки А1: -9<10, -4<7. 0<4, -8<4. Для строки А2 : для А2В3 11> 10 или 11-10=1, 1 записываем в клетку. Для А2В4: 12>6, 12-6=6 записываем в клетку. Для А2В5 12>11, 12-11=1 записываем в клетку. Для строки А3: -8<8, -3<5, 1<3 Для строки А4: 3<11, 13<16
Описание слайда:
Для строки А1: -9<10, -4<7. 0<4, -8<4. Для строки А1: -9<10, -4<7. 0<4, -8<4. Для строки А2 : для А2В3 11> 10 или 11-10=1, 1 записываем в клетку. Для А2В4: 12>6, 12-6=6 записываем в клетку. Для А2В5 12>11, 12-11=1 записываем в клетку. Для строки А3: -8<8, -3<5, 1<3 Для строки А4: 3<11, 13<16

Слайд 47


Выбор клетки, в которую следует послать перевозку Загрузке подлежит клетка соответствующая max[(Ui+Vj)-Cij] Таким образом, выбираем max(1;6;1)=6 клетку А2В4 Отмечаем знаком + клетку, которую надо загрузить, она считается занятой.
Описание слайда:
Выбор клетки, в которую следует послать перевозку Загрузке подлежит клетка соответствующая max[(Ui+Vj)-Cij] Таким образом, выбираем max(1;6;1)=6 клетку А2В4 Отмечаем знаком + клетку, которую надо загрузить, она считается занятой.

Слайд 48


Построение цикла и определение величины перераспределения груза В таблице m+n-1 занятых клеток, поэтому имеется единственный цикл, все вершины которого в занятых клетках. Начинаем движение от клетки с + поочередно проставляем – и +.
Описание слайда:
Построение цикла и определение величины перераспределения груза В таблице m+n-1 занятых клеток, поэтому имеется единственный цикл, все вершины которого в занятых клетках. Начинаем движение от клетки с + поочередно проставляем – и +.

Слайд 49


Находим Q0=min xij, где xij – перевозки, стоящие в вершинах цикла со знаком “-”. Q0=min(50;50;0)=0. Находим Q0=min xij, где xij – перевозки, стоящие в вершинах цикла со знаком “-”. Q0=min(50;50;0)=0. Следовательно, нулевую перевозку перемещаем в клетку А2В4, остальные числа при вычитании и прибавления нуля не изменяются.
Описание слайда:
Находим Q0=min xij, где xij – перевозки, стоящие в вершинах цикла со знаком “-”. Q0=min(50;50;0)=0. Находим Q0=min xij, где xij – перевозки, стоящие в вершинах цикла со знаком “-”. Q0=min(50;50;0)=0. Следовательно, нулевую перевозку перемещаем в клетку А2В4, остальные числа при вычитании и прибавления нуля не изменяются.

Слайд 50


Новый опорный план проверяется на оптимальность Строится новая система потенциалов Клетка А2В4 стала занятой и для нее должно выполняться равенство U2+V4=C24=-1+13=12≠6. Следовательно, надо U2 либо V4 уменьшить на 6. Удобнее изменить V4, т.к. он связан только с U1 . V4=13-6=7 U1=C14-V4=1-7=-6.
Описание слайда:
Новый опорный план проверяется на оптимальность Строится новая система потенциалов Клетка А2В4 стала занятой и для нее должно выполняться равенство U2+V4=C24=-1+13=12≠6. Следовательно, надо U2 либо V4 уменьшить на 6. Удобнее изменить V4, т.к. он связан только с U1 . V4=13-6=7 U1=C14-V4=1-7=-6.

Слайд 51


Проверяется выполнение условий оптимальности для каждой незанятой клетки. Проверяется выполнение условий оптимальности для каждой незанятой клетки. Значение V4 уменьшилось на 6 и в В4 не могут появиться свободные клетки не удовлетворяющие условию оптимальности. Такие клетки могут быть только в строке (столбце) потенциал которой увеличился. U1 увеличился на 6. Строка А1: -3<10; 2<7; 6>4; 7>4. А1В3 и А1В5 не удовлетворяют условию для их находим Ui+Vj-Cij и записываем в левый нижний угол клеток.
Описание слайда:
Проверяется выполнение условий оптимальности для каждой незанятой клетки. Проверяется выполнение условий оптимальности для каждой незанятой клетки. Значение V4 уменьшилось на 6 и в В4 не могут появиться свободные клетки не удовлетворяющие условию оптимальности. Такие клетки могут быть только в строке (столбце) потенциал которой увеличился. U1 увеличился на 6. Строка А1: -3<10; 2<7; 6>4; 7>4. А1В3 и А1В5 не удовлетворяют условию для их находим Ui+Vj-Cij и записываем в левый нижний угол клеток.

Слайд 52


Находим max(2;3;1;1)=3. А1В5 подлежит загрузке, отмечаем ее + и определяем цикл перераспределения. Q0=min(50;50;100)=50. Находим max(2;3;1;1)=3. А1В5 подлежит загрузке, отмечаем ее + и определяем цикл перераспределения. Q0=min(50;50;100)=50. По циклу 50 переносим в А1В5
Описание слайда:
Находим max(2;3;1;1)=3. А1В5 подлежит загрузке, отмечаем ее + и определяем цикл перераспределения. Q0=min(50;50;100)=50. Находим max(2;3;1;1)=3. А1В5 подлежит загрузке, отмечаем ее + и определяем цикл перераспределения. Q0=min(50;50;100)=50. По циклу 50 переносим в А1В5

Слайд 53


Транспортная задача линейного программирования, слайд №53
Описание слайда:

Слайд 54


В полученном опорном плане изменяем систему потенциалов. В полученном опорном плане изменяем систему потенциалов.
Описание слайда:
В полученном опорном плане изменяем систему потенциалов. В полученном опорном плане изменяем систему потенциалов.

Слайд 55


Строим цикл перераспределения. Строим цикл перераспределения.
Описание слайда:
Строим цикл перераспределения. Строим цикл перераспределения.

Слайд 56


Транспортная задача линейного программирования, слайд №56
Описание слайда:

Слайд 57


Транспортная задача линейного программирования, слайд №57
Описание слайда:

Слайд 58


Открытая(несбалансированная) модель транспортной задачи Возможны два случая открытой модели: Суммарные запасы превышают суммарные потребности
Описание слайда:
Открытая(несбалансированная) модель транспортной задачи Возможны два случая открытой модели: Суммарные запасы превышают суммарные потребности

Слайд 59


Транспортная задача линейного программирования, слайд №59
Описание слайда:

Слайд 60


Транспортная задача линейного программирования, слайд №60
Описание слайда:

Слайд 61


Открытая модель решается приведением к закрытой модели. Открытая модель решается приведением к закрытой модели. В случае 1 вводится фиктивный потребитель Bn+1, потребности которого bn+1=∑ai-∑bj В случае 2 вводится фиктивный поставщик Аm+1, потребности которого am+1=∑bj- ∑ai Стоимость перевозки единицы груза до фиктивного потребителя или фиктивного поставщика полагают равной нулю. Получается закрытая задача. При ее решении фиктивному потребителю (поставщику) направляют груз от наименее выгодных поставщиков (потребителей).
Описание слайда:
Открытая модель решается приведением к закрытой модели. Открытая модель решается приведением к закрытой модели. В случае 1 вводится фиктивный потребитель Bn+1, потребности которого bn+1=∑ai-∑bj В случае 2 вводится фиктивный поставщик Аm+1, потребности которого am+1=∑bj- ∑ai Стоимость перевозки единицы груза до фиктивного потребителя или фиктивного поставщика полагают равной нулю. Получается закрытая задача. При ее решении фиктивному потребителю (поставщику) направляют груз от наименее выгодных поставщиков (потребителей).

Слайд 62


Пример
Описание слайда:
Пример

Слайд 63


Транспортная задача линейного программирования, слайд №63
Описание слайда:

Слайд 64


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

Слайд 65


Ответ
Описание слайда:
Ответ

Слайд 66


Вопросы Как формулируется транспортная задача? Как составить первый опорный план в транспортной задаче? В чем сущность метода потенциалов? Как с помощью метода потенциалов опорный план проверяется на оптимальность? Как решается проблема вырождения в транспортной задаче? Как решаются транспортные задачи с нарушенным балансом между спросом и предложением?
Описание слайда:
Вопросы Как формулируется транспортная задача? Как составить первый опорный план в транспортной задаче? В чем сущность метода потенциалов? Как с помощью метода потенциалов опорный план проверяется на оптимальность? Как решается проблема вырождения в транспортной задаче? Как решаются транспортные задачи с нарушенным балансом между спросом и предложением?

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию