На главную v-garant.ru
Функции в области экономики Модель Леонтьева Управление и планирование Транспортные задачи Экономический анализ Математический анализ Вычисление длины дуги кривой Криволинейный интеграл 2-го рода Матрицы и определители Многочлены

Учебник по высшей математике

Альтернативный оптимум в транспортных задачах

Признаком наличия альтернативного оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (Xопт1).Сделав перераспределение грузов относительно клетки, имеющей Δij = 0, получим новое оптимальное решение (Хопт2), при этом значение целевой функции (транспортных расходов) не изменится. Если одна оценка свободных переменных равна нулю, то оптимальное решение находится в виде

где 0 ≤ t ≤ 1.

Рассмотрим конкретную задачу, имеющую альтернативный оптимум.

Пример 1. На трех складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырем хлебозаводам в количестве: 30, 80, 60, 110 т соответственно.

Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей Функции двух переменных В естествознании встречаются ситуации, когда одна величина является функцией нескольких других:

Решение. Составим распределительную таблицу в виде табл. 23.6.

По методу минимального тарифа найдем исходное решение. Определим потенциалы строк и столбцов. Найдем оценки свободных клеток:

Так как Δ12 = 4 > 0, то перераспределим грузы относительно клетки (1,2):

Занесем полученное перераспределение грузов в распределительную таблицу и вычислим потенциалы занятых и оценки свободных клеток (табл. 23.7).

Получим

Так как Δ33 = 0, то задача имеет альтернативный оптимум и одно из решений равно

Стоимость транспортных расходов составляет: L(Xопт1) = 1550 усл. ед.

Произведем перераспределение грузов относительно клетки (3,3):

Занесем в распределительную таблицу полученное перераспределение грузов, вычислим потенциалы занятых и оценки свободных клеток (табл. 23.8):

Так как Δ14 = 0, получили еще одно решение:

Стоимость транспортных расходов составит L(Хопт2) = 1550 усл. ед.

Данная задача имеет два оптимальных решения Хопт1 и Xопт2, общее решение находится по формуле

где 0 ≤ t ≤ 1.

Найдем элементы матрицы общего решения:

Итак,

Стоимость транспортных расходов составляет 1550 усл. ед.

Вырожденность в транспортных задачах

При решении транспортной задачи может оказаться, что число занятых клеток меньше, чем m + п - 1. В этом случае задача имеет вырожденное решение. Для возможного его исключения целесообразно поменять местами поставщиков и потребителей или ввести в свободную клетку с наименьшим тарифом нулевую поставку. Нуль помещают в такую клетку, чтобы в каждой строке и каждом столбце было не менее одной занятой клетки.

Рассмотрим вырожденность в транспортной задаче на примере.

Пример 2. Фирма осуществляет поставку бутылок на три завода, занимающиеся производством прохладительных напитков. Она имеет три склада, причем на складе 1 находится 6000 бутылок, на складе 2 — 3 000 бутылок и на складе 3 — 4 000 бутылок. Первому заводу требуется 4000 бутылок, второму заводу — 5 000 бутылок, третьему заводу — 1000 бутылок. Матрицей

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

Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки была минимальной?

Решение. Запишем исходные данные в распределительную таблицу (табл. 23.9), найдем исходное опорное решение по методу минимального тарифа. Число заполненных клеток равно 5, т + п - 1 = 6, следовательно, задача является вырожденной.

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

Так, для нахождения потенциала и3 поместим нулевую поставку в клетку (3,2), после чего представляется возможным вычислить остальные потенциалы.

Оценки свободных клеток следующие:

Все оценки отрицательные, получили оптимальное решение:

Таким образом, со склада 1 целесообразно поставить 3000 бутылок второму и четвертому заводам, со склада 2 — 2000 бутылок второму заводу и 1000 бутылок третьему, со склада 3 — 4000 бутылок первому заводу, при этом стоимость транспортных расходов будет минимальной и составит 28 000 усл. ед.

 

Открытая транспортная задача

При открытой транспортной задаче сумма запасов не совпадает с суммой потребностей, т.е.

При этом:

а) если

то объем запасов превышает объем потребления, все потребители будут удовлетворены полностью и часть запасов останется невывезенной. Для решения задачи вводят фиктивного (n + 1)-потребителя, потребности которого

Модель такой задачи будет иметь вид

при ограничениях:

б) если

то объем потребления превышает объем запасов, часть потребностей останется неудовлетворенной. Для решения задачи вводим фиктивного (m + 1)- поставщика

:

Модель такой задачи имеет вид

при ограничениях:

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

Определение оптимального варианта перевозки грузов с учетом трансформации спроса и предложений

Рассмотрим следующую задачу.

Составить оптимальный план перевозки грузов от трех поставщиков с грузами 240, 40, 110 т к четырем потребителям с запросами 90, 190, 40 и 130 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей

Решение. Запасы грузов у поставщиков:  = 390 т. Запросы потребителей:  = 450 т; так как

  < то вводим фиктивного поставщика с грузом а4ф = 450 - 390 = 60 т.

Тариф фиктивного поставщика 4ф примем равным 20 усл. ед.

Так как т + п – 1 = 7, а число занятых клеток равно 6, то для исключения вырожденности введем в клетку (2, 2) нулевую поставку. Оценки свободных клеток:

(табл. 23.10).

Оценка свободной клетки (1,3) больше нуля, перераспределим грузы:

Запишем полученное перераспределение грузов в табл. 23.11.

Имеем

Получили оптимальное решение:

Стоимость транспортных расходов — 3120 усл. ед.

Экономический анализ задач с использованием графического метода Проведем экономический анализ рассмотренной выше задачи по производству мороженого.

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

Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной. Первоначальная задача является исходной. Эти две задачи тесно связаны между собой и образуют единую двойственную пару. Различают симметричные, несимметричные и смешанные двойственные задачи.

Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов


Схема исследования графика функции