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

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

Доступные файлы (1):
n1.docx842kb.30.03.2014 00:58скачать

n1.docx

  1   2   3   4   5

РЕКОМЕНДУЕМАЯ ЛИТЕАТУРА


  1. Костевич Л.С. Математическое программирование – Мн.: БГЭУ, 2003. – 203с. (Система дистанционного обучения)

  2. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию – Мн.: Выш. шк., 2001. – 448 с.

  3. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. – Мн.: Выш. шк., 2001. – 351 с.

  4. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. – Мн.: Выш. шк., 1994. – 286 с.

  5. Кузнецов А.В., Сакович В.А., Холод Н.И. и др. Под общей ред. А.В. Кузнецова. Сборник задач и упражнений по высшей математике: Математическое программирование – Мн.: Выш. шк., 1995. – 382 с.

  6. Бородина Т.А. Математическое программирование: Учебно-методическое. – Минск: БГЭУ, 2006. – 55 с.



ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ

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

Линейные модели являются одним из наиболее активно используемых классов математических моделей.

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

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

Линейность — это свойство математических выражений и функций. Выражение вида , где х и у — переменные величины, а, b и с — постоянные числа, называется линейным относительно переменных х и у.

В случае если переменных больше двух — х1, х2, …, хn, линейное выражение относительно этих переменных имеет вид

,

где — постоянные числа.

Заметим, что в линейное выражение все переменные входят в первой степени и никакие переменные не перемножаются.

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

Линейное программирование — это частный раздел оптимального программирования. В свою очередь оптимальное (математическое) программирование — раздел прикладной математики, изучающий задачи условной оптимизации. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании и управлении.

Математическая модель задачи – это отражение оригинала в виде функций, уравнений, неравенств, цифр и т.д. Модель задачи математического программирования включает: совокупность неизвестных величин х1, х2, …, хn ; целевую функцию (показатель эффективности, критерий оптимальности, функцию цели и др.); условия (или систему ограничений), налагаемых на неизвестные величины, совокупность которых образует область допустимых решений (Ω). Таким образом, мы можем записать математическую модель в следующем виде

F=f(х1, х2, …, хn)?max (min)

(i=) (1.1)



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

Рассмотрим основные примеры экономических задач, ставшие классическими:

Задача планирования производства (задача о наилучшем использовании имеющихся ресурсов)

Пусть некоторая производственная единица производит n видов продукции , затрачивая при этом m типов ресурсов . Известны следующие параметры:

– цена единицы продукции j-го вида (вектор цен);

– запас i-го ресурса (вектор ресурсов);

– количество i-го ресурса, необходимое для производства единицы продукции j-го вида (технологическая матрица);

– планируемый объем производства j-го вида продукции (план производства), при котором обеспечивается максимум прибыли при имеющихся ресурсах.

Составим экономико-математическую модель данной задачи.

Так как цена единицы продукции j-го вида, тогда стоимость единиц будет равна , а цена общего объема продукции:



Так как – расход i-го ресурса на производство единиц j-го вида продукции, то просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса на производство продукции, который не должен превышать :



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



Таким образом, математическая модель задачи о планировании производства примет вид:

(1.2)

(1.3)

(1.4)

Итак, (1.2) - (1.4) – модель поставленной задачи.

Транспортная задача.

Пусть имеется m производителей, у каждого из которых находится единиц однородного товара. Этот товар нужно доставить n потребителям, потребность в товаре которых соответственно равна единиц, чтобы общая величина транспортных издержек была минимальной.

Причем: =.

Известны следующие параметры:

– стоимость перевозки единицы товара от i-го производителя j-му потребителю.

– количество товара, перевозимое от i-го производителя j-му потребителю.

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

– матрица тарифов.

– матрица перевозок.

Математическая модель транспортной задачи примет вид:

(1.5)

(1.6)

(1.7)

(1.8)

(1.5) – целевая функция, описывающая транспортные затраты;

(1.6) – весь продукт из пунктов производства должен быть вывезен;

(1.7) – спрос потребителей должен быть удовлетворен;

(1.8) – условия неотрицательности переменных исключают обратные перевозки.

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

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

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

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

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

(1.9)

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



(1.10)

………………………………………



, (1.11)

где аij, bi, cj — заданные числа.

Условие (1.11) необязательно, но его всегда при необходимости можно добиться. Обозначение { говорит о том, что в конкретном ограничении возможен один из знаков: или .

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

найти максимум или минимум функции.

f ()=f1, х2, …, хn)= (1.12)

при ограничениях

(1.13)

(1.14)

Задача (1.12) - (1.14) — общая задача линейного программирования, иначе — математическая модель задачи линейного программирования, в основе построения (разработки) которой лежат принципы оптимальности и системности.

Вектор =(х1, х2, …,хn) (набор управляющих переменных) называется допустимым решением, или планом задачи, или вектором управления, или поведением оптимального программирования, если он удовлетворяет системе ограничений (1.13) и (1.14). Неотрицательное базисное допустимое решение задачи называется опорным планом. А тот план =(х1, х2, …,хn) (опорное решение), который доставляет максимум или минимум целевой функции f1, х2, …, хn) (1.12), называется оптимальным планом (оптимальным поведением, или просто решением) задачи линейного программирования.

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

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

Пример 1. Фирма выпускает два вида древесно-стружечных плит ― обычные и улучшенные. При этом производятся две основные операции ― прессование и отделка. Составить экономико-математическую модель задачи при помощи которой, требуется определить, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальный доход при ограничениях на ресурсы (материал, время, затраты) представленных в таблице 1, если за каждые 100 обычных плит фирма получаем доход, равный 80 ден.ед., за каждые 100 плит улучшенного вида ― 100 ден.ед.

Решение: Перейдем к построению математической модели поставленной задачи.

Введем следующие обозначения. Пусть х1 ― количество партий в 100 плит обычного вида, изготавливаемых в течение месяца, а х2 ― то же для плит улучшенного качества.
Таблица 1

Затраты

Партия из 100 плит

Имеющиеся ресурсы на месяц

Обычных

улучшенных

Материал (кг)

Время на прессование (ч)

Время на отделку (ч)

Средства (ден.ед.)

5

4

4

30

10

6

4

50

1000

900

600

6000

Тогда ожидаемый доход можно записать так:

f = 80х1 + 100х2 max. (1.15)

Для изготовления х1 партий в 100 плит обычного вида и х2 партий в 100 плит улучшенного вида требуется 5х1 + 10х2 килограммов дерева. Ясно, что полученное число не может превосходить количество материала, имеющегося в наличии, т.е. 1000 кг. Тем самым, ограничение на материал имеет вид: 5х1 + 10х2 1000.

Подобным же образом рассчитывается ограничения на время изготовления и затраты:

прессование: 4х1 +6х2 900,

отделка: 4х1 +4х2 600,

затраты: 30х1 +50х2 6000.

Наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объемы выпуска плит:

х1 0, х2 0.

Итак подведем итог: требуется найти такие значения х1 и х2, подчиненные условиям

5х1 + 10х2 1000,

4х1 +6х2 900,

4х1 +4х2 600, (1.16)

30х1 +50х2 6000,

х1 0,

х2 0,

для которых

f = 80х1 + 100х2 max.

Итак, соотношения (1.15) – (1.16) и есть математическая модель задачи поставленной в данном примере. Эта задача будет решена позже, после того как будет рассмотрен графический метод решения задач линейного программирования. ■
Формы записи задач линейного программирования

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

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

f = max (min) (2.1.)

при линейных ограничениях

(2.2.)

и при условиях

,

, , (2.3.)

где J1 J2 =( j=) и аij, bi, cj — постоянные числа.

Симметричной формой записи задачи линейного программирования называют задачу максимизации линейной функции (2.1.), при линейных ограничениях (2.2.), когда все ограничения имеют смысл неравенства вида «?» и все переменные неотрицательны, т.е.

f = max (2.4.)

(2.5.)

(2.6.)

Канонической формой записи задачи линейного программирования называют задачу максимизации линейной функции (2.1.), при линейных ограничениях (2.2.), когда все ограничения имеют смысл равенства и все переменные неотрицательны, т.е.

f = max (2.7.)

(2.8.)

(2.9.)

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

  1. При необходимости задачу максимизации можно заменить задачей минимизации и наоборот. Экстремум этих функций достигается в одной и той же точке, т.е. min f =  max ( -f ). После решения задачи max ( -f ) необходимо изменить на противоположный знак оптимума функции.

  2. Если на какую-либо переменную не наложено условие неотрицательности (например хк), то её можно заменить разностью двух новых неотрицательных переменных (хки xк’’), т.е. хкк’–xк’’.

  3. Любое ограничение неравенство задачи линейной оптимизации вида “”, можно преобразовать в равенство добавлением к его левой части дополнительной неотрицательной переменной, а неравенство, вида “” ― вычитанием из его левой части дополнительной неотрицательной переменной.

В экономических задачах дополнительные переменные всегда имеют определенный, практический смысл. Рассмотрим пример.

Пример 2. Привести модель задачи к канонической форме.

f = 8х1 +6х2 + 3х3 min

1 + 4х2 - 6х3 9

1 + 4х3 11

2 + 5х3 = 4

х1 0, х3 0.

Решение: Модель нашей задачи записана в общем виде. Так как на переменную х2 не наложено условие неотрицательности, то её мы заменим разностью двух неотрицательных переменных х2и х2 (x2 = х2- х2”) и подставим полученное выражение вместо переменной х2 в модель задачи. В результате мы получим модель:

f = 8х1 +6( х2- х2”) + 3х3 min

1 + 4( х2- х2”) - 6х3 9

1 + 4х3 11

2( х2- х2”)+ 5х3 = 4

х1 0, х3 0, х2 0, х2 0.

Ограничение неравенство 1 + 4( х2- х2”) - 6х3 9 преобразуем в равенство путем вычитания дополнительной переменной х4

1 + 4( х2- х2”) - 6х3 – х4 = 9.

Ограничение неравенство 1 + 4х3 11 преобразуем в равенство путем добавления к левой части дополнительной переменной х5

1 + 4х35 = 11.

Следует заметить, что в каждое ограничение необходимо вводить свою дополнительную переменную. И, наконец, преобразуем исходную задачу минимизации к задаче максимизации, применив соображения из пункта 1 z = - f = -8х1 -6( х2- х2”) - 3х3 max.

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

z = -8х1 -6 х2’ + 6 х2” - 3х3 max

1 + 4 х2- 2” - 6х3 – х4 = 9

1 + 4х3 + х5 = 11

2 х2- 2”+ 5х3 = 4

х1 0, х3 0, х2 0, х2 0, х4 0, х5 0.
  1   2   3   4   5
Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации