Поиск оптимального решения

Поиск оптимальных решений.

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

Краткий комментарий

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

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

Постановка задачи

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

Исходная информация:

ai - количество единиц груза в i- м пункте отправления(i= Поиск оптимального решения - student2.ru );

bj - потребность в j- м пункте назначения (j= Поиск оптимального решения - student2.ru ), в единицах груза;

cij - стоимость перевозки единицы груза из i- го пункта в j- й.

Найти: xij – планируемое количество единиц груза для перевозки из i-го пункта отправления в j-й пункт назначения.

Цель: минимум затрат на перевозку.

Математическая модель задачи выглядит следующим образом.

Целевая функция:

Поиск оптимального решения - student2.ru →min.

ЦФ представляет суммарную стоимость перевозок.

Ограничения:

Поиск оптимального решения - student2.ru , i= Поиск оптимального решения - student2.ru , вывоз груза из i-го пункта отправления равен запасу груза в этом пункте.

Поиск оптимального решения - student2.ru , j= Поиск оптимального решения - student2.ru доставка груза в j-ый пункт назначения равен спросу на груз в этом пункте.

Граничное условие: Поиск оптимального решения - student2.ru , объем перевозимого груза не может быть отрицательным.

Согласно уравнениям ограничений модели количество вывезенного груза должно быть равно количеству принятого Поиск оптимального решения - student2.ru .

Задание и технология выполнения

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

Поставщики Потребители Запасы
А Б В
I
II
III
Спрос  

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

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

Целевая функция имеет вид:

Поиск оптимального решения - student2.ru

Ограничения имеют вид:

Поиск оптимального решения - student2.ru Поиск оптимального решения - student2.ru

Граничные условия

Поиск оптимального решения - student2.ru

Электронная таблица

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рисунке.

Искомые значения xij находятся в блоке ячеек B12:D14. Требования к ограничениям по спросу и запасам представлены соответственно в ячейках B7:D7 и E4:E6. Коэффициенты ЦФ, означающие затраты на доставку расположены в блоке ячеек B4:D4.

Формулы целевой функции и ограничений находятся соответственно в ячейке E15 и ячейках B15:D15 (ограничения по спросу), E12:E14 (ограничения по запасам).

Таблица в режиме отображения значений

Поиск оптимального решения - student2.ru

Поиск оптимального решения - student2.ru

Вид электронной таблицы в режиме отображения формул

Поиск оптимального решения

1. Выполнить команду меню Сервис►Поиск решения.

2. Ввести параметры поиска в окне диалога Поиск решения:

Поиск оптимального решения - student2.ru

Результат поиска оптимального решения

Поиск оптимального решения - student2.ru

Самостоятельная работа

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

Вариант 1  
Задание 1  
Затраты на поставку единицы груза
Поставщики Потребители Запас
B1 B2 B3 B4
A1
A2
A3
Спрос  

Ответ: 462

 
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 4-му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 2-му потребителю зафиксирована и равна 20 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Задание 4  
Затраты на перевозку груза
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1
A2
A3
Потребности  

Ответ: 780

 
Вариант 2  
Задание 1  
Затраты на поставку единицы груза
Поставщики Потребители Запас
B1 B2 B3 B4
A1
A2
A3
Спрос  

Ответ: 13 100

 
Задание 2  
Решить задачу 1 при условии, что запрещена перевозка груза от 2-го поставщика 3-му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.  
Задание 3  
Решить задачу 1 при условии, что поставка груза от 2-го поставщика 4-му потребителю зафиксирована и равна 100 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.  
Задание 4  
Затраты на перевозку груза
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1
A2
A3
Потребности  

Ответ: 720

 
Вариант 3  
Задание 1  
Затраты на поставку единицы груза
Поставщики Потребители Запас
B1 B2 B3 B4
A1
A2
A3
Спрос  

Ответ: 1 650

 
Задание 2  
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 3-му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.  
Задание 3  
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 3-му потребителю зафиксирована и равна 50 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.  
     

Задание 4  
Затраты на перевозку груза
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1
A2
A3
Потребности  

Ответ: 800

 
Вариант 4  
Задание 1  
Затраты на поставку единицы груза
Поставщики Потребители Запас
B1 B2 B3 B4
A1
A2
A3
Спрос  

Ответ: 1 295

 
Задание 2  
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 2-му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.  
Задание 3  
Решить задачу 1 при условии, что поставка груза от 2-го поставщика 3-му потребителю зафиксирована и равна 10 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.  
Задание 4  
Затраты на перевозку груза
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1
A2
A3
Потребности  

Ответ: 790

 
Вариант 5  
Задание 1  
Затраты на поставку единицы груза
Поставщики Потребители Запас
B1 B2 B3 B4
A1
A2
A3
Спрос  

Ответ: 1 272

 
Задание 2  
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 4-му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.  
Задание 3  
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 4-му потребителю зафиксирована и равна 20 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.  
Задание 4  
Затраты на перевозку груза
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1
A2
A3
Потребности  

Ответ: 965

 
Вариант 6  
Задание 1  
Затраты на поставку единицы груза
Поставщики Потребители Запас
B1 B2 B3 B4
A1
A2
A3
Спрос  

Ответ: 1 070

 
Задание 2
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 1-му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.
Задание 3
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 2-му потребителю зафиксирована и равна 50 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.
Задание 4
Затраты на перевозку груза
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1
A2
A3
Потребности  

Ответ: 850

 
Вариант 7  
Задание 1  
Затраты на поставку единицы груза
Поставщики Потребители Запас
B1 B2 B3 B4
A1
A2
A3
Спрос  

Ответ: 482

 
Задание 2  
Решить задачу 1 при условии, что запрещена перевозка груза от 3-го поставщика 3-му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.  
Задание 3  
Решить задачу 1 при условии, что поставка груза от 2-го поставщика 4-му потребителю зафиксирована и равна 50 единиц. Оценить изменение перевозок груза по сравнению с оптимальным вариантом.  
Задание 4  
Затраты на перевозку груза
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1
A2
A3
Потребности  

Ответ: 1 020

 
Вариант 8  
Задание 1  
 
Затраты на поставку единицы груза
Поставщики Потребители Запас
B1 B2 B3 B4
A1
A2
A3
Спрос  

Ответ: 18 010

 
Задание 2  
Решить задачу 1 при условии, что запрещена перевозка груза от 1-го поставщика 4-му потребителю. Определить, как изменились затраты из-за запрета перевозки по сравнению с оптимальным вариантом.  
Задание 3  
Решить задачу 1 при условии, что поставка груза от 1-го поставщика 1-му потребителю зафиксирована и равна 400 единиц. Оценить удорожание перевозок груза по сравнению с оптимальным вариантом.  
Задание 4  
Затраты на перевозку груза
Пункты отправления Пункты назначения Запасы
B1 B2 B3 B4
A1
A2
A3
Потребности  

Ответ: 710

 
       

Задание 5

На трех складах оптовой базы сосредоточена мука в количест­вах, равных 150, 360 и 180 т соответственно. Эту муку необходимо завез­ти в пять магазинов, каждый из которых должен получить 90, 120, 230, 180 и 60 т соответствен­но. С 1-го склада муку не представляется возмож­ным перевозить во 2-й и 5-й магазины, а из 2-го склада в 3-й магазин должно быть завезено 100 т муки. Тарифы на перевозку 1 т муки с каж­дого склада в соответствующие магазины, представлены в таблице:

Склады Тарифы на перевозку 1 т
Магазин №1 Магазин №2 Магазин №3 Магазин №4 Магазин №5
Склад №1
Склад №2
Склад №3

Составьте план перевозок, обеспечивающий минимальную общую стои­мость.

Задание 6

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

Наши рекомендации