Глава II. Модели линейного программирования 4 страница

Задачу 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.

Здесь следует иметь в виду, что число неизвестных , а число уравнений – . Следовательно, система уравнений имеет бесконечное число решений. Для однозначности решения один из потенциалов приравнивают к нулю (как правило ).