Векторный алгоритм решения некоторых задач линейного программирования

10. Сорокин А.С. Распространение вариационной теоремы П.П.Куфарева на многосвязные области. Вопросы геометрической теории функций. Т.4, Тр. Томск. Ун-та, 1966, с.221-239.

11. Сорокин А.С. Вариационный метод Г.М.Голузина-П.П.Куфарева и формула М.В.Келдыша-Л.И.Седова. ДАН СССР, Т.308, №2, (1989), с.273-277.

12. Сорокин А.С. Параметрическое представление функций в конечносвязных областях. Сиб.матем.ж., Т.38, №5, (1997), с. 1163-1178.

13. Сорокин А.С. Формулы Келдыша - Седова и дифференцируемость по параметру семейств однолистных функций в конечносвязных областях. РАН, Математические заметки, Т.58, №6, (1995), с. 878-889.

14. Дундученко Л.Е. Еще про формулу Шварца для П — связной круговой области. ДАН УССР, №11, 1966, с.1383-1386.

15. Зморович В.А. Об обобщении интегральной формулы Пуассона на П — связные круговые области. ДАН УССР, Т.7, (1958), с. 698-701.

16. ЛаврентьевМ.А., Шабат Б.В. Методы теории функций комплексного переменного. М-Л, 1963.

17. Александров И.А. Вариационные формулы для однолистных функций в двусвязных областях. Сиб.матем.ж., Т.4, №5, (1963), с. 967-976.

18. Сирык Г.В. О конформном отображении близких областей. Успехи математических наук, Т.9, № 5(71), (1956), с. 57-60.

19. Сирык Г.В. Обобщение вариационной формулы М.А.Лаврентьева для конформного отображения близких односвязных областей на случай двусвязных областей. Изв. Вузов, Математика, Т.5, (1960), с. 152-159.

Автор статьи:

Сорокин Андрей Семенович канд. физ.-мат.наук, доцент, ст.н.с. (филиал КузГТУ , г. Новокузнецк) тел.: 8(3843) 772459

УДК 519.6

В. А. Гоголин

ВЕКТОРНЫЙ АЛГОРИТМ РЕШЕНИЯ НЕКОТОРЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задача линейного программирования состоит в оптимизации линейной формы

п

Ь

7=1

Хі > 0, і = 1,..п

XАрХ^. < (>)Б;, ] = п +1,..

7 =1

Область допустимых решений представляет выпуклый многогранник п -мерного пространства с наибольшим возможным числом граней (п + т). Экстремальные значения (1) достигаются на его границах: в угловых точках, на гиперплоскостях, на гиперпрямых - в частности в точке пересечения п из (п + т) гиперплоскостей, определяемых уравнениями для (2, 3). Наряду с симплекс-методом [1] имеются и другие методы решения линейных программ: метод эллипсоидов [2], метод внутренней точки [3] и их модификации.

Для выделения точки на границе области допустимых решений с максимальным значением

линейной формы предлагается векторный алгоритм, состоящий в следующем. Все неравенства (2, 3) переписываются через знак меньше или равно. Выделяется градиент линейной формы

С = {С1,....,Сп}, градиенты (нормали) гиперплоскостей (2) N1 = {—1,0,...,0},...,Ып{0,...,0,—1} и градиенты (нормали) гиперплоскостей (3) Ы] = {А]1,..., Ар }0' = п + 1,...п + т). Здесь

обозначения А^ сохранены, хотя у некоторых координат могут быть изменены знаки за счет изменения знаков неравенств. При таком изменении знаков координат нормалей гиперплоскостей, нормали будут обращены во внешность выпуклого многогранника допустимых решений. Определяем наиболее близкую к градиенту С нормаль Ык (к = 1,...,п + т) гиперплоскости и ее номер

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

76

В. А. Гоголин

исключаем ее из (1) и (2, 3), понижая размерность задачи на единицу. Этот процесс понижения размерности продолжается до тех пор, пока останется только одна переменная, например Х1> с линейной формой Ц( X) = С • Х1 + О. и с ограничениями вида 0 < А < Х1 < Б.

Максимальное значение линейной формы достигается при Х1 = Б, если С > 0; и при Х1 = А,

если С < 0 Затем процесс нахождения всех координат точки максимума выполняется в обратном порядке: по Х1 вычисляем, например, Х2, затем по ним - Х3 и так далее до Хп. При нахождении минимума - знаки координат ее градиента меняются на обратные.

Пример 1.

Максимизировать линейную форму

Ц( Х) = 2 Х1 + Х2 + 4 Х3 + 3Х4 при ограничениях:

1) Х1 > 0; 2) Х2 > 0; 3) Х3 > 0; 4) Х4 > 0;

5) Х1 + 3Х2 + Х3 + 2Х4 < 12;

6)3Х1 + 2Х3 + Х4 > 4;

7) 4Х1 + 2Х2 + 3Х3 + Х4 > 6;

8) Х1 + Х2 + Х3 + Х4 > 1.

Координаты градиента и внешних нормалей с учетом знаков ограничений имеют вид:

С = {2; 1; 4; 3}

^N1 ={—1;0;0;0}, N2 ={0; —1;0;0}

N 3 ={0; 0; — 1; 0}, Ы4 = {0; 0; 0; — 1},

Ы5 = {1; 3; 1; 2} Ы6 = {— 3; 0; — 2; — 1},

Ы7 ={— 4; — 2; — 3; — 1} Ы8 ={—1; —1; —1; —1}

После расчетов косинусов углов между градиентом и внешними нормалями, выбираем наибольший - между С и N5 .

Выражаем из равенства 5) переменную Х = 12 — 3Х2 — Х3 — 2Х4 и ее подстановкой в

линейную форму и ограничения имеем трехмерную задачу: максимизировать линейную форму Ц Х) = — 5Х2 + 2 Х3 — Х4 + 24 при ограничениях:

1) 3Х2 + Х3 + 2Х4 < 12;

2) Х2 > 0; 3) Х3 > 0; 4) Х4 > 0;

6)9Х2 + Х3 + 5Х4 < 32;

7) 10Х2 + Х3 + 7Х4 < 44;

8) 2Х2 + Х4 < 11.

Здесь координаты градиента и внешних нормалей с учетом знаков ограничений имеют вид:

С = {- 5; 2; -1}, Щ ={3; 1; 2},

N2 = {— 1; 0; 0}, N3 = {Э; — 1; 0}, N4 = {Э;0; — 1}

N6 = {9; 1; 5}, N7 = {10; 1; 7}, N8 = {2; 0; 1}

После расчетов косинусов углов между градиентом и внешними нормалями, выбираем наибольший - между С и N2. ТогдаХ2=0.

Отсюда имеем двухмерную задачу максимизации линейной формы Ц( Х) = 2 Х3 — Х4 + 24 при ограничениях

1) Х3 + 2Х4 < 12; 3) Х3 > 0; 4) Х4 > 0;

6) Х3 + 5Х4 < 32; 7) Х3 + 7Х4 < 44;

8) Х4 < 11.

Координаты градиента и внешних нормалей с учетом знаков ограничений имеют вид:

С = {2; — 1}, N1 = {1; 2},

N3 ={—1;0} N4 ={0; — 1},

N6 ={1;5} N7 = {Ц;7} N8 = {);1}

После расчетов косинусов углов между градиентом и внешними нормалями, выбираем наибольший - между С и N4. ТогдаХ4=0.

Отсюда имеем уже одномерную задачу максимизации Ц(Х) = 2Х 3 + 24 при ограничениях

1) Х3 < 12; 3) Х3 > 0; 6) Х3 < 32; 7) Х3 < 44. Таким образом, задача свелась к отысканию максимума линейной функции Ц(Х ) = 2Х3 + 24

на интервале [0,12], откуда тахЬ(Х) = 48 при

Х1=0, Х2=0, Хз=12, Х4=0.

Пример 2.

Минимизировать линейную форму Ц( Х) = 2 Х1 + Х 2 + 4 Х 3 + 3Х 4

при тех же ограничениях (1-8).

Координаты «градиента» и внешних нормалей граней области допустимых решений с учетом знаков ограничений имеют вид:

С = {- 2;—1;—4;—з},

N1 ={—1;0;0;0} N2 ={0; —1;0;0},

N3 = {0; 0; —1;0} N4 = {0; 0; 0; —1},

^N5 = {I; 3; 1; 2} N6 ={— 3;0; — 2; — 1},

N7 = {— 4; — 2; — 3; — 1} N8 ={—1; —1; — 1; — 1} Сводим задачу к трехмерной, исключая Х4 из ограничения 7) по условию наибольшей близости градиента к нормали грани области допустимых решений Х4 = 6 — 4Х1 — 2Х2 — 3Х3 . После подстановки в линейную форму и ограничения имеем трехмерную задачу: минимизации Ц( Х) = —10 Х1 — 5Х2 — 5Х3 +18 при ограничениях

1) Х1 > 0;

2) Х2 > 0; 3) Х3 > 0; 4) 4Х1 + 2Х2 + ^.Х3 < 6;

5) ^.Х1 + Х2 + 5Х3 > 0;

6)^.Х^1 + 2Х2 + 5Х3 > 10;

8) 5Х1 + 3Х2 + 4Х3 > 7.

Размерность задачи по принятому критерию близости градиента и нормали грани области допустимых решений понижается на единицу после исключения Х3 из ограничения 4). Новая двухмерная задача имеет вид:

минимизировать линейную форму Ц X) = — 10/3Х1 — 5/3Х 2 + 8 при ограничениях

1) Х1 > 0; 2) Х2 > 0; 3) 2Х1 + Х2 < 3;

5) — X + 7Х2 < 30; 6) Х1 — 4X2 > 0;

8) Х1 — X2 <3.

Одномерная задача свелась к минимизации

Ц(Х) = 3 при ограничениях 4/3<Х\ <3/2.

Соответственно, min Ь( Х) = 3 при

4/3 < Х1 < 3/2, Х2 = 3 — 2 Х1, Х3 = Х4 = 0.

Достаточным условием применения векторного алгоритма, как следует из его процедуры, является включение в область допустимых решений всех ограничений. Например, когда все ограничения (3) имеют один знак неравенств и один знак правых частей. К таким задачам, в частности, относится задача о распределении ресурсов и задача о смесях. Число операций симплекс-метода имеет

порядок т , число операций векторного алгорит-

2

ма - порядок тп2

СПИСОК ЛИТЕРАТУРЫ

1. Данциг Д. Линейное программирование, его применение и обобщение. М.: Прогресс, 1966, 600с.

2. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании. Ж. вычисл. матем. и ма-тем. физ., 1980, 20:1, с 51-68.

3. Дикин И.И. Метод внутренней точки в задачах линейного и нелинейного программирования. Издательство: Эдиториал УРСС, 2010, 120 с.

Автор статьи:

Г оголин Вячеслав Анатольевич, докт.техн.наук, проф. каф. математики КузГТУ Email: inna-e@inbox.ru

УКД 519.21

А.В. Бирюков, Е.В.Гутова АНАЛИТИЧЕСКАЯ ГРАНУЛОМЕТРИЯ

Рассмотрим дисперсную систему из частиц случайных размеров и формы. Размер частицы определяет ее диаметр х, распределенный с плотностью /(х) и начальными моментами т(к), равными математическому ожиданию к-ой степени диаметра.

Форму частицы характеризуют ее меры сферичности

р=8/х2 , , д=У/х2 где 5, V — площадь поверхности и объем частицы.

Обозначим через 5, V, р, Ц математические ожидания. Тогда

5 = рт, V = цт.

Величина §/V равна суммарной площади поверхности частиц в единичном объеме. Она является основным параметром динамики дробления. Любая частица имеет геометрическую или физическую характеристику, пропорциональную к — ой степени ее диаметра.

Интегрируя отношение хк[(х)/ т(к) в границах от 0 до х, получим гранулометрическую функцию £ (х, к), которая дает описание фракционного состава дисперсной системы по заданной суммарной характеристике частиц.

В частности, при к = 3 она дает описание фракционного состава по суммарному объему частиц, что чаще всего востребовано инженерной практикой.

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

Если т{к)и п(к) — моменты распределения диаметра частиц и их степеней, то

т(1)=10 / п(-1)’ ; т(2)=2^1) / п(-2)’ где п(-1) - среднее гармоническое диаметров сечений.

Эти формулы получены регрессионным анализом результатов лабораторных исследований.

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

/ со = 2 (1 — х), где за масштабную единицу принята правая гра-