Тема 3 Целочисленное программирование 4 страница

БП СП				СЧ

Получим новый опорный план (0;0;1).План является оптимальным и удовлетворяет условиям целочисленности. Функция имеет максимальное значение Z(X)=13

Задания для самостоятельного решения по теме №3

Тема 4. Транспортная задача

Задача 5

На трех базах А₁, А₂, А₃ имеется однородный груз в количестве а₁, а₂, а₃ единиц. Этот груз нужно перевезти в пять пунктов В₁, В₂, В₃, В₄, В₅ в количестве b₁, b₂, b₃, b₄, b₅ единиц соответственно. Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов С:

.

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

.

Решение

Исходные данные ТЗ записываются в таблице

В левом верхнем углу пишем тарифы на перевозку грузов от поставщиков к потребителям.

Значения тарифов берутся из матрицы С, которая обычно дается в условии задачи.

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

Поставка -это величина, обозначающая количество груза, которое перевозится из пункта отправления в пункт получения .

!!! Все поставки !!!

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

План перевозок - это совокупность всех поставок .

Оптимальный план перевозок- это такой план перевозок, при котором общая стоимость всех перевозок минимальна.

Таблица 25 Матрица перевозок

	В1	В2	В3	В4	В5	Запасы на складе
А1
А2
А3
Потребности

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

Если получаем модель открытого типа, то ее обязательно нужно привести к модели закрытого типа с помощью введения фиктивного поставщика или потребителя с недостающим объемом грузов и нулевыми тарифами на перевозку.

Заполним транспортную таблицу методом северо – западного угла

Поставки вписываются в клетки матрицы перевозок, начиная с левого верхнего угла в правый нижний угол.

Фактически это означает, что товар вывозится по порядку от каждого поставщика: сначала вывозится груз от первого поставщика до тех пор, пока у первого поставщика не кончатся запасы, затем от второго поставщика, затем от третьего и т.д.

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

Процесс продолжается до тех пор, пока не будут вывезены все запасы или не удовлетворены все потребности

Таблица 26.

	В1	В2	В3	В4	В5	Запасы на складе
А1
А2
А3
Потребности

Определяем стоимость перевозки методом северо- западного угла.

Заполним таблицу методом минимального элемента.

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

Сначала выбираются и заполняются клетки с минимальными тарифами на перевозку, а затем с более высокими тарифами. Размеры тарифов идут по возрастанию.

Стараемся в клетки с минимальными тарифами вписать максимально возможные поставки.

Таблица 27.

	В1	В2	В3	В4	В5	Запасы на складе
А1
А2
А3
Потребности

Определяем стоимость перевозки методом минимального элемента.

Сравним стоимость перевозки двумя методами.

Выгоднее перевозить грузы по схеме, заполненной методом минимального элемента.

Если количество заполненных клеток равно m+n-1, то план перевозок называется невырожденным.

Если количество заполненных клеток не равно m+n-1, то план перевозок называется вырожденным.

Если количество клеток меньше, чем m+n-1, нужно дописать нулевые поставки в свободные ацикличные клетки, чтобы количество клеток стало равным m+n-1.

Проведем проверку плана перевозки методом минимального элемента на оптимальность.

Для проверки плана на оптимальность применим метод потенциалов.

Потенциалы, их экономический смысл.

Векторы A=(а₁, а₂...., а_m ) и B=(b₁, b₂...., b_n ) называются потенциалами поставщиков и потребителей соответственно, если их координаты удовлетворяют соотношениям

Для заполненных клеток

для х_ij > 0, i = 1,2,…, m, j =1,2,…, п.

Определим потенциалы и по базисным клеткам.

Для этого решим систему уравнений , для х_ij > 0, i = 1,2,…, m, j =1,2,…, п, которая имеет бесконечное множество решений.

Для нахождения частного решения системы одно из значений потенциала задают произвольно, на пример, полагают

Определяем значения потенциалов:

тогда

Проверяем выполнение условия оптимальности для всех свободных клеток. Для этого вычисляем при x_ij =0.

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

Получили две неоптимальные клетки (2,4) и (3,4)

Если все > 0 , то план оптимален, вычисляют значение целевой функции и решение задачи заканчивается.

Если в свободной клетке <0, приступают к улучшению решения путем перемещения перевозок по циклу.

Клетка называется ацикличной, если она не образует с другими клетками замкнутый цикл.

Циклом называется многоугольник, у которого:

Все стороны расположены в строках и столбцах матрицы.

Все угла многоугольника прямые.

Все вершины расположены в заполненных клетках, за исключением, может быть одной.

Стороны многоугольника могут пересекаться, но точка пересечения может не быть вершиной цикла:

рисунок 1

Число вершин в цикле должно быть четно!!!

Если среди свободных клеток найдется хотя бы одна, в которой величина , то решение может быть улучшено.

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

Таблица 29.

	В1	В2	В3	В4	В5	Запасы на складе
А1			Sn S1   Sn S1   Sn S1   Sn S1   4
А2
А3
Потребности

Переместим по циклу, включающему в себя клетки (1;3), (1;4),(2;3),(2;4) поставку в клетку с координатами (2;4)

Снова проверяем полученный план перевозок на оптимальность с помощью метода потенциалов.

Если план все еще не оптимален, процедура улучшения продолжается до тех пор, пока не будет найдено оптимальное решение.

Таблица 30.

	В1	В2	В3	В4	В5	Запасы на складе
А1
А2	Sn S1   Sn S1   Sn S1   Sn S1   100
А3
Потребности

Для полных клеток

пусть , тогда

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

Получили одну неоптимальную клетку (3,1)

Переместим по циклу, включающему в себя клетки (3;1), (3;2),(2;1),(2;2) поставку в клетку с координатами (3;1)

Таблица 31.

	В1	В2	В3	В4	В5	Запасы на складе
А1
А2
А3
Потребности

Для полных клеток

пусть , тогда

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

Все клетки оптимальны. План оптимален.

Решите транспортную задачу методом потенциалов. Решение

Таблица 1.

ai bj

Проверим уравнение баланса. Сумма запросов потребителей должна быть равна сумме запасов продукции на складе.

Матрица перевозок (транспортная матрица) имеет вид:

Таблица 2

	В1	В2	В3	В4
В1
В2
В3
В4

Построим начальное опорное решение, методом «северо-западного угла»

Таблица 3.

	В1	В2	В3	В4
В1
В2
В3
В4

Проверим правильность составления плана по количеству базисных клеток (их должно быть N=m + n – 1, остальные клетки — свободные).Так как количество заполненных клеток меньше чем 4+4-1=7, то вводим две нулевых поставки в пустые ацикличные клетки.

Таблица 4.

	В1	В2	В3	В4
В1			4
В2				2
В3
В4

Для заполненных клеток

пусть , тогда

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

Получили две неоптимальные клетки (3;2) и (3;3)

Переместим по циклу, включающему в себя клетки (1;2), (1;3), (2;3), (2;4), (3;2), (3;4) поставку в клетку с координатами (3;2)

Таблица 5.

	В1	В2	В3	В4
В1			4
В2				2
В3
В4

Для заполненных клеток

пусть , тогда

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

Происходит зацикливание

Поэтому более дешевого плана перевозки нет

. 2100

Задания для самостоятельного решения по теме №4

Задание. На трех базах А₁, А₂, А₃ имеется однородный груз в количестве а₁, а₂, а₃ единиц. Этот груз нужно перевезти в пять пунктов В₁, В₂, В₃, В₄, В₅ в количестве b₁, b₂, b₃, b₄, b₅ единиц соответственно. Затраты на перевозку груза между пунктами поставок и потребления заданы матрицей тарифов С:

.

Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Задание

Задание

Дата добавления: 2017-02-01