Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Общая задача линейного программирования. Примеры. Графический метод - файл 1.docx


Общая задача линейного программирования. Примеры. Графический метод
скачать (99.2 kb.)

Доступные файлы (1):

1.docx100kb.13.12.2011 05:15скачать

содержание
Загрузка...

1.docx

Реклама MarketGid:
Загрузка...
Общая задача линейного программирования, примеры задач линейного программирования. Графический метод.

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

История

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

Джордж Данциг разработал симплекс-метод и считается «отцом линейного программирования» на западе.

Общей задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (8)

при условиях

(9)

(10)

(11)

где - заданные постоянные величины и .

Функция (8) называется целевой функцией (или линейной формой) задачи (8) – (11), а условия (9) – (11) – ограничениями данной задачи.

^ Стандартной (или симметричной} задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (9) и (11), где k = m и l = n.

Канонической (или основной) задачей линейного программирования называется задача, которая состоит в определении максимального значения функции (8) при выполнении условий (10) и (11), где k = 0 и l = п.

Совокупность чисел , удовлетворяющих ограничениям задачи (9) – (11), называется допустимым решением (или планом).

План , при котором целевая функция задачи (8) принимает свое максимальное (минимальное) значение, называется оптимальным.

Значение целевой функции (8) при плане Х будем обозначать через . Следовательно, X* – оптимальный план задачи, если для любого Х выполняется неравенство [соответственно ].

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

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



Ограничение-неравенство исходной задачи линейного программирования, имеющее вид “”, можно преобразовать в ограничение-равенство добавлением к его левой части дополнительной неотрицательной переменной, а ограничение-неравенство вида “” – в ограничение-равенство вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничение-неравенство

преобразуется в ограничение-равенство(12)

а ограничение-неравенство

– в ограничение-равенство(13)

В то же время каждое уравнение системы ограничений

можно записать в виде неравенств:

(14)

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

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

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

Пример 1.

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



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

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

^ Пример 2: Транспортная задача

Имеется некий однородный груз, который нужно перевести с n складов на m заводов. Для каждого склада i известно, сколько в нём находится груза ai, а для каждого завода известна его потребность bj в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния cij от i-го склада до j-го завода известны). Требуется составить наиболее дешёвый план перевозки.

Решающими переменными в данном случае являются xij — количества груза, перевезённого из i-го склада на j-й завод. Они удовлетворяют ограничениям:



Целевая функция имеет вид:,

которую надо минимизировать.

^ Графический метод

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

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

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

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

Этап 1.

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

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

  1. Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (рис. 3а)).

  2. 

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

Рис. 3

а) б)

Наконец, возможен случай, когда неравенства (1.31) противоречат друг другу, и допустимая область вообще пуста.

Рассмотрим теорию на конкретном примере:

Найти допустимую область задачи линейного программирования, определяемую ограничениями

(1.32)

Решение:

  1. Рассмотрим прямую . При , а при . Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Беря получим, что -0+0



Рассмотрим прямую. Будем увеличивать L. Что будет происходить с нашей прямой?

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

А теперь сведем всё вместе. Итак, надо решить задачу

Ограничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая пересекает допустимую область. Это пересечение дает какие-то значения переменных , которые являются планами.

Этап 2

Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 7). В конце концов эта прямая выйдет на границу допустимой области - как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение



Рис.7

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

^ Примеры задач, решаемых графическим методом.

Пример:

Решить задачу

(1.41)

Решение

Допустимую область мы уже строили - она изображена на рис. 5.

Повторим еще раз этот рисунок, оставив только допустимую область и нарисовав дополнительно прямые (см. рис. 8).

Рис. 8



Пусть, например, L=2. Тогда прямая проходит через точки (2,0) и (0,1) и изображена на рис. 8. Будем теперь увеличивать L. Тогда прямая начнёт двигаться параллельно самой себе в направлении, указанном стрелкой. Легко догадаться, что максимальное значение L получится тогда, когда прямая пройдет через вершину многоугольника, указанную на рисунке, и дальнейшее увеличение L приведет к тому, что прямая выйдет за пределы многоугольника и её пересечение с допустимой областью будет пустым.

Выделенная вершина лежит на пересечении прямых

и поэтому имеет координаты . Это и есть решение нашей задачи, т.е. есть оптимальный план задачи (1.41). При этом значение целевой функции , что и дает её максимальное значение.

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



Рис.9

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

Подводя итог этим примерам, можно сформулировать следующие положения:

1. допустимая область - это выпуклый многоугольник;

2. оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста);

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



Список используемой литературы:

  1. Акулич И.Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. -319 с.

  2. Ашманов С.А.Линейное программирование. - М.: Наука, 1981.

  3. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.1. Общие задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 176 с.

  4. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.2. Транспортные задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 240 с.

  5. Тынкевич М.А. Экономико-математические методы (исследование операций). Изд. 2, испр. и доп. - Кемерово, 2000. - 177 с.






Скачать файл (99.2 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru