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

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

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

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

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

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

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

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

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

a_i - количество единиц груза в i- м пункте отправления(i= );

b_j - потребность в j- м пункте назначения (j= ), в единицах груза;

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

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

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

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

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

→min.

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

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

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

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

Граничное условие: , объем перевозимого груза не может быть отрицательным.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариант 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-бальной шкале) (см. табл.). Постройте модель, позволяющую выполнять работы на станках наилучшим образом.