Понятия линейного программирования

Задание

1. Решить задачу линейного программирования:
• графическим методом
• симплекс- методом
• методом симплекс-таблица

2. Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально - денежных ресурсов в количестве b₁, b₂, b₃ единиц. При этом для продажи 1 группы товаров на 1тыс.руб. товарооборота расходуется ресурса первого вида в количестве a₁₁ единиц, ресурса второго вида в количестве a₂₁ единиц, ресурса третьего вида в количестве a₃₁ единиц. Для продажи 2 и 3 групп товаров на 1 тыс.руб. товарооборота расходуется соответственно ресурса первого вида в количестве a₁₂, a₁₃ единиц, ресурса второго вида в количестве a₂₂, a₂₃ единиц, ресурса третьего вида в количестве a₃₂, a₃₃ единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно с₁, с₂, с₃ (тыс. руб.). Определить плановый объём и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

 

 

 

 

a₁₁ =9      а₁₂ = 9     a₁₃= 3

a₂₁ = 3     a₂₂ = 6     a₂₃ = 9

a₃₁ = 7     a₃₂ = 4     a₃₃ = 12

b₁ = 801  b₂ = 453  b₃ = 280

с₁ = 3       с₂ = 4      с₃ = 3

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

 

Содержание

1. Введение………………………………………………………….…………4

Теоретическая часть…………………………………………………………6

1. Понятия линейного программирования……………………………6
2. Общая задача линейного программирования……………..….……6
3. Симплекс-метод……………………………………………..………7
4. Алгоритм Симплекс-метода: ………………………………………8
5. Метод искусственного базиса: ………………………………….…8
6. Двойственный симплекс-метод………………………………….…9

2. Практическая часть………………………………………………………12

1. Решение задачи линейного программирования…………………12
• графический метод……………………………………………………….12
• метод симплекс-таблица…………………………………………………26
2. Решение задачи на определение планового объёма и структуры товарооборота……………………………………………………………………36
3. Решение двойственной задачи линейного программирования…39

• составление двойственной задачи линейного программирования……39

• установка сопряженных пар переменных прямой и двойственной задач……………………………………………………………………………...39
• решение двойственной задачи…………………………………..….……39

3. Заключение………………………………………………………..………44

4. Использованная литература……………………………………...………45

 

1. Введение.

Термин линейное программирование появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском  Союзе исследования в этой области  начались ранее. В конце 30-х годов  целый ряд существенных результатов  по линейному программированию был  установлен Л.В. Канторовичем.

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

Задачи линейного программирования являются самыми простыми и лучше  изученными задачами. Для них характерно: показатель эффективности (целевая  функция) выражается линейной зависимостью; ограничения на решения – линейные равенства или неравенства.

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

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

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

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

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

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

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

 

ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

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

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

Линейное программирование - это  наука о методах, исследование и  отыскивания min (max) линейной функции, на переменные которой наложены линейные ограничения.

Линейность - это свойство математических выражений и функций  

выражение ax+by является линейным относительно переменных x и y.

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

(1.1) при условиях

, где  (1.2)

 _{(i=k+1, m)}   (1.3)

    (1.4)

     Функция (1) называется  целевой функцией задачи (1.2)-(1.4) условия(1.2)-(1.4) ограничениями данной задачи.

     Стандартной задачей  линейного программирования называется, задача которая состоит в определении максимума значения  функции (1) при выполнении условий (1.2)-(1.4), где k=m и t=n.

     Канонической задачей  линейного программирования называется  задача, которая состоит в определении  максимума значения функции (1) при выполнении условий (1.3)-(1.4), где k=0 и t=n.

     Совокупность чисел  x=x1,x2,…xn, удовлетворяющих ограничениям задачи (1.2)-(1.4) называется планом.

Общая задача линейного  программирования

Постановка задачи: Найти наибольшее (наименьшее) значение показателей  эффективности целевой функции

Z=c₁x₁ + c₂x₂ + … + c_nx_n -> max (min)

При системе линейных ограничений:

 

n – количество переменных

m – количество ограничений

Необходимо найти значение x₁, x₂, …, x_n, неотрицательные, соответствующие системе ограничений (2), в которой функция Z принимает max (min) значение.

Этапы решения задачи ЛП графическим  методом:

1.Систему ограничений представить  в виде системы равенств;

2.Получить многоугольник допустимых  решений;

3.Начерить прямую целевой функции;

4.Построить перпендикуляр к  прямой целевой функции, которая  проходит через т. (0;0)

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

2.Симплекс – метод

Универсальным методом решения  систем линейных уравнений является симплексный метод.

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

а)Алгоритм Симплекс-метода:

1.Заменяя систему неравенств на систему уравнений, добавляем дополнительные переменные;

2.Выражаем дополнительные переменные  через остальные;

3.Находим первое опорное решение  при независимых переменных;

4.Если при решении задачи  в записи целевой функции есть  отрицательные (положительные) коэффициенты, то:

а).Рассматриваем элементы из записи целевой функции с наибольшим по модулю ‘’-‘’ коэффициентом (при решении на min рассматривается наибольший ‘’+’’ коэффициент).

Переменные с наибольшим коэффициентом  выражаем через остальные;

б).Находим min соответствие свободных элементов к коэффициенту выбранной переменной;

в).Подставляем полученное выражение в другие уравнения и целевую функцию;

г).Находим опорное решение при всех независимых переменных, равных нулю;

5.Смотрим пункт 4).

 

6.Получаем оптимальный план.

  б)Метод искусственного базиса:

Если в системе ограничений  в неравенствах содержится знак = или >=0, то для построения первого опорного плана вводят искусственные базисные переменные.

 

Z=x₁ + 1,1x₂ + 7,5x₃ -> min

Решение:

 

Для получения решения в каждое уравнение добавляют неотрицательные  искусственные переменные (0)

 

Для искусственных переменных коэффициент  целевой функции M.

Если решается задача на min M – очень большое ‘’+’’ число, если на max – очень маленькое ‘’-‘’

Продолжить решение системы  по алгоритму симплекс– метода.

 в) Двойственный симплекс-метод.

Рассмотрим алгоритм двойственного  симплекс-метода.

Запишем условия задачи:

 

Введём новую функцию 

1. Приведём условия задачи  к каноническому виду:

 

 

 

2. Запишем симплекс таблицу, соответствующую задаче.

№	Б	u0	u1	u2	v1	v2	v3	v4
1	u1	c1	1	0	a11	a21	a31	a41
2	u2	c2	0	1	a12	a22	a32	a42
3	-z		0	0	-b1	-b2	-b3	-b4