Лекции по "Развитию операционных систем"

Лекция 20.

 

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

 

Пример 17.2.  В пунктах производится однородная продукция в коли-чествах единиц. Готовая продукция поставляется в пункты , потребности которых составляют единиц. Стоимость cij перевозки единицы продукции из пункта Ai в пункт Bj заданы матрицей :

.

Требуется:

1) методом потенциалов  найти план перевозок продукции, при котором минимизируются суммарные затраты по ее доставке потребителям;

2)  вычислить суммарные  затраты fmin.

 

Решение.

1)  Найдем суммарные  запасы продукции и суммарные  потребности  900+100=1500; b1+b2+b3+b4=200+650+150+300=1300. Поскольку ,то есть отсутствует баланс между производимой продукцией и потребнос-тями, то мы имеем задачу открытого типа. Вводим фиктивного поставщика A4, который имеет запас продукции в объеме (един.). Все тарифы на доставку продукции фиктивного поставщика равны нулю, т.е. c15=c25=c35=0

Данные задачи заносим в таблицу 1.

Табл. 1.

Поставщики	Потребители					ui
	B1 (200)	B2 (650)	B3 (150)	B4 (300)	B5 (200)
A1 (500)	7	7	8	4 300	0 200	0
A2 (900)	6 100	1 650	2 150	7	0 0	0
A3 (100)	4 100	7	5	6	0	- 2
vj	6	1	2	4	0

 

Начальный опорный план получим по правилу «минимального элемента».

Загрузку начинаем с клетки, которой соответствует наименьший тариф cij≠0 всей матрицы тарифов. В нашем случае минимальным тарифом является с22=1, который соот-ветствует клетке (2, 2). В эту клетку вписываем x22=min (650; 900)=650. Исключаем второй столбец. У поставщика A2 осталось еще 250 единиц продукции, которые располагаем следующим образом: 100 единиц в клетку (2, 1) и 150 единиц в клетку (2, 3). Исключаем вторую строку и третий столбец. Но потребителю B1 необходимо еще 100 ед. продукции, которые берем у поставщика A3, и помещаем в клетку (3, 1). Исключаем первый столбец и третью строку. 500 единиц продукции у поставщика A1 размещаем следующим образом: 300 единиц в клетку (1, 4) и 200 единиц – в клетку (1, 5).

Полученный нами план является вырожденным, так как не выполняется условие базисных клеток: m+n-1=3+5-1=7, а число заполненных клеток равно 6.

В одну из базисных клеток, например, в клетку (2, 5) таблицы 1 вписываем число нуль - «нуль-загрузку», и эту клетку считаем базисной.

 

Замечания: Нельзя вписывать 0 в клетки (3, 2) и (3, 3), поскольку образуется цикл. Если вписывать 0 в другие незанятые клетки, то произойдет перераспределение продукции, количество которого равно 0. И в итоге заполниться клетка (2, 5).

 

Теперь условие базисных клеток выполняется: m+n-1=3+5-1=7. В результате получено опорное решение, которое запишем матрицей

.

 

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

ui+vj=cij,

где ui – потенциал i-го поставщика;

      vj – потенциал j-го потребителя;

      cij – тариф заполненной клетки.

В нашем случае получаем следующие уравнения:

Полагая v4=0, получаем следующие потенциалы:

          u1=0                               v1= 6                    v3= 4

          u2=0                             v2= 1                     v4=0

          u3= - 2                           v3= 2

Все полученные данные заносим в таблицу 1.

Далее вычисляем оценки свободных клеток по формуле:  .

      s11=c11-(u1+v1) =7-(0+6) =1 ³ 0          s32=c32-(u3+v2) = 7-(-2+1) = 8 ³ 0

      s12=c12-(u1+v2) = 7-(0+1) =6 ³ 0          s33=c33-(u3+v3) = 5-(-2+2) = 5 ³ 0

      s13=c13-(u1+v3) = 8-(0+2) =6 ³ 0           s34=c34-(u3+v4) = 6-(-2+4) = 4 ³ 0

      s24=c24-(u2+v4) = 7-(0+4) =3 ³ 0           s35=c35-(u3+v5) = 0-(-2+0) = 2 ³ 0

 

Поскольку все sij>0, то полученный план является оптимальным и единственным, который можно представить в виде матрицы

.

 

2)  Суммарные затраты fmin при этом будут составлять:

В пункте A1 нераспределенными остались 200 единиц продукции.

Ответ: ,  fmin=3150 ден.ед.

,

 

 

п.18.  Дискретное программирование.

 

18.1.  Классические задачи

целочисленного программирования.

 

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

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

Существует огромное количество задач с дискретной природой. Прежде всего, это задачи с физической неделимостью многих факторов и объектов расчета. Дискретными являются задачи с логическими переменными, принимающие только два значения – нуль или единица (вариант отвергается или принимается).

Иногда дискретное программирование называется целочисленным. Этот термин некоторые математики считают неправильным, так как, строго говоря, дискретное – не обязательно целочисленное. Например, ряд вместимостей (в м3) 1,3; 1,6; 1,9; … - дискретный, но не целочисленный. Отсюда целочисленное программирование правильно считать частным случаем дискретного.

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

Прежде чем прейти к рассмотрению методов решения ЗЦП, сначала обратимся к некоторым моделям задач данного раздела.

 

1.  Общая задача целочисленного программирования.

Математическая модель задачи имеет такой же вид, как модель ЗЛП, только на переменные накладывается условие целочисленности, т.е. .

 

2.  Задача о контейнерных  перевозках (задача о рюкзаке).

Эта задача формулируется так. Контейнер оборудован m отсеками вместимостью для перевозки n видов продукции . Виды продукции характе-ризуются свойством неделимости, т.е. их можно брать в количестве 0, 1, 2, … единиц. Пусть – расход i-го отсека для перевозки единицы j-й продукции. Обозначим через полезность единицы j-й продукции (это может быть цена реализации, прибыль и др.). Требуется найти план ( – количество единиц j-й продукции, погруженной в контейнер) перевозки, при котором максимизируется общая полезность рейса. Модель задачи примет вид

при ограничениях на вместимость отсеков

,

условии неотрицательности

,

условии целочисленности.

- целые   

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

 

3.  Задача о назначении (проблема выбора, задача о женихах  и невестах).

Один из видов этих задач рассматривался в разделе «Элементы теории графов» («Паросочетания»). В общем виде эта задача формулируется так.

Имеется n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-й работы . Необхо-димо назначить исполнителей на работы, чтобы добиться максимальной полезности при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должен быть закреплен только один исполнитель.

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

Итак, приходим к следующей математической модели задачи: найти план назна-чения , который масимизирует суммарную полезность назначений

при следующих ограничениях: каждый исполнитель назначается только на одну работу

,

на каждую работу назначается только один исполнитель

,

условие неотрицательности и целочисленности (булевости)

.

Легко видеть, что задача о назначении – частный случай транспортной задачи при . Однако с учетом специфики задачи для ее решения разработаны специаль-ные, более эффективные, алгоритмы.

 

4.  Задача коммивояжера (бродячего торговца).

Математическая модель этой задачи была введена в разделе «Элементы теории графов» («Гамильтонов цикл»).

 

 

18.2.  Суть методов дискретной оптимизации.

 

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

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

В первом приближении методы целочисленной оптимизации можно разделить на две основные группы: точные и приближенные. К точным относятся методы отсечения и комбинаторные методы (метод ветвей и границ). Это универсальные методы дискретной оптимизации. Кроме универсальных, имеется много специальных точных методов, учи-тывающих специфику задачи. Однако точные методы имеют слабую сходимость. Многие экспериментальные и прикладные задачи не удалось решить точными методами за десят-ки и сотни тысяч итераций, хотя их конечность теоретически доказана. Трудности машин-ной реализации точных методов привели к появлению различного рода приближенных методов, построенных на использовании особенностей конкретной задачи. Среди прибли-женных методов наметились два направления: 1)  разработка детерминированных эврис-тических алгоритмов, учитывающих специфику задачи;  2)  использование случайного поиска в сочетании с локальной оптимизацией.

Общая идея решения задачи дискретного программирования методами отсечения состоит в следующем. Исходная задача решается сначала без учета ограничений целочис-ленности. Если полученный оптимальный план удовлетворяет условиям целочисленности, то задача решена. В противном случае к ограничениям исходной задачи добавляется но-вое, обладающее следующими свойствами:  1)  полученный нецелочисленный план нару-шает это ограничение;  2)  любой целочисленный допустимый план исходной задачи заве-домо удовлетворяет и новому ограничению. Затем задача решается с учетом нового ограничения. В случае необходимости добавляется еще одно ограничение и т.д. Геомет-рически каждому новому ограничению соответствует поверхность, которая отсекает от области допустимых решений некоторую его часть с оптимальной точкой с нецелыми координатами, но не затрагивает ни одной из целочисленных точек этого многогранника.