Презентация на тему "Формализм задачи линейной оптимизации на примере транспортной задачи"

Содержание

• 
  Слайд 1
  

  Формализм задачи линейной оптимизации на примере транспортной задачи

• 
  Слайд 2
  

  Вопрос . Постановка транспортной задачи . Решение средствами MS Excel.

• 
  Слайд 3
  

  Вопрос 1. Постановка транспортной задачи . Решение средствами MS Excel.

• 
  Слайд 4
  

  Считаем, что некоторая однородная продукция находится у несколькихпоставщиков в различных объёмах. Необходимо доставить эту продукцию рядупотребителей в разных количествах. Известны стоимости перевозки единицыпродукции от каждого поставщика каждому потребителю. Требуется составить такой план перевозок, при котором суммарные затраты на перевозку всех грузов минимальны.

• 
  Слайд 5
  
• 
  Слайд 6
  

  Рассмотрим постановку и математическую модель одной из задач линейной оптимизации, которая получила название транспортной задачи. Необходимо доставить от поставщиков i( ) некоторый однородный груз (товар) в объеме aiединиц потребителям с минимальными транспортными издержками (здесь mи n – конечные числа).

• 
  Слайд 7
  

  Потребность в данном товаре каждого j-го потребителя известна и составляет bjединиц. Известны также cij – величины стоимости перевозки единицы груза от i-го поставщика к j-му потребителю. Следует составить такой план перевозок xij, при котором суммарная стоимость перевозки груза (товара) будет минимальной, т.е.

• 
  Слайд 8
  

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

• 
  Слайд 9
  

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

• 
  Слайд 10
  

  Пусть на складах А1, А2, АЗ, А4, А5 хранится однотипная продукция в количестве соответственно 100, 150, 350, 200, 200 единиц. Эту продукцию необходимо доставить потребителям В1, В2, В3, В4, В5 по их заказам: 100, 200, 200, 300, 200 единиц соответственно. Стоимость перевозки одной единицы груза из каждого пункта отправления в каждый пункт назначения задается следующей таблицей: Закрытая транспортная задача

• 
  Слайд 11
  
• 
  Слайд 12
  

  Табличнаяпостановка задачи

• 
  Слайд 13

  Математическая модель

  Введение переменных X11- кол-во груза которое нужно вести от 1 поставщика 1 потребителю; X12- кол-во груза которое нужно вести от 1 поставщика 2 потребителю; X13- кол-во груза которое нужно вести от 1 поставщика 3 потребителю; X14- кол-во груза которое нужно вести от 1 поставщика 4 потребителю; X15- кол-во груза которое нужно вести от 1 поставщика 5 потребителю;

• 
  Слайд 14
  

  Введение переменных X21- кол-во груза которое нужно вести от 2 поставщика 1 потребителю; X22- кол-во груза которое нужно вести от 2 поставщика 2 потребителю; X23- кол-во груза которое нужно вести от 2 поставщика 3 потребителю; X24- кол-во груза которое нужно вести от 2 поставщика 4 потребителю; X25- кол-во груза которое нужно вести от 2 поставщика 5 потребителю; итд.

• 
  Слайд 15
  

  Введение переменных Общая запись Xij- кол-во груза которое нужно вести от i поставщика j потребителю, где i=1..5, j=1..5

• 
  Слайд 16
  

  2. Определение целевой функции F=4x11+3x12+5x13+2x14+3x15+7x21+x22+2x23+3x24+x25+ 9x31+2x32+4x33+5x34+6x35+x41+3x42+6x43+4x44+10x45+5x51+ +8x52+15x53+6x54+15x55

• 
  Слайд 17
  

  2. Ограничения x11+x12+x13+x14+x15=100 x21+x22+x23+x24+x25=150 x31+x32+x33+x34+x35=350 x41+x42+x43+x44+x45=200 x51+x52+x53+x54+x55=200

• 
  Слайд 18
  

  2. Ограничения x11+x21+x31+x41+x51=100 x12+x22+x32+x42+x52=200 x13+x23+x33+x43+x53=200 x14+x24+x34+x44+x54=300 x15+x25+x35+x45+x55=200 Xij>=0 демонстрация

• 
  Слайд 19

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

  Три поставщика одного и того же продукта располагают в планируемый период следующими запасами этого продукта: первый- 120 условных единиц, второй- 100 и третий 80 единиц. Этот продукт должен быть перевезен к трем потребителям, спросы которых соответственно равны 90, 90 и 120 условных единиц. Приведенная ниже таблица содержит показатели затрат, связанных с перевозкой продукта из i-го пункта отправления в j-й пункт потребления. Требуется перевезти продукт с минимальными затратами.

• 
  Слайд 20
  
• 
  Слайд 21
  

  Транспортная задача 3 Заводы фирмы расположены в городах Минске и Витебске. Они доставляют товары на склады городов Могилев, Гомель и Брест. Затраты на перевозку 1 т товара представлены в таблице. Завод в Минске выпускает 800 т товаров, а в Витебске – 500 т. Могилевский склад вмещает 400 т, Гомельский – 600 т, а Брестский - 300 т. Как следует транспортировать товар для минимизации цен на перевозки.