Файл: Понятие переменной в программировании. Виды и типы переменных (ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ ИССЛЕДОВАНИЯ ПЕРЕМЕННЫХ В ПРОГРАММИРОВАНИИ).pdf

Другой уровень абстракции требует принципиально иных решений, новой конфигурации «железа», новых команд для нового «железа». Но это уже, что называется, другая история…

ГЛАВА 3 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ КОМПЬЮТЕРНЫМ ПЕРЕБОРОМ КОМБИНАЦИЙ ВЕЛИЧИН ИСКОМЫХ ПЕРЕМЕННЫХ

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

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

Как известно [2,3], задачи линейного программирования подразде­ляются на общие, канонические и стандартные. В общих задачах ограни­чения на переменные представлены некоторым количеством уравнений и неравенств. В канонических задачах ограничения заданы в виде уравне­ний, а в стандартных только неравенствами.

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

Между тем вычислительные возможности компьютеров позволяют существенно снизить затраты времени и усилий исследователей в реше­нии такого рода задач. Предлагается общее описание вычислительной программы, решающей такого рода задачи. Считается, что математическая модель задачи линейного программирования построена (записаны ограни­чения в виде равенств, неравенств, выражение целевой функции, содержа­щие искомые величины). Порядок действий:

1. Задаться численной величиной целевой функции, заведомо большей или меньшей предполагаемого ее значения в зависимости от смысла задачи.
2. Для общих и канонических задач из общего числа искомых пере­менных выбрать основные переменные, число их не более числа равенств.

---

209

1. Неосновные переменные перенести в правую часть уравнений.
2. Систему уравнений разрешить относительно основных перемен­ных аналитически, либо решать численно на каждом шаге вычислений.
3. Составить циклы перебора значений неосновных переменных, вложенные друг в друга (для стандартных задач пункты 2,3,4 опускаются, так как деление на основные и неосновные переменные теряет смысл - за­даются изменения каждой переменной).
4. Задать шаг изменения каждой неосновной переменной в цикле.
5. Задать длину интервала изменения каждой неосновной перемен­ной, учитывая величины правых частей исходной системы ограничений.
6. Внутрь системы вычислительных циклов вставить решение си­стемы линейных уравнений относительно основных переменных и провер­ку условий в виде неравенств. Если все условия выполняются, то вычис­ляется значение целевой функции.
7. Далее при тех же условиях сравнивается значение целевой функ­ции с предыдущим лучшим ее значением и, если последнее лучше, то ее величина запоминается вместе с соответствующими величинами всех ис­комых переменных.
8. Так продолжается, пока не будут исчерпаны все шаги в преде­лах заданных интервалов изменения переменных.
9. Для повышения уверенности в получении оптимального резуль­тата можно повторять вычисления, уменьшая шаг и (или) увеличивая ин­тервал изменения некоторых переменных.

Далее рассматривается несколько примеров, решение которых вы­полнялось с применением языка программирования turbobasic.

Пример 1. Задача на составление смеси [1]

Составляется комбинированный корм из трех злаков: кукурузы, ов­са и ржи. Калорийность и содержание витамина С в одном кг каждого зла­ка, а также цена одного кг злака указаны в табл. 1 ниже [1].

Таблица 1 - Калорийность, содержание витамина С в одном кг каждого злака, цена оДного кг злака

Параметры	Кукуруза	Овес	Рожь
Ккал	200	175	100
Витамин С (г)	5	1	3
Цена (руб)	6	4	1

Требуется составить наиболее дешевый комбинированный корм, 1 кг которого содержал бы не менее 125 ккал и не менее 2 г витамина С.

Решение. Обозначим содержание кукурузы, овса и ржи в 1 кг ком­бикорма символами x₁, x₂ и x₃ (кг) соответственно. По условию задачи эти переменные удовлетворяют следующей системе ограничений:

---

x₁ + x₂ + x₃ = 1, 8^1 + 7X2 + 4X3 > 5, 5xi + X2 + ЗХ3 > 2, xi > 0,X2 > 0,X3 > 0.

Требуется найти план, доставляющий минимум функции затрат

r = 6 xi + 4 X2 + X3 ® min

Ниже приведен полный текст программы в символах языка про­граммирования, решающей поставленную задачу:

r0=i000

for xi=0 to i step .00i for x2=0 to i step .00i x3=i-x2-xi

if x3>=0 and 8*xi+7*x2+4*x3>=5 and 5*xi+x2+3*x3>=2 then_ r=6*xi+4*x2+x3

if r<r0 and x3>=0 and 8*xi+7*x2+4*x3>=5 and 5*xi+x2+3*x3>=2_ then r0=r : xi0=xi : x20=x2 : x30=x3

next x2 : next xi

print r0, xi0, x20, x30

Из текста программы видно, что в качестве основной переменной выбрана x₃, a x₁ и x₂- неосновные переменные, могущие принимать зна­чения в интервале от 0 до i. Внутрь тела циклов изменения величин x_i и x₂ вставлена математическая модель задачи. Если выполняется первый набор условий при произвольной комбинации величин x_i и x₂, то это до­пустимая комбинация переменных и для нее вычисляется целевая функ­ция. Выполнение второго набора условий означает, что для данной комби­нации величин переменных значение целевой функции оказалось лучше прежнего, и оно запоминается вместе с соответствующими величинами всех переменных. Таким образом, в процессе счета производится улучше­ние показаний целевой функции и в итоге вычислений оказывается луч­ший результат. Это напоминает поиск в симплекс-методе, только здесь нет необходимости искать вершины выпуклых многогранников.

Вычисления с приведенными в программе числовыми данными приводят к результату: r0 » 2.002, x_i0 = 0, x₂₀ » 0.334, x₃₀ » 0.666. Точный результат из [i]: r0 = 2, x_i0 = 0, x₂₀ =i/3, x₃₀ = 2/3.

В другом варианте решения для изменения неосновных переменных можно использовать генератор случайных чисел rnd в интервале между 0 и i, тогда вычислительная программа несколько изменится:

r0=i000

for s=i to i000 step i

xi=rnd : x2=rnd : x3=i-x2-xi

if x3>=0 and 8*x1+7*x2+4*x3>=5 and 5*x1+x2+3*x3>=2 then_ r=6*x1+4*x2+x3

if r<r0 and x3>=0 and 8*x1+7*x2+4*x3>=5 and 5*x1+x2+3*x3>=2 then r0=r : x10=x1 : x20=x2 : x30=x3

next s : print r0, x10, x20, x30

Здесь параметр s обозначает номер шага в процессе вычислений. Ре­

зультат:

r0 » 2.002455, x₁₀ » 0.0000241, x₂₀ » 0.3341163, x₃₀ » 0.665864

Пример 2. Транспортная задача [2,3].

Имеются три поставщика и четыре потребителя. Мощность по­ставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары “поставщик - потребитель” сведены в табл. 2 по­ставок, расположенную ниже. Искомый объем перевозки от z-того постав­щика у-тому потребителю указан в правом нижнем углу каждой клетки и обозначен как xij. В левом верхнем углу каждой клетки приведен коэффи­циент затрат на перевозку единицы груза для каждой пары “поставщик - потребитель”.

---

Задача ставится следующим образом. Найти объемы перевозок Ху для каждой пары “поставщик - потребитель” так, чтобы:

1. мощности всех поставщиков были реализованы;
2. спросы всех потребителей были удовлетворены;
3. суммарные затраты на перевозку были бы минимальны.

Суммарные затраты на перевозку выражаются через коэффициенты затрат следующим образом:

^{r = x}₁₁^{+ 2x}₁₂^{+ 5x}₁₃^{+ 3x}₁₄^{+ x}₂₁^{+ 6x}₂₂^{+ 5x}₂₃^{+ 2x}₂₄^{+ 6x}₃₁⁺
+3x32 +7x33 + 4x34.

Таблица 2 - Затраты на перевозку единицы груза для каждой пары

«поставщик - потребитель»

Мощность поставщиков	Потребители и их спрос
	1	2	3	4
	20	110	40	110
60	1 Х11	2 Х12	5 Х13	3 Х14
120	1 Х21	6 Х22	5 Х23	2 Х24
100	6 Х31	3 Х32	7 Х33	4 Х34

Решение. Математическая модель задачи представляется следую­щим образом. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных xij. Чтобы мощность каждого из поставщиков была реализована, надо составить уравнение ба­ланса для каждой строки таблицы поставок, т.е.

^x₁₁^{+ x}₁₂^{+ x}₁₃^{+ x}₁₄^{= 60,}

x₂₁ + x₂₂ + x₂₃ + x₂₄ = 120, (1)

x31 + x32 + x33 + x34 = 100.

Чтобы спрос каждого из потребителей был удовлетворен, уравне­ние баланса должно быть составлено для каждого столбца таблицы поста­вок:

^x₁₁^{+ x}₂₁^{+ x}₃₁^{= 20, x}12 ^{+ x}22 ^{+ x}32 ^{= 110,} x13 + x23+ x33 = 40,

(2)

^x₁₄^{+ x}₂₄^{+ x}₃₄^{= 110.}

Объемы перевозимых грузов не могут быть отрицательными, по­этому

Xij>0 (i = 1,2,3; j =1,2,3,4).

Суммарные затраты должны быть минимальны

r = Хц + 2 Xj2 + 5X13 + 3xi4 + X21 + 6 X22 + 5 X23 + i

(3)

^+2x₂₄^{+ 6x}₃₁^{+ 3x}₃₂^{+ 7x}₃₃^{+ 4x}₃₄^.

Особенности этой задачи таковы:

---

*ограничения представлены системой уравнений (транспортная за­дача задана в канонической форме);

*коэффициенты при переменных системы уравнений равны 1 или 0;

*каждая переменная входит в систему ограничений дважды: один раз в систему уравнений (1), и один раз в систему (2).

*суммарная мощность поставщиков равна суммарному спросу по­требителей (закрытая модель транспортной задачи).

Общее число переменных равно 12. Для закрытой модели транс­портной задачи ранг матрицы системы уравнений (1), (2) на единицу меньше общего числа уравнений [2]. Это максимальное число линейно не­зависимых уравнений. Отсюда имеем 6 основных (базисных) и 6 неоснов­ных переменных.

Выбор вида переменных отчасти произволен, надо только иметь в виду, что в каждом уравнении систем (1),(2) должно быть не менее одной основной и одной неосновной переменной. Ниже системы уравнений (1), (2) переписаны и в них для наглядности помечены черточкой базисные переменные.

Из этой системы выразить основные переменные через неосновные очень просто, так как коэффициенты при всех переменных равны единице:

Теперь можно записать программу вычислений искомых перемен­ных:

Интервал изменения каждой неосновной переменной задавался из следующих соображений: рассматривалась правая часть каждого уравне­ния системы (5), она не должна при предельных условиях делаться отрица­тельной. Для первого уравнения системы (5) каждое слагаемое правой ча­сти по отдельности не должно превышать число 60 (это интервал для пе­ременных x11, x12, x14). Из пятого и шестого уравнений соответственно имеем интервал 110 для x22 и x24. Наименьший интервал для x33 получается из третьего уравнения, он равен 160. Увеличение интервалов сверх найден­ных значений приведет к росту времени вычислений и не улучшит резуль­тат, уменьшение может привести к потере оптимального результата.

Наши вычисления по приведенной программе дали полное совпа­дение с оптимальным результатом в [2]:

На вычисления при записанных данных уходит около трех секунд, за это время просматривается более восьмисот тысяч комбинаций величин неосновных переменных, чтобы отыскать оптимальную комбинацию. Бы­ло сделано вычисление при шаге изменения переменных, равном пяти. Ре­зультат от этого не изменился, зато время счета выросло в десятки раз. Ес­ли же взять шаг изменения равным единице, то это увеличит время вычис­лений ровно в миллион раз, и они продлятся около месяца.

---