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

Введение

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

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

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

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

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

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

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

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

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

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

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

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

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

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

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

 

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

Большинство задач, решаемых методами исследования операций, может быть сформулировано так:максимизировать F(x₁, x₂,., x_n) при ограничениях:

(1.1.1)

 

где f(x₁, x₂,., x_n) - целевая функция, или критерий эффективности (например, прибыль от производства каких-либо видов продукции, стоимость перевозок и т.п.);

X={x₁,.,x_n} - варьируемые параметры; g₁(x),.,g_m(x) - функции, которые задают ограничения на имеющиеся ресурсы.

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

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

Задача 1.

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

Решение.

Приводим задачу к каноническому виду. Для этого в левую часть правого ограничения вводим дополнительные переменные Х₄, Х₅ и Х₆ с коэффициентом +1. В целевую функцию переменные Х₄, Х₅ и Х₆ входят с коэффициентом 0.

Получим:

 

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

Получаем опорное решение.

С единичным базисом Б_1.

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

:

С_б = (с₁, с₂,..., с_m) — вектор коэффициентов целевой функции при базисных переменных

X_k = (x_1k, x_2k,..., x_mk) — вектор разложения соответствующего вектора А_k по базису опорного решения

С_k — коэффициент целевой функции при переменной х_k.

 

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

Таблица 1

			47	39	36	0	0	0
Б	Сб	А0	А1	А2	А3	А4	А5	А6	D1
A4	0	816	336	256	316	1	0	0	2.4
A5	0	716	186	146	126	0	1	0	4
A6	0	916	396	456	466	0	0	1	2.3
	0	-47	-39	-36	0	0	0

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

В последней строке таблицы с оценками Δk в столбце "А₀" записываются значения целевой функции на опорном решении Z(X₁).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -47, Δ2= -39, Δ3= -36 для векторов А_1, А₂ и А₃ отрицательные.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение функции находится по формуле:

Вычислим значение D по формуле:

Полученные значения записываем в таблицу.

Находим приращение целевой функции при введении в базис первого вектора

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А₁ вместо первого вектора базиса А₆, так как минимум параметра D₀₁ достигается в третьей строке.

Производим преобразование Жордана с элементом Х₃₁ =396, получаем второе опорное решение Х2 = (2.3;0;0;43.2;288.2;0) с базисом Б2 = (А₄, А₅, А₁).

 

Таблица 2

			47	39	36	0	0	0
Б	Сб	А0	А1	А2	А3	А4	А5	А6
A4	0	43.2	0	-130.4	-80.48	1	0	-0.84
A5	0	288.2	0	-67.9	-93.48	0	1	-0.465
A1	47	2.3	1	1.15	1.18	0	0	0.0025
	108.1	0	15.05	19.46	0	0	0.1175

 

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ₂ = 15.05, Δ₃ = 19.46, Δ₆ = 0.1175.

Ответ: max f(X)=108.1 при Х= (2.3;0;0;43.2;288.2;0)

Формализация

1. Шаг 1. Задаются начальные границы отрезка и точность .

2. Шаг 2. Рассчитывают начальные точки деления:

(2.1.4)

(2.1.5)

и значения в них целевой функции:

(2.1.6)

(2.1.7)

Если (для поиска max изменить неравенство на ), то

Иначе .

3. Шаг 3.

Если , то и останавливаемся.

Иначе возврат к шагу 2.

Шаг 3.

Если , то и останавливаемся.

Иначе возврат к шагу 2

Задача 2.

Пример решения задач нелинейного программирования методом Фибоначчи.

Найти min функции f(x)=18 – 20х – 32 на отрезке [ 0; 40 ] за 8 шагов.

Решение:

F_n+1 = F₁₀ = 55;

F_n+1 = F₉ = 34;

F_n = F₈ = 21;

F_n-1 = F₇ = 13;

F_n-2 = F₆ = 8;

F_n-3 = F₅ = 5;

F_n-4 = F₄ = 3;

F_n-5 = F₃ = 2;

F_n-6 = F₂ = 1;

F_n-7 = F₁ = 1;

Итерация 1.

Х₁¹ = а + ∙(b - a) = a + ∙(b – a) = ∙ 40 = 15,2

X₂¹ = a+ ∙(b – a) = a + ∙(b – a) = ∙ 40 = 24,72

f (x₁¹)=18x² - 20x - 32= 18 ∙(15,2)² – 20∙ (15,2) - 32 = 4158,72 - 304 - 32 = 3822,72

f(x₂¹)= 18x² - 20x – 32=18∙(24,72)² – 20∙(24,72) - 32 = 10998 - 494,4 - 32=10471,6

f(x₁¹) < f(x₂¹), следовательно отрезок ограничен [ 0; 24,72 ].

Итерация 2.

x₁² = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 24,72 = 9,4

x₂² = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 24,72 = 15,4

f(x₁²) = 18x² - 20x – 32 = 18 ∙ (9,4)² – 20 ∙ (9,4) – 32 = 1590,48 – 188 - 32 = 1370,48

f(x₂²)= 18x² - 20x – 32 = 18 ∙ (15,3)² – 20 ∙ (15,3) – 32 = 4213,62 – 306 – 32 = 3875,62

f(x₁² ) < f(x₂² ), следовательно отрезок ограничен [ 0; 15,3 ].

Итерация 3.

x₁³= a + ∙ (b – a) = a + ∙ (b – a) = ∙ 15,3 = 5,8

x₂³= a + ∙ (b – a) = a + ∙ (b – a) = ∙ 15,3 = 9,5

f(x₁³) = 18x² - 20x – 32 = 18 ∙ (5,8)² – 20 ∙ (5,8) – 32 = 605,52 – 116 – 32 = 457,52

f(x₂³) = 18x² - 20x – 32 = 18 ∙ (9,5)² – 20 ∙ (9,5) – 32 = 1624,5 – 190 – 32 = 1402,5

f(x₁³) < f(x₂³), следовательно отрезок ограничен [ 0; 9,5 ].

Итерация 4.

x₁⁴ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 9,5 = 3,61

x₂⁴ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 9,5 = 5,8

f(x₁⁴) = 18x² - 20x – 32 = 18 ∙ (3,61)² – 20 ∙ (3,61) – 32 = 234 – 72,2 – 32 = 129,8

f(x₂⁴) = 18x² - 20x – 32 = 18 ∙ (5,8)² – 20 ∙ (5,8) – 32 = 605,52 – 116 – 32 = 457,52

f(x₁⁴) < f(x₂⁴), следовательно отрезок ограничен [ 0; 5,8 ].

Итерация 5.

x₁⁵ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 5,8 = 2,18

x₂⁵ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 5,8 = 3,63

f(x₁⁵) = 18x² - 20x – 32 = 18 ∙ (2,18)² – 20 ∙ (2,18) – 32 = 85,5 – 43,6 – 32 = 9,9

f(x₂⁵) = 18x² - 20x – 32 = 18 ∙ (3,63)² – 20 ∙ (3,63) – 32 = 237,06 – 72,6 – 32 = 132,46

f(x₁⁵) < f(x₂⁵), следовательно отрезок ограничен [ 0; 3,63 ].

 

Итерация 6.

x₁⁶ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 3,63 = 1,5

x₂⁶ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 3,63 = 2,2

f(x₁⁶) = 18x² - 20x – 32 = 18 ∙ (1,5)² – 20 ∙ (1,5) – 32 = 40,5 – 30 – 32 = -21,5

f(x₂⁶) = 18x² - 20x – 32 = 18 ∙ (2,2)² – 20 ∙ (2,2) – 32 = 87,12 – 44 – 32 = 11,12

f(x₁⁶) < f(x₂⁶), следовательно отрезок ограничен [ 0; 2,2 ].

Итерация 7.

x₁⁷ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 2,2 = 0,726

x₂⁷ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 2,2 = 1,47

f(x₁⁷) = 18x² - 20x – 32 = 18 ∙ (0,726)² – 20 ∙ (0,726) – 32 = 9,486 – 14,52 – 32 = -37,034

f(x₂⁷) = 18x² - 20x – 32 = 18 ∙ (1,47)² – 20 ∙ (1,47) – 32 = 38,88 – 29,4 – 32 = -22,52

f(x₁⁷) < f(x₂⁷), следовательно отрезок ограничен [ 0; 1,47 ].

Итерация 8.

x₁⁸ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 1,47 = 0,735

X₂⁸ = a + ∙ (b – a) = a + ∙ (b – a) = ∙ 1,47 = 0,735

f(x₁⁸) = 18x² - 20x – 32 = 18 ∙ (0,735)² – 20 ∙ (0,735) – 32 = 9,72 – 14,7 – 32 = -36,98

f(x₂⁸) = 18x² - 20x – 32 = 18 ∙ (0,735)² – 20 ∙ (0,735) – 32 = 9,72 – 14,7 – 32 = -36,98

f(x₁⁸) = f(x₂⁸) = -36,98 – точка min функции.

Ответ: min f(x)= -36,98

Заключение

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

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

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

 

 

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

1. Замков О.О., Толстопятенко А.В., Черешных Ю.Н. Математические методы в экономике: Учебник. - М.: МГУ им. М.В.Ломоносова, Издательство «ДИС», 1997.

2. Конспект лекций по предмету «Основы математического моделирования социально-экономических процессов».

3. Минюк С.А. Математические методы и модели в экономике: Учеб. пособие / Минюк С.А., Ровба Е.А., Кузьмич К.К. - Мн.: ТетраСистемс, 2002.

4. Смородинский С.С., Батин Н. В. Оптимизация решений на основе методов и моделей математического программирования. Мн.: БГУИР, 2003.

5. Экономико-математические методы и модели/ Под. ред. А. В. Кузнецова. Мн.: БГЭУ.1999.

 

Введение

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

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

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

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

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

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

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

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

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

Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

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

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

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

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

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