Задача линейного программирования, которая является частным случаем задачи оптимизации , записывается следующим образом:

n
F=?(cj xj) ???max(min, Const)
? j=1
? n
??? aij xj <= bi
? j=1
? dj<=xj<=Dj
? i=1,...,m; j=1,...,n

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

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

УПРАЖНЕНИЕ 1. Задача распределения ресурсов

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

Рассмотрим следующий пример.

Требуется определить, в каком количестве надо выпускать продукцию четырех типов Прод1, Прод2, ПродЗ, Прод4, для изготовления которой требуются ресурсы трех видов: трудовые, сырье, финансы. Количество ресурса каждого вида, необходимое для выпуска единицы продукции данного типа, называется нормой расхода. Нормы расхода, а также прибыль, получаемая от реализации единицы каждого типа продукции, приведены в таблице. Там же приведено наличие располагаемого ресурса.

Табл. 6.1.

Составим математическую модель, для чего введем следующие обозначения:

xj - количество выпускаемой продукции j-го типа, j = 1,...,4 ;
bi - количество располагаемого ресурса i-го вида, j=l,...,3 ;
ai j - норма расхода i-ro ресурса для выпуска единицы продукции j-го типа;
cj - прибыль, получаемая от реализации единицы продукции j-го типа.

Теперь приступим к составлению модели.

Как видно из таблицы, для выпуска единицы Прод1 требуется 6 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 6х1 единиц сырья, где х1 — количество выпускаемой продукции Прод1. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид:
1+5х2+4х3+3х4 <= 110.

В этом ограничении левая часть равна величине потребного ресурса, а правая показывает количество имеющегося ресурса.

Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид:

F=60х1+70х2+120х3+130х4 ? max
х1234<=16
1+5х2+4х3+3х4<=110 (6.1.1)
1+6х2+10х3+13х4<=100
хj>=0; j=1,...,4

Задачу, имеющую 4 переменных, представить на плоскости невозможно, поэтому ее следует решать аналитическим методом.

Основные положения симплекс-метода.

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

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

В геометрии есть такое понятие "симплекс". Симплексом тела в k-мерном пространстве называют совокупность k+l его вершин. Так, для плоскости при к = 2 симплексом будут три вершины треугольника, при к = 3 - четыре вершины четырехгранника и т. д. С учетом этого понятия аналитический метод решения задачи линейного программирования называют симплекс-методом. Вычисления, обеспечивающие определение значения целевой функции и переменных в одной вершине, называются итерацией.

Решение задачи с помощью симплекс-метода будем рассматривать на примере задачи, математическая модель которой имеет вид (6.1.1).

По сравнению с (6.1.1) в системе (6.1.2) введены дополнительные переменные yi и выполнен переход от системы неравенств к системе уравнений. Следует подчеркнуть, что с точки зрения содержания величина yi равна величине неиспользованого ресурса.

F=60х1+70х2+120х3+130х4 ? max
х1234+y1=16
1+5х2+4х3+3х4+y2=110 (6.1.2)
1+6х2+10х3+13х4+y3=100
хj>=0; yi>=0; j=1,...,4; i=1,...,3

Систему (6.1.2) перепишем в виде:

F=0 - (-60х1 - 70х2 - 120х3 - 130х4) ? max
y1=16 - (х1234)
y2=110 - (6х1+5х2+4х3+3х4) (6.1.3)
y3=100 - (4х1+6х2+10х3+13х4)
хj>=0; yi>=0; j=1,...,4; i=1,...,3

Систему (6.1.3) можно представить в виде таблицы:

Табл. 6.2.

Эта таблица называется симплекс-таблицей и является основной формой решения задачи линейного программирования. В этой таблице все переменные делятся на свободные и базисные. Свободные - переменные находятся в ячейках C3:F3, базисные - в ячейках A5:A7. Если переменная свободная , то ее значение равно нулю. В таблице все основные переменные свободные, следовательно, х1234=0

Значения базисных переменных приведены в ячейках B5:B7, следовательно

y1=16; y2=110; y3=100.

Действительно, если х1234=0, т.е. продукция не выпускается, то величина y неиспользованного ресурса будет равна всему имеющемуся ресурсу, и прибыль при этом будет равна 0 (B4=0).

Решения бывают допустимыми и оптимальными. Каждое решение имеет свой признак. Приведем эти очень важные признаки:

Признак 1 - определяет , является ли полученное решение допустимым. Согласно этому признаку решение является допустимым, если в столбце свободных членов B5:B7 (целевая функция не рассматривается) все величины неотрицательные.

Признак 2 - определяет наличие оптимального решения, при этом возможны 2 варианта:

Признак 2а) Целевая функция имеет минимальное значение в том случае, когда все элементы в строке целевой функции C4:F4 (свободный член не рассматривается) будут отрицательными. Следовательно в таблице приведено решение при минимизации целевой функции. Действительно, если ничего не выпускать, то х1234=0 и при этом прибыль будет F=B4=0

Признак 2б) Целевая функция имеет максимальное значение в том случае, когда все элементы в строке целевой функции C4:F4 будут положительными.

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

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

Табл. 6.3.

Из этой таблицы видно, что в столбце свободных членов все элементы положительные, тогда по признаку 1 решение является допустимым. В строке целевой функции все элементы также положительные. Следовательно, согласно признаку 2б) решение является оптимальным в смысле максимизации целевой функции. В этом случае оптимальным решением будут величины:

х1*=10; х3*=6 ( которые являются базисными);
х2*= х4*=0 (так ка они свободные);
целевая функция F=1320

Таков результат решения задачи. Но это еще не все. Симплекс-таблица является мощным средством для выполнения анализа. Из последней таблицы видно, что свободные переменные y1= y3=0, а базисная переменная y2=26. Это значит, что в оптимальном плане величины неиспользованных трудовых и финансовых ресурсов равны нулю. Следовательно, эти ресурсы используются полностью. Вместе с тем, величина неиспользованных ресурсов для сырья y2=26, значит, имеются излишки сырья.

(Б.Я.Курицкий "Поиск оптимальных решений средствами Excel 7.0" стр.91)

УПРАЖНЕНИЕ 2: Определить время встречи двух людей, идущих навстречу друг другу.

Уточним условия задачи. Требуемой величиной здесь является время движения людей навстречу друг другу. Обозначим его t. Исходными данными служат начальное расстояние s между двумя пешеходами и скорость их движения v1 и v2.

Далее нужно уточнить, как движутся пешеходы? Они могут двигаться с остановками, с ускорением и начать свое движение в разные моменты времени. Будем считать, во-первых, что пешеходы вышли навстречу друг другу одновременно, во-вторых, примем, что они движутся равномерно с постоянными скоростями. При этих предположениях движение пешеходов можно описать следующими уравнениями:

s1 = vl * t
s2=v2*t
s=s1+s2.

Первое и второе уравнения выражают предположения о равномерном характере движения пешеходов, а третье - что сумма длин пройденных ими путей должна быть равна расстоянию s.

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

Задача: найти время движения пешеходов, идущих навстречу друг другу.

Дано: х - начальное расстояние
v1 - скорость первого пешехода
v2 - скорость второго пешехода

Треб: t - время движения

где:
s1 = vl * t
s2=v2*t
s=s1+s2

при:
v1>0
v2>0
s>0

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

s > 0 и v1,v2 > 0.

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

Метод решения этой задачи можно выразить формулой, которая получается из системы уравнений, включенной в постановку задачи:
t=s / (v1+v2).

Эту формулу вполне можно использовать для решения данной задачи и без ЭВМ, например с помощью калькулятора. На персональном компьютере решения такого рода конкретных задач можно получить в диалоге с ЭВМ с помощью команд языка Бейсик:
s=240 <=
v1=40 <=
v2=60 <=
s=240 <=
t=s / (v1+v2) <=
?t <=

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

Сценарий"Движение навстречу".

Соответствующий этому сценарию алгоритм приведен ниже:

Алгоритм:

алг "движение навстречу"
НАЧ
вывод ("движение людей")
запрос("расстояние: s=", s)
запрос("скорость: v1=",v1)
запрос("скорость: v2=",v2)
если s<=0 то
вывод ("недопустимо:s<=0")
если v1 <= 0 или v2 <= 0 то
вывод ("недопустимо:v<=0" ) и
если s>0 и v1 >0 и v2>0 то
* вызов подпрограммы (см.ниже)
t = s/ (vl+v2) вывод ("время пути=",t)
КОН

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

Сцена 2 "График движения":

В этой сцене предполагается отображение в динамике графика движения пешеходов. По горизонтали указываются координаты положения пешеходов х1 и х2, а по вертикали - время движения t. Начальное положение пешеходов в момент времени t=0: для первого пешехода х1 =0, а для второго - х2= s.

Движение людей в соответствии с принятыми нами предположениями будут описываться соотношеяиями:

x1(t)=v1*t
x2(t)=s - v2*t

Для моделирования движения примем некоторую величину dt (приращение времени), используя которую можно будет рассчитывать положение пешеходов в моменты времени: 0, dt, 2*dt, 3*dt и т.д. Моделирование должно продолжаться до тех пор, пока пешеходы не встретятся друг с другом, т.е. пока х1 < х2. При достижении момента, когда х1 > х2, моделирование должно прекратиться.

Алгоритм моделирования движения с учетом принятых предположений и приращения времени, равного dt=0.1, приобретают следующий вид.

Алгоритм подпрограммы:

алг "модель движения"
НАЧ
очистка-экрана
хm=250; ym=190
xl=0; x2=s
t=0; dt=0.1
нц
точка(х1,уm - t)
точка(х2,уm - t)
t=t+dt
xl=v1 t
x2=v2 t
при х1> х2 выход
кц
КОН

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

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

x1(t)=v1*t
x2(t)=s - v2*t

Однако если допустить, что первый пешеход движется не равномерно, а с ускорением (замедлением) аl, то для отражения этого предположения в рассмотренной модели достаточно учесть ускорение в уравнении движения для первого пешехода:

x1(t)=v1*t + а1* t2/2
x2(t)=s - v2*t

Ниже приводится рисунок движения пешеходов в случае, когда первый пешеход движется с замедлением (а1 < 0):

Сцена2"Графикдвижения"

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

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

(В.А.Каймин "Основы компьютерной технологии" М1992 стр.145)

УПРАЖНЕНИЕ 3: Составьте математическую модель способа одевания по утрам, если в комплект надеваемых предметов входят брюки, рубашка, галстук, носки, ботинки и пиджак.

Решение. Обозначим надеваемые предметы числами 1, 2, 3, 4, 5, 6. Тогда способ одевания можно описать перестановкой этих чисел. Например, перестановка (4,2, 1,5,3,6) означает, что сначала надевают носки (4), затем рубашку (2), затем брюки (1) и т.д. Всего существует 720 способов одевания. Однако не все из них допустимы. Надевать ботинки раньше носков, конечно, можно, но вряд ли этот способ можно считать допустимым. Другими словами, необходимы некоторые ограничения. Не будем их описывать, примем только их наличие. Это уже математическая модель. Каждый из допустимых способов одевания можно охарактеризовать одним числом.

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

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

(Н.И.Коршунова, В.С.Плясунов "Математика в экономике" М 1996 стр.11)

Задачи: (п.6. Элементы линейного программирования)

6.1. Вычислить количество краски для покрытия пола в спортивном зале. Для выполнения этого задания измеряют длину а и ширину b и вычисляют площадь S=a*b. При покупке краски выясняют, какую площадь можно покрыть содержимым одной банки, и вычисляют необходимое количество банок N=a*b/S1

(Промоделировать ситуации с изменением площади пола).

6.2. о встрече двух граждан в течение одного часа:

На месте встречи один субъект появляется в случайный момент Х, (0<=X<=1), другой, независимо - в случайный момент Y(0<=Y<=1). Пришедший первым ждет 1/3 часа или до окончания назначенного часа, если Х>2/3 (или Y>2/3).

Ученик знаком с основами распространенного в школе программирования, составляет самостоятельно простейшую программу и на ее основе моделирует момент встречи.

Моделирование с использованием метода Монте-Карло.

6.3. На плоскости даны координаты N точек. Требуется составить программу, которая отвечает на вопрос: можно ли так занулировать точки, чтобы при соединении их отрезками в порядке возрастания индексов номеров (от i до i+1) получился выпуклый многоугольник. Если "ДА", то установить эту нумерацию.