Пиши Дома Нужные Работы

Обратная связь

Математическая модель прямой задачи

 

при условии что,

Математическая модель двойственной задачи:

 

Экономический смысл переменных:

 

Z – целевая функция прямой задачи (суммарные затраты);

Z' – целевая функция двойственной задачи (суммарная потенциальная прибыль от перевозки груза);

Сij – стоимость перевозки единицы продукции из i-го пункта в j-ый;

Xij – объем перевозок от i-го поставщика j-му потребителю;

Ui – условная плата перевозчику за вывоз единицы груза из i-го пункта отправления;

Vj – условная плата перевозчику за доставку единицы груза в j-ый пункт назначения.

 

Потребители Поставщики В1 В2 В3 В4 В5 Ui
А1 350 4 8 50 -W +W U1=-2
6 9 0
А2 9 100 +W 200 -W 0 U2=-6
5 10 4
А3 7 150 -W 100 +W 8 250 6 0 U3 =0
11
Vj V1=6 V2=11 V3=8 V4=6 V5= 6 W=50

 

Проверяем на вырожденность:

R=m+n-1=3+5-1=7

m= 3 – количество поставщиков;

n = 5 – количество потребителей.

Базисных клеток 7, план не вырожден.

 

 

Проверяем план на оптимальность, используя метод потенциалов. Для базисных клеток составляем систему уравнений Ui + Vj = Сij находим значение потенциалов так как переменных на 1 больше, чем уравнений,

то переменной U3 присваиваем значение 0 и решаем систему уравнений, получаем

 

Проверяем выполнение неравенства в свободных: клетках Ui + VjСij

 

более всего не выполняется условие Ui + VjСij, сюда ставим «+W», строим контур перераспределения W и находим его значение:

Перераспределяем W=50 по контуру.

 

 

Составляем следующий план:

 

 

Потребители Поставщики В1 В2 В3 В4 В5 Ui
А1 350 -W 50 +W U1=-6
4 8 6 9 0
А2 9 150 +W 150 -W 0 U2=-6
5 10 4
А3 +W 100 -W 150 8 250 6 0 U3 =0
7 11
Vj V1=10 V2=11 V3=8 V4=6 V5= 6 W=100

 



Так как переменных на i больше, чем уравнений, то переменной U3 присваиваем значение 0 и решаем систему уравнений, получаем

 

проверяем выполнение неравенства в свободных клетках Ui + VjСij,

 

 

 

– более всего не выполняется условие Ui + VjСij, сюда ставим «+W», строим контур перераспределения W и находим его значение: перераспределяем W=100 по контуру.

 

 

Составляем следующий план:

 

Потребители Поставщики В1 В2 В3 В4 В5 Ui
А1 250 4 8 6 9 150 0 U1=-3
А2 9 250 5 10 4 50 0 U2=-3
А3 100 7 11 150 8 250 6 0 U3 =0
Vj V1=7 V2=8 V3=8 V4=6 V5= 3

 

Для базисных клеток Ui + Vj = Cij . Составляем для них систему уравнений. Принимаем U3=0, так как в строке потенциала U3 наибольшее количество (три) базисных клеток, решаем систему уравнений и находим количественное значение Ui и Vj :

 

Проверяем выполнение неравенства Ui + VjСij, в свободных клетках:

 

 

Неравенство Ui + VjСij,в свободных клетках выполняется, построенной план является оптимальным.

 

Анализ решения.

 

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

– от поставщика А1 перевозится 250 ед. продукции потребителю В1; 150 ед. продукции остается у поставщика;

– от поставщика А2 перевозится 250 ед. продукции потребителю В2; 50 ед продукции остается у поставщика;

– от поставщика А3 перевозится 100 ед.продукции потребителю В1, 150 ед, потребителю В3, 250 ед. потребителю В4 .

 

2.Суммарные затраты на изготовление и перевозку продукции:

 

ден. ед.

 

Контрольные вопросы.

1.Как сформулировать постановку транспортной задачи?

2.Какие величины в математической модели транспортной задачи постоянные и какие переменные?

3.Как составить математическую модель прямой и двойственной транспортной задачи?

4.Какая клетка в плане транспортной задачи называется «базисной» и какая «свободной»?

5.Приведите пример сбалансированной и несбалансированной транспортной задачи. Как сбалансировать исходный план транспортной задачи?

6.Поясните понятие «вырожденность» и «невырожденность» плана. Как построить «невырожденный» план?

7.Алгоритм метода наименьшего (наибольшего) элемента.

8.Метод потенциалов и его алгоритм.

9.Какой план транспортной задачи называется опорным?

10.Какой критерий оптимальности плана транспортной задачи?

11.Поясните понятие «коэффициент перераспределения груза – W» и как он определяется?

12.Как построить контур перераспределения W?

13.Анализ решения транспортной задачи.

 

Лекция. Целочисленное программирование.






ТОП 5 статей:
Экономическая сущность инвестиций - Экономическая сущность инвестиций – долгосрочные вложения экономических ресурсов сроком более 1 года для получения прибыли путем...
Тема: Федеральный закон от 26.07.2006 N 135-ФЗ - На основании изучения ФЗ № 135, дайте максимально короткое определение следующих понятий с указанием статей и пунктов закона...
Сущность, функции и виды управления в телекоммуникациях - Цели достигаются с помощью различных принципов, функций и методов социально-экономического менеджмента...
Схема построения базисных индексов - Индекс (лат. INDEX – указатель, показатель) - относительная величина, показывающая, во сколько раз уровень изучаемого явления...
Тема 11. Международное космическое право - Правовой режим космического пространства и небесных тел. Принципы деятельности государств по исследованию...



©2015- 2024 pdnr.ru Все права принадлежат авторам размещенных материалов.