Hi-Tech  ->  Программы  | Автор: | Добавлено: 2015-03-23

Геометрия задач линейного программирования

Великий русский математик Пафнутий Львович Чебышев в работе “Черчение географических карт” писал, что особенную важность имеют те методы науки, которые позволяют решать задачу, общую для всей практической деятельности человека: как располагать своими средствами для достижения по возможности большей выгоды. С такими задачами приходиться иметь дело представителям самых разных специальностей – инженеры-технологи стремятся так организовать производство, чтобы на имеющемся станочном парке сделать как можно больше продукции, конструкторы ломают голову, стремясь сделать наилегчайший прибор на космическом корабле, экономисты стараются так спланировать прикрепление заводов к источникам сырья, чтобы транспортные расходы оказались наименьшими.

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

Пчелам помогает решать свои задачи инстинкт. Человек же отличается от них тем, что ему на помощь приходит разум. Маркс говорил: «Но и самый плохой архитектор от наилучшей пчелы с самого начала отличается тем, что, прежде чем строить ячейку из воска, он уже построил ее в своей голове». Математикам удалось разработать методы решения задач на наибольшие и наименьшие значения, или, как их еще называют, задач на оптимизацию (от латинского «оптимум» - наилучший).

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

Линейное программирование является частью раздела математики, называемого «Методы оптимизации».

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

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

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

Этот вопрос и рассмотрен в предложенной работе.

I. Историческая справка

Леонид Витальевич Канторович

(1912 - 1986)

Один из основоположников экономико-математического направления. В

1930 году окончил математическое отделение Ленинградского государственного университета. В 1935 г. ему присвоена ученая степень доктора физико-математических наук.

В 1958 году Л. В. Канторовича избирают членом-корреспондентом, а в 1964 году - действительным членом АН СССР. За разработку метода линейного программирования и экономических моделей он был удостоен в 1965 году Ленинской премии, а в 1975 г. ему была присуждена Нобелевская премия по экономике за вклад в разработку теории оптимального использования ресурсов.

В 1939 году Л. В. Канторович опубликовал работу "Математические методы организации и планирования производства", в которой сформулировал принципиально новый класс экстремальных задач с ограничениями и разработал эффективный метод их решения. Так был открыт новый раздел прикладной математики, получивший впоследствии название "линейное программирование".

2. 1. Примеры задач линейного программирования

Рассмотрим несколько задач линейного программирования.

Задача 1.

Цех выпускает трансформаторы двух видов. На один трансформатор первого вида расходуется 5 кг трансформаторного железа и 3 кг проволоки, а на один трансформатор второго вида 3 кг железа и 2 кг проволоки. От реализации одного трансформатора первого вида цех получает прибыль в 1,2 у. е. , а от реализации одного трансформатора второго вида 1 у. е. Сколько трансформаторов каждого вида должен выпустить цех, чтобы получить наибольшую сумму прибыли, если цех располагает 480 кг железа и 300 кг проволоки?

Решение:

Пусть x трансформаторов – выпущено первого вида

Тогда y трансформаторов – выпущено второго вида.

Для их изготовления потребуется 5x+3y кг железа и 3x+2y проволоки.

В наличии имеется всего 480 кг железа и 300 кг проволоки, поэтому должны выполняться неравенства:

Задача 2.

Для откорма животных на ферме в их ежедневный рацион необходимо включать не менее 33 единиц питательного вещества А, 23 единицы питательного вещества В и 12 единиц питательного вещества С. Для откормки животных используется три вида кормов. Данные о содержании питательных веществ и стоимости одной весовой единицы каждого из кормов помещены в таблице.

А В С Стоимость одной единицы

В одной единице корма 1 4 ед 3 ед 1 ед 20 у. е.

В одной единице корма 2 3 ед 2 ед 1 ед 20 у. е

В одной единицы корма 3 2 ед 1 ед 2 ед 10 у. е

Пусть в рационе: x– единиц корма 1 y – единиц корма 2 z– единиц корма 3

Задача 3.

Из листового проката определенной формы необходимо вырезать некоторое количество заготовок двух типов А и В для производства 90 штук изделий. Для одного изделия требуется 2 заготовки типа А и 10 заготовок типа В. Возможны 4 варианта раскроя одного листа проката. Количества заготовок А и В, вырезаемых из одного при каждом варианте раскроя указаны в таблице

Варианты раскроя Заготовки Отходы от раскроя

1 4 шт 0 шт 12 ед

2 3 шт 3 шт 5 ед

3 1 шт 9 шт 3 ед

4 0 шт 12 шт 0 ед

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

На 90 штук изделий потребуется 180 заготовок типа А и 900 заготовок типа В.

х - листы, раскроенные по первому варианту у - листы, раскроенные по второму варианту d - листы, раскроенные по третьему варианту к - листы, раскроенные по четвертому варианту

Мы рассмотрели три вида задач и заметили в их постановке нечто общее. Каждая задача на нахождение оптимального (наиболее выгодного) варианта: наиболее доходной производственной программы в первой задаче, наиболее экономного рациона – во второй, наиболее рационального раскроя – в третьей.

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

Такими задачами занимается линейное программирование.

2. 2. Основные определения

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

Общий вид задач линейного программирования формулируется следующим образом: среди неизвестных x1 , x2 , , xn , удовлетворяющих системе a11х1 + а12х2 ++ а1nxn ≥ b1, a21x1 + a22x2 +. + a2nxn ≥ b2,

am1x1 + am2x2 +. + amnxn ≥ bm, x1 ≥ 0, x2 ≥ 0,, xn ≥ 0, определить такие, при которых функция

S = c1x1 + c2x2 +. +cnxn достигает своего наименьшего или наибольшего значения.

Определение 2. Целевая функция – функция, для которой находится ее наибольшее (наименьшее) значение.

Определение 3. Системами ограничения - системы неравенств или уравнений, которым должны удовлетворять переменные целевой функции.

Определение 4. Любое решение системы ограничений называется допустимым решением задачи линейного программирования.

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

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

Любую задачу максимизации можно свести к задаче минимизации и наоборот.

2. 3. Графическое решение задач линейного программирования.

Геометрия задачи линейного программирования

Так как система ограничений есть система линейных неравенств, то множество ее решений есть выпуклый многоугольник М, лежащий в первой четверти координатной плоскости.

С учетом этого задачу можно сформулировать иначе: среди всех точек выпуклого многоугольника М найти такую, координаты которой минимизируют (максимизируют) линейную функцию

S = c1x1 + c2x2

Если зафиксировать какое – нибудь значение функции S = d, то получим линейное уравнение с двумя неизвестными c1x1 + c2x2 = d, график которого есть прямая плоскости. При изменении d от - ∞ до + ∞ прямая c1x1 + c2x2 = d, смещаясь параллельно самой себе, «зачертит» всю плоскость.

Пусть М – многоугольник решений системы ограничений При изменении d от - ∞ до + ∞ прямая c1x1 + c2x2 = d при некотором значении d = d1 достигает многоугольника М и имеет с ним общую точку А (точка «входа»), а затем, пройдя весь многоугольник М, при некотором значении d = d2 будет иметь с ним последнюю общую точку В (точка «выхода»).

Наименьшего значения целевая функция S = c1x1 + c2x2 достигает в точке «входа» А и наибольшего значения в точке «выхода» В.

Возможен случай, когда при перемещении прямой c1x1 + c2x2 = d «вход» («выход») прямой в многоугольник решений М произойдет по стороне этого многоугольника Это случится, если в многоугольнике М есть стороны, параллельные прямой c1x1 + c2x2 = d. В этом случае точек «входа» («выхода») бесчисленное множество, минимальное (максимальное) значение целевая функция принимает во всех точках этой стороны многоугольника.

Так, координаты всех точек отрезка AD минимизируют значение функции S = c1x1 + c2x2, а координаты всех точек отрезка AB (рис. 4) максимизируют значение целевой функции.

В случае открытых областей решений прямая c1x1 + c2x2 = d при изменении d от - ∞ до + ∞ не имеет точки «выхода» из области решений (рис. 5). Тогда максимальное значение функцией не достигается.

Учитывая, что оптимальное значение целевая функция принимает в точках «входа» и «выхода», то есть в вершинах области решений, существует следующий план графического решения задачи линейного программирования:

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

Пример решения задачи

В качестве примера решим задачу 1(см. выше). Решение этой задачи заключается в нахождении наибольшего значения функции S = 1,2x + y при условии, что ее переменные х и y подчинены системе:

В плоскости построим многоугольник ABCO системы ограничений. Фиксируем произвольное значение функции S, например S = -30, и построим прямую 1,2x + y = -30. При параллельном перемещении прямой 1,2x + y = -30 в направлении, указанном стрелкой (увеличивая значение функции S), получим, что точка «выхода» будет вершина С многоугольника решений. Определим координаты точки С. Точка С есть результат пересечения прямой (b), соответствующей неравенству (b), и оси ординат ОY, следовательно, ее координаты определяются из системы уравнений:

3x+2y = 300, х = 0.

Решая эту систему, получим: х = 0, y = 150.

Теперь вычислим значение целевой функции S = 1,2x + y при этих значениях неизвестных: S = 1,2*0 + 150 = 150.

Итак, наибольшее значение функции S = 1,2x + y равно 150, и оно достигается при х = 0, y = 150.

Пример. Найти наименьшее и наибольшее значение функции при условии, что ее переменные удовлетворяют системе неравенств: x + y ≥ 1,(a)

-x + y ≤ 1,(b) x ≥ 0, y ≥ 0.

Построим область решений системы ограничений, получим фигуру CBAD (рис. 7). Зафиксировав значение функции S = -2, построим прямую 2х + 2y = -2. Перемещая ее параллельно в направлении, указанном стрелкой (увеличивая значение S), убеждаемся, что точками «входа» будут две вершины А и В, так как прямая 2х + 2y = -2 параллельна прямой АВ, следовательно, функция S = 2х + 2y достигает наименьшего значения во всех точках отрезка АВ, и оно равно 2. Наибольшего значения функция не достигает, так как область решений открытая.

Алгоритм решения задач линейного программирования:

• Построить математическую модель задачи

• На координатной плоскости построить множество допустимых решений

• Построить линии уровня для целевой функции

• Определить, какие из вершин многоугольника допустимых решений являются точками «входа» и точками «выхода»

• Найти координаты точек «входа» ( «выхода»)

• Вычислить оптимальное значение функции.

• Провести интерпретацию полученного решения.

• Уточнить математическую модель.

2. 4. Примеры решения задач линейного программирования геометрическим методом.

Задача 1:

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

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

Дневное питание этими новинками должно давать не более 14 единиц жира (чтобы похудеть), но и не менее 300 калорий (чтобы не сойти с дистанции раньше). На банке с продуктом Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на банке с продуктом Q – 4 единицы жира и 200 калорий соответственно. При этом цена 1 кг продукта Р равна 150 рублям, а 1 кг продукта Q – 250 рублям.

Так как дама просто приятная в это время была весьма стеснена в средствах, то ее интересовал ответ на следующий вопрос: «В какой пропорции нужно брать эти удивительные продукты Р и Q для того, чтобы выдержать условия диеты и истратить как можно меньше денег?»

Решение:

Надо купить х кг продукта Р и y кг продукта Q.

Тогда 15х – количество жира в продукте Р и 4y в продукте Q.

150 х калорий в продукте Р и 200y в продукте Q.

Строим математическую модель задачи:

15х + 4y ≤ 14- ограничение по жирам

150x + 200y ≥ 300- ограничение по калориям x ≥ 0 у ≥ 0

S = 150x + 250y - целевая функция

S → min

Построим графики:

15х + 4y = 14150x + 200y = 300

y 0 1. 5

х 0 14/15

y 3. 5 0

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

А – точка «входа»

Найдем координаты точки «входа»(А):

15х + 4y = 14

150x + 200y = 300

15x + 4y = 14

3x + 4y = 6

Решим систему уравнений методом Крамера:

∆ = 15*4-4*3 = 48x = 2/3

∆x = 14*4-4*6 = 32y = 1

∆y = 15*6-14*3 = 48

А (2/3; 1)

Вычислим оптимальное значение функции:

S = 150x + 250y

S(A) = 150*2/3 + 250*1 = 350

Мы советуем даме купить 2/3 кг продукта Р и 1 кг продукта Q, при этом она истратит всего лишь 350 рублей.

Задача 2:

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

Тип вагонов Багажные Почтовые Жесткие Купейные Мягкие Вид поезда

Число вагонов в поезде 1 0 5 6 3 курьерский

1 1 8 4 1 скорый

Вместимость вагонов - - 58 40 32

Наличный парк 12 8 81 70 27

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

Решение:

Пусть х – курьерские поезда, тогда y – cкорые поезда.

Строим математическую модель задачи: x + y ≤ 12ограничение по количеству поездов y ≤ 8

5x + 8y ≤ 81

6x + 4y ≤ 70

3x + y ≤ 27 x ≥ 0, y ≥ 0

S = 626x + 656y

Построим графики: x + y = 125x + 8y = 81

x 0 16,2

y 10,125 0

6x + 4y = 703x + y = 27

x 0 11,66

y 17,5 0

Определим точку «выхода». Для этого построим линии уровня данной целевой функции:

А – точка «выхода»

Найдем координаты точки (А): x + y = 12

5x + 8y = 81

Решим систему уравнений методом Крамера:

∆x = 15x = 5

∆y = 21y = 7

Вычислим оптимальное значение функции:

S = 626x + 656y

S(A) = 626*5 + 656*7 = 7722

Требуется ежедневно отправлять 5 курьерских и 7 скорых поездов, чтобы число пассажиров достигло максимума.

2. 5. Решение задач в случае трех переменных

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

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

III. Выводы

. Изучая данную тему, мы

- ознакомились с историей возникновения одного из разделов математики - линейного программирования;

- узнали об основоположниках экономико-математического направления;

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

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

- разработали программу решения задач линейного программирования для двух переменных;

- ознакомились с теорией решения задач линейного программирования с тремя переменными.

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

Комментарии


Войти или Зарегистрироваться (чтобы оставлять отзывы)