![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Задачу I¢ можно трактовать следующим образом. Пусть на предприятии решили продать сырье ,
и
вместо производства из него продукции
и
.
Обозначим через
,
и
(7.5¢)
цены единиц сырья.
Справедливое требование к ценам со стороны продающего предприятия состоит в следующем: если взять сырье, идущее на изготовление единицы товара
, то выручка от его продажи должна быть не меньше, чем прибыль от реализации готового изделия (в противном случае нет смысла продавать сырье – лучше изготовить из него товар и получить за него прибыль). Это требование приводит к неравенствам (7.4¢).
Других требований к ценам ,
и
предприятие-продавец предъявлять не вправе. Что же касается покупателя, то для него единственное пожелание заключается в сокращении до минимума расходов на покупку сырья, т. е. величины
.
Решения взаимно двойственных ЗЛП (I) и (I¢) имеет следующий экономический смысл: предприятию безразлично, производить ли продукцию по оптимальному плану (36; 6) и получить максимальную прибыль единиц, либо продать сырье по оптимальным ценам (16; 9; 0) и возместить от продажи равные ей минимальные затраты на сырье
единиц.
Транспортная задача. Распределительный метод
Частным случаем ЗЛП является так называемая транспортная задача. Она состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления в n пунктов назначения
.
При этом в качестве критерия оптимальности берут либо минимальную стоимость перевозок всего груза, либо минимальное время его доставки.
Выберем минимальную стоимость перевозок. Примем обозначения: – тарифы перевозки единицы груза из i -ого пункта отправления в j -ый пункт назначения;
– запасы груза в
;
– потребности в грузе в
;
– количество груза перевозимого из
в
. Тогда математическая постановка транспортной задачи состоит в следующем:
(8.1)
при условиях
(8.2)
(8.3)
(8.4)
Транспортную задачу (8.1) – (8.4), как ЗЛП в канонической форме, решают распределительным методом, являющимся упрощенной модификацией симплекс-метода. Упрощение обусловлено специфичностью систем ограничений (8.2) и (8.3) – неизвестные входят в них лишь по одному разу с коэффициентами, равными единице или нулю.
Исходные данные транспортной задачи записывают в виде таблицы 8.1.
Всякое неотрицательное решение систем линейных уравнений (8.2) и (8.3), определяемое матрицей размерности m ´ n, называют планом транспортной задачи (8.1) – (8.4).
План , m ´ n называют оптимальным планом транспортной задачи (8.1) – (8.4), если целевая функция (8.1) при этих значениях
принимает минимальное значение.
Таблица 8.1
Пункты отправления | Пункты назначения | Запасы | |||||
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ||
![]() | ![]() ![]() | ![]() ![]() | ![]() | ![]() ![]() | ![]() | ![]() ![]() | ![]() |
![]() | ![]() ![]() | ![]() ![]() | ![]() | ![]() ![]() | ![]() | ![]() ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() ![]() | ![]() ![]() | ![]() | ![]() ![]() | ![]() | ![]() ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() ![]() | ![]() ![]() | ![]() | ![]() ![]() | ![]() | ![]() ![]() | ![]() |
Потребности | ![]() | ![]() | ![]() | ![]() | ![]() | ![]() |
Всюду ниже будем рассматривать закрытую модель транспортной задачи, т. е. случай, когда общая потребность в грузе пунктов назначения равна запасу грузов в пунктах отправления
(8.5)
Замечание. Если условие (8.5) не выполняется, то модель транспортной задачи называют открытой. Ее решение сводится к решению закрытой модели, путем введения фиктивных пунктов отправления или потребления с нулевыми тарифами.
Справедлива следующая теорема.
Теорема. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось соотношение (8.5).
Решение транспортной задачи распределительным методом выполняют посредством шагов, на каждом из которых неизвестные разбиваются на базисные и свободные.
Число базисных неизвестных транспортной задачи равно рангу системы линейных алгебраических уравнений (8.2), (8.3) и равно .
Каждому разбиению неизвестных задачи на базисные и свободные соответствует базисное решение, заключающееся в заполнении таблицы поставок (базисном заполнении). Клетки, заполненные базисными неизвестными, называют базисными, а клетки, соответствующие свободным неизвестным, – свободными.
Алгоритм решения транспортной задачи:
1. Находят первоначальное базисное распределение поставок – опорный план.
2. Проверяют опорный план на оптимальность.
3. Если решение оказалось неоптимальным, то переходят к следующему базисному распределению. Процесс повторяют до тех пор, пока базисное решение станет оптимальным.
Как найти опорный план?
Для его нахождения существуют разные методы. Укажем два из них – метод северо-западного угла и метод наименьших затрат на примере транспортной задачи, заданной таблицей 8.2.
Таблица 8.2
![]() ![]() | ![]() | ![]() | ![]() | Запасы |
![]() | ||||
![]() | ||||
![]() |
Окончание таблицы 8.2
![]() | ||||
![]() | ||||
Потребности |
Метод северо-западного угла или диагональный метод. При этом методе на каждом шаге построения опорного плана заполняется верхняя левая клетка («северо-западный угол») оставшейся части таблицы.
Заполняем клетку (1; 1): . В результате запасы груза в пункте
израсходованы. Строка
выпадает из последующего рассмотрения. Заполняем клетку (2; 1):
. Запасы груза в пункте
также израсходованы и строка
выпадает из последующего рассмотрения. Заполняем клетку (3; 1):
. В результате столбец
выпадает из последующего рассмотрения: потребности в грузе пункта
удовлетворены
.
Заполняем клетку (3; 2): . Строка
выпадает из последующего рассмотрения. Заполняем клетку (4; 2):
. Строка
выпадает из дальнейшего рассмотрения. Заполняем клетку (5; 2):
. Столбец
выпадает из последующего рассмотрения
.
Заполняем клетку (5; 3). В ней запасы груза в пункте
и потребности в грузе в пункте
также 25. Следовательно,
. Заполнение клеток завершено. Оно началось с левой верхней клетки (1; 1) и закончилось в клетке (5; 3), т. Е. происходило по диагонали таблицы (см. таблицу 8.3) с севера на запад.
Получили опорный план в виде таблицы 8.2 с числом базисных лееток: .
Таблица 8.3
![]() ![]() | ![]() | ![]() | ![]() | Запасы |
![]() |
Окончание таблицы 8.3
![]() | ||||
![]() | ||||
![]() | ||||
![]() | ||||
Потребности |
Общая стоимость перевозок при таком опорном плане составляет: .
Недостаток метода северо-западного угла заключается в том, что опорный план построен без учета тарифов.
Метод наименьших затрат. На каждом шаге заполняют клетку с наименьшим тарифом. Применим этот метод к рассмотренной выше транспортной задаче.
Минимальный тариф, равный 2, находится сразу в нескольких клетках: (2; 3), (3; 2) и (4; 1). Выберем одну из них, например, (2; 3) и заполним ее: . Исключаем из рассмотрения строку
и считаем потребности пункта
равными
единиц. В оставшейся части таблицы (строки
,
,
и
, столбцы
,
и
) содержатся две клетки (3; 2) и (4; 1) с минимальным тарифом, равным 2. Выберем, к примеру, клетку (3; 2) и заполним ее:
. Исключаем из рассмотрения строку
и считаем потребности пункта
равными
единиц. В оставшейся части таблицы (строки
,
и
и столбцы
,
,
) содержится лишь одна клетка (4; 1) с минимальным тарифом, равным 2. Заполним ее:
. Повторяя предыдущие рассуждения, последовательно выберем и заполним следующие клетки:
(1; 2), ;
(5; 1), ;
(1; 1), ;
(1; 3), .
Получим опорный план в виде таблицы 8.4 с числом базисных клеток .
Таблица 8.4
![]() ![]() | ![]() | ![]() | ![]() | Запасы | ||
![]() | ||||||
![]() | ||||||
![]() | ||||||
![]() | ||||||
![]() | ||||||
Потребности |
Общая стоимость перевозок при таком опорном плане составляет: .
Очевидно, опорный план, полученный методом наименьших затрат, предпочтительнее опорного плана, полученного методом северо-западного угла: .
Но является ли он оптимальным? Ответ на этот вопрос дает следующая теорема (критерий оптимальности).
Теорема. Опорный план транспортной задачи является оптимальным тогда и только тогда, когда ему соответствует система из
чисел
и
удовлетворяющих условиям:
для занятых клеток,
для свободных клеток.
Числа и
, сопоставляемые соответственно каждому пункту отправления и каждому пункту потребления, называют потенциалами пунктов отправления и назначения.
Сформулированный критерий оптимальности позволяет перейти ко второму шагу алгоритма решения транспортной задачи – проверке найденного опорного плана на оптимальность. Процесс проверки осуществляется в следующей последовательности действий.
1° Находя потенциалы и
пунктов отправления и назначения из системы уравнений:
,
где – тарифы, стоящие в заполненных клетках таблицы 8.1.
Здесь следует иметь в виду, что число неизвестных , а число уравнений –
. Следовательно, система уравнений имеет бесконечное число решений. Для однозначности решения один из потенциалов приравнивают к нулю (как правило
).
Дата публикования: 2014-11-03; Прочитано: 239 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!