Метод потенциалов
Этот метод используется при решении транспортной задачи, суть которой заключается в определении оптимального плана перевозок некоторого однородного груза из 
пунктов отправления 
в 
пунктов потребления 
.
Рассмотрим транспортную задачу, в которой критерием оптимальности является минимальность транспортных расходов по перевозке грузов.
Экономико-математическая модель такой задачи содержит системы линейных уравнений:
,
,
условие неотрицательности переменных 
и целевую функцию
.
Следует иметь в виду, что:
1. Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей 
называется допустимым планом транспортной задачи.
2. Ранг матрицы, составленной из коэффициентов при неизвестных системы основных ограничений задачи, на единицу меньше числа уравнений, т.е. равен 
. Следовательно, число линейно независимых уравнений равно и они определяют вектора, вошедшие в базис, а соответствующие им переменных будут являться базисными.
3. Допустимый план транспортной задачи, имеющий не более отличных от нуля величин 
, называется опорным.
4. Если в опорном плане число отличных от нуля компонент в точности равно , то план является невырожденным, если меньше, то план является вырожденным.
5. План, при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
6. Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения:
.
7. Модель транспортной задачи, удовлетворяющей этому условию, называется закрытой. Если же указанное условие не выполняется, то модель называется открытой.
В случае превышения запаса над заявками
,
вводится фиктивный 
пункт назначения с потребностью 
и соответствующие тарифы считаются равными нулю: 
.
При 
водится фиктивный 
пункт отправления с запасами груза 
и соответствующие тарифы считаются равными нулю: 
.
8. Наилучшим элементом матрицы тарифов С называется наименьший тариф, если решается задача на минимум, наибольший тариф – если решается задача на максимум целевой функции.
Рассмотрим один из методов построения начального опорного плана – метод наименьших тарифов.
Алгоритм построения начального опорного плана методом наименьших тарифов включает следующие этапы:
а) среди тарифов определяется наименьший;
б) клетка с выбранным тарифом заполняется величиной, равной максимально возможному объему груза с учетом ограничений по строке и столбцу. При этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Если одновременно весь груз вывозится от некоторого поставщика и полностью удовлетворяется заявка рассматриваемого потребителя, то в клетку с наименьшим тарифом, принадлежащей строке или столбцу, которые содержат упомянутых поставщика или потребителя, вводят нуль.
в) из оставшихся тарифов вновь находится наилучший (наименьший), и процесс продолжается до тех пор, пока не будет распределен весь груз.
Если модель транспортной задачи открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей, и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю.
9. Дальше полученный план проверяется на оптимальность. Для этого используется метод потенциалов, суть которого состоит в следующем.
План 
транспортной задачи будет оптимальным, если существует система 
чисел 
, называемых потенциалами поставщиков и потребителей соответственно, удовлетворяющая условиям:
Потенциалы 
и 
обозначают оплату за перевозку единицы груза в пунктах потребления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу 
.
Введем так называемое превышение клетки таблицы
.
Тогда признак оптимальности опорного плана транспортной задачи, которая исследуется на минимум, можно сформулировать следующим образом.
Если 
для заполненных клеток и 
для свободных клеток, то рассматриваемый план является оптимальным.
Алгоритм оценки оптимальности плана транспортной задачи методом потенциалов включает следующие этапы.
1) Построение начального плана.
2) Определение значения целевой функции путем суммирования произведений тарифов на объем запланированного к перевозке груза по всем заполненным клеткам таблицы.
3) Проверка условия оптимальности. Определяются потенциалы и . Для каждой заполненной клетки таблицы записываются уравнение . Получается система уравнений с переменными.
Т.к. число переменных больше числа уравнений 
, то система является неопределенной и имеет бесконечное множество решений. Поэтому одному из неизвестных потенциалов и задают произвольное значение, например, для простоты вычислений полагают 
. Тогда остальные потенциалы определяются из приведенных уравнений.
В транспортную таблицу добавляются дополнительная строка и столбец, куда заносятся потенциалы.
Определяются превышения свободных клеток 
.
Если все (решается задача на минимум целевой функции) для свободных клеток, то оптимальный план найден. Если хотя бы одно превышение свободной клетки 
(решается задача на минимум целевой функции), то план не является оптимальным, его можно улучшить, осуществив перераспределение груза.
4) Построение нового опорного плана. Из всех положительных превышений свободных клеток выбирается наибольшая (если поставлена задача на минимум). Клетку, которой соответствует наибольшее превышение, следует заполнить, т.е. направить груз. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других заполненных и связанных с заполняемой клеткой так называемым циклом.
Циклом, или прямоугольным контуром, в таблице транспортной задачи называется ломаная линия, вершины которой расположены в заполненных клетках таблицы, а звенья – вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое – в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл.
Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки «+ » и «– ».
Из объемов груза, стоящих в минусовых клетках, выбираем наименьший. Перераспределяем его по циклу, прибавляя к соответствующим объемам груза, стоящим в плюсовых клетках и вычитая из объемов, стоящих в минусовых клетках таблицы. В результате клетка, которая ранее была свободной, становится заполненной, а одна из заполненных клеток цикла становится свободной.
Полученный новый опорный план проверяется на оптимальность, т.е. возвращаемся к третьему этапу алгоритма.
Примечания.
1. Если в минусовых клетках цикла находятся два (или несколько) одинаковых минимальных значения , то при перераспределении объемов груза освобождается только одна клетка (с наибольшим тарифом 
), а в остальных клетках проставляются нули. Таким образом, во вновь полученном опорном плане число занятых клеток будет равно .
2. Если в оптимальном плане транспортной задачи превышение свободной клетки равно нулю (), то задача имеет множество оптимальных планов. Для клетки с нулевым превышением можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь такое же значение целевой функции.
3. Значение целевой функции на каждой итерации можно рассчитывать следующим образом:
(задача решается на минимум),
где 
величина перемещаемого по циклу объема груза;
превышение свободной клетки, в которую направляется груз при переходе к новому плану;
значение целевой функции на 
той итерации;
значение целевой функции на предыдущей итерации.
Пример. На три базы 
поступил однородный и делимый груз в количествах, соответственно равных 39, 36, 38 ед. Этот груз требуется перевезти в три магазина 
в количествах соответственно 27, 35, 33 ед. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов (ден. ед. за ед. груза):
.
Необходимо составить план перевозок груза с минимальными транспортными издержками.
Решение. 1. Проверим необходимое и достаточное условие разрешимости задачи:
, 
.
Как видно, суммарные запасы груза на базах превышают суммарную потребность в пунктах назначения. Следовательно, модель исходной транспортной задачи является открытой.
Чтобы получить закрытую модель, введем дополнительный (фиктивный пункт назначения 
с потребностью груза, равной 18 ед. (113 – 95). Тарифы перевозки единицы груза с баз к полагаем равными нулю.
Занесем данные в таблицу перевозок.
| 
| 
| 
|
| 
| |
| 
| 
| ||||
| 
| 
| - 4 | |||
| 
| 
| - 2 | |||
|
Используя метод наименьшей стоимости, построим начальный опорный план транспортной задачи.
Среди тарифов из всей таблицы наименьшим является 
, поэтому в клетку 
направляем максимально возможное количество груза. Оно равно 
. Тогда 
и с базы не вывезен груз в количестве 9 ед., а потребность магазина удовлетворена полностью. Столбец таблицы выходит из рассмотрения. Из оставшихся тарифов таблицы наименьшим является 
. Поэтому в клетку 
направляем максимально возможное количество груза, равное 
. Тогда строка выходит из рассмотрения, поскольку с базы вывезен весь груз, а потребность третьего магазина не удовлетворена на 24 ед. Из оставшихся тарифов наилучший 
и 
. Но 
относится ко второй строке , а она вышла из рассмотрения. В клетку 
направляем количество груза, равное 
. При этом потребность третьего магазина удовлетворена, а с третьей базы не вывезены 14 ед. груза. Третий столбец выходит из рассмотрения. Из оставшихся тарифов наилучшими являются 
и 
, которые соответственно принадлежат столбцам и , вышедшим из рассмотрения. Аналогично, тариф 
принадлежит столбцу и поэтому наилучшим теперь будет 
. В клетку 
направляем груз в количестве 14 ед., который оставался на базе . Строка выходит из рассмотрения. Остался один тариф 
. В клетку 
направляем груз в количестве 
ед., поскольку потребность магазина ранее была не удовлетворена на 21 ед. (35 – 14). На базе остались не вывезенными 18 ед. (39 – 21) груза. Направим их фиктивному потребителю, т.е. от 18 е. груза в клетку 
.
В результате получен начальный опорный план
,
который является допустимым, поскольку потребности всех магазинов удовлетворены, а грузы с баз по возможности вывезены.
2. Подсчитаем число заполненных клеток таблицы перевозок, их 6 и должно быть 
. Следовательно, опорный план является невырожденным.
3. Определяем значение целевой функции начального опорного плана:
ден. ед.
4. Проверим оптимальность полученного плана. Найдем потенциалы по заполненным клеткам перевозок, в которых (превышение =0), полагая, что . Решим систему уравнений:
Занесем найденные значения потенциалов в таблицу перевозок и вычислим превышения свободных клеток:
; 
; 
;
; 
; 
.
Начальный опорный план 
не является оптимальным, т.к. 
, поэтому переходим к его улучшению.
5. Выбираем свободную клетку с максимальным положительным превышением (в нашем примере только одна свободная клетка имеет положительное превышение 
). Для этой клетки 
построим цикл перераспределения груза. Для этого в клетку поставим знак «+ », а в остальных вершинах многоугольника чередующиеся знаки «– », «+ »,«– ». Цикл приведен в таблице перевозок.
Из чисел , стоящих в минусовых клетках, выбираем наименьшее, т.е. 
. Прибавляем 9 к объемам грузов, стоящих в плюсовых клетках, и вычитаем 9 из , стоящих в минусовых клетках. В результате получим новый опорный план.
|
|
|
|
|
|
| |
|
|
|
| ||||
|
|
| 
| 
| |||
| 
| 
| ||||
|
| - 4 | - 3 | - 10 |
6. Определим значение целевой функции
ден. ед.
7. Проверяем оптимальность плана 
методом потенциалов, для этого находим потенциалы по заполненным клеткам таблицы, где , полагая, что 
:
Затем рассчитываем превышение свободных клеток:
; 
; 
;
; 
; 
.
Поскольку все превышения свободных клеток неположительны, то план является оптимальным, но не единственным. Последнее следует из того, что клетка 
имеет нулевое превышение и для нее можно построить цикл перераспределения 
, который позволяет установить альтернативный оптимальный план
.
Значение целевой функции при этом плане
ден. ед.,
т.е. совпадает со значением 
, которое является минимальным.
Анализ плана. С первой базы необходимо направить 21 ед. груза в третий магазин, со второй базы направить 27 ед. и 9 ед. в первый и второй магазины соответственно, а груз с третьей базы следует вывозить во второй и третий магазины в количестве 26 и 12 ед. соответственно. При этом на первой базе останется 18 ед. груза. Общая стоимость доставки груза потребителям будет минимальной и составит 487 ден. ед.
Задачи для аудиторной и самостоятельной работы
1. Кондитерская фабрика производит два вида карамели – «Фруктовая» и «Лимонная», используя три основных вида сырья: сахар, патоку и фруктовое пюре. В таблице приведены расходы трех видов сырья на оба вида карамели, запасы сырья и цена 1 т карамели каждого вида.
| Сырье | Расход сырья на 1 т карамели | Запасы | ||
| «Фруктовая» | «Лимонная» | |||
| Песок | 0,5 | 0,6 | ||
| Патока | 0,2 | 0,3 | ||
| Фруктовое пюре | 0,1 | - | ||
| Цена 1 т карамели, тыс. грн. | ||||
Определить план производства карамели каждого вида, обеспечивающий максимальный доход от их реализации.
2. Фирма производит два вида безалкогольных напитков – «Цитрусовый» и «Лимонад» с добавлением натурального сока и пищевых ингредиентов. В таблице приведены расходы двух видов сырья на оба вида напитков, запасы сырья и цена партии (1000 бутылок) напитка.
| Сырье | Расход сырья на партию, т | Запасы | ||
| «Лимонад» | «Цитрусовый» | |||
| Сок | 0,1 | 0,2 | ||
| Ингредиенты | 0,2 | 0,1 | ||
| Цена партии, тыс. грн. | ||||
Определить ежедневный план производства напитков каждого вида, обеспечивающий максимальный доход от их реализации.
3. Автотранспортное предприятие занимается перевозкой пассажиров на двух маршрутах – городском и междугородном. В таблице приведены расходы на техническое обслуживание, горючее и на прочие расходы (амортизация, зарплата и т.д.) автобуса в городском и междугородном режимах работы, предельно-допустимые нормы расходов, установленные администрацией предприятия, и условная цена билета за 100 км пути.
| Виды расходов | Расходы автобуса на 100 км, грн. | Норма грн./д. | ||
| Городской режим | Междугородний режим | |||
| Техобслуживание | ||||
| Горючее | ||||
| Прочие расходы | ||||
| Цена билета, грн. | ||||
Определить количество автобусов в городском и междугороднем режимах, обеспечивающее максимальный доход от их работы. При этом учесть, что на каждом маршруте должны работать не менее 5 автобусов.
4. Птицефабрика выращивает кур-бройлеров, используя три вида кормов: известняк, зерно, бобовую смесь. В таблице приведены данные, характеризующие содержание (по весу) питательных веществ в каждом из видов кормов и их стоимость.
| Вид кормов | Содержание питательных веществ в 1кг | Стоимость (грн./кг) | ||
| Кальций | Белок | Клетчатка | ||
| Известняк | 0,4 | - | - | 0,5 |
| Зерно | 0,001 | 0,1 | 0,02 | |
| Бобовая смесь | 0,002 | 0,5 | 0,09 |
Определить недельный расход ингредиентов, образующих кормовую смесь минимальной стоимости и удовлетворяющую следующим условиям:
1) общее количество смеси на неделю не менее 1 кг;
2) недельное потребление кальция не менее 100г и не более 200г;
3) недельное потребление белка не менее 250г;
4) недельное потребление клетчатки не более 100г.
5. Для поддержания нормальной жизнедеятельности человеку ежедневно необходимо потреблять не менее 118 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в 1 кг каждого вида потребляемых продуктов, а также цена 1 кг каждого из этих продуктов приведены в таблице:
| Питательные вещества | Содержание питательных веществ в 1кг | ||||||
| Мясо | Рыба | Молоко | Сыр | Масло | Крупа | Картофель | |
| Белки | 0,18 | 0,19 | 0,03 | 0,26 | 0,01 | 0,13 | 0,021 |
| Жиры | 0,02 | 0,003 | 0,04 | 0,31 | 0,8 | 0,03 | 0,002 |
| Углеводы | - | - | 0,05 | 0,02 | 0,006 | 0,65 | 0,2 |
| Минеральные соли | 0,01 | 0,01 | 0,007 | 0,06 | 0,02 | 0,02 | 0,01 |
| Цена (грн./кг) |
Составить дневной рацион, содержащий не менее минимальной суточной нормы потребности человека в необходимых питательных веществах при минимальной общей стоимости потребляемых продуктов.
6. На трех мукомольных заводах ежедневно производится 200, 150 и 100 т муки. Мука потребляется тремя хлебозаводами и оптовой базой, ежедневные потребности которых 90, 110, 130 и 120 т. Тарифы перевозок 1 т муки с мукомольных заводов на хлебозаводы и базу заданы матрицей
Составить план перевозки муки, при котором общая стоимость перевозок является минимальной.
7. На трех кирпичных заводах ежедневно производится 20000, 5000 и 10000 штук кирпича. Кирпич необходим на четырех строительных объектах. Ежедневные потребности каждого строительного объекта составляют 5000, 7000, 13000 и 12000 кирпичей. Тарифы перевозок 1 кирпича с заводов на строительные объекты заданы матрицей
Составить план перевозки кирпичей, при котором общая стоимость перевозок является минимальной.
8. Для выполнения четырех видов землеройных работ могут быть использованы экскаваторы четырех типов. Производительность экскаватора 
го типа при выполнении 
й работы задается матрицей
Учитывая, что на каждой из работ может быть занят только лишь один экскаватор и что все экскаваторы должны быть задействованы, найти такое распределение экскаваторов между работами, которое обеспечит максимальную производительность.
9. Решить задачу линейного программирования графоаналитическим методом.
1) 
(min) 2) 
(max) 3) 
(min)
4) 
(min) 5) 
(max) 6) 
(min)
7) 
(min) 8) 
(min) 9) 
(max)
10) 
(min) 11) 
(min) 12) 
(max)
10. Найти целочисленное решение задачи линейного программирования.
1) (max) 2) 
(min) 3) 
(max)
4) 
(max) 5) 
(min) 6) 
(max)
11. Предприятие выпускает три вида продукции: А, В, С, используя при этом три вида ресурсов: 
. Известны удельные затраты ресурсов, их запасы и прибыль, получаемая от реализации единицы продукции.
Необходимо:
1. Составить математическую модель задачи нахождения оптимального плана производства продукции из имеющихся ресурсов, обеспечивающего максимальную прибыль.
2. Построить математическую модель задачи, двойственной к данной.
3. Решить исходную задачу и выписать решение другой, дать экономическое истолкование полученных решений.
4. На основе свойств двойственных оценок оптимального плана провести экономико-математический анализ.
| Ресурсы | А | В | С | Запасы | Ресурсы | А | В | С | Запасы | |
|
| |||||||||
|
| |||||||||
|
| |||||||||
| Прибыль | Прибыль |
12. Заданы мощности поставщиков 
, спрос потребителей 
и матрица тарифов 
.
Считая, что товар, сосредоточенный у поставщиков является однородным и делимым, а стоимость перевозок пропорциональна объему перевозимого товара, составить план перевозок, который обеспечит минимум транспортных затрат.
Необходимо:
1. Составить математическую модель задачи.
2. Решить задачу методом потенциалов.
3. Выписать оптимальный план задачи и выполнить экономический анализ.
Варианты контрольных работ по темам
«Задача рационального использования ресурсов»,
«Транспортная задача»
Предприятие выпускает три вида продукции: А, В, С, используя при этом три вида ресурсов: . Известны удельные затраты ресурсов, их запасы и прибыль, получаемая от реализации единицы продукции.
Необходимо:
1. Составить математическую модель задачи нахождения оптимального плана производства продукции из имеющихся ресурсов, обеспечивающего максимальную прибыль.
2. Построить математическую модель задачи, двойственной к данной.
3. Решить исходную задачу и выписать решение другой, дать экономическое истолкование полученных решений.
4. На основе свойств двойственных оценок оптимального плана провести экономико-математический анализ.
Вариант 1. Вариант 2.
| Ресурсы | А | В | С | Запасы | Ресурсы | А | В | С | Запасы | |
|
|
| |||||||||
|
|
| |||||||||
|
|
Поиск по сайту©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование. Дата создания страницы: 2017-12-12 Нарушение авторских прав и Нарушение персональных данных |
Поиск по сайту: Читайте также: Деталирование сборочного чертежа Когда производственнику особенно важно наличие гибких производственных мощностей? Собственные движения и пространственные скорости звезд |