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

Содержание

 

	Введение	3
1	Линейное программирование	4
1.1	Задачи линейного программирования	4
1.2	Решение задач линейного  программирования симплекс – методом	5
1.3	Решение задач линейного  программирования графическим методом	10
2	Реализация методов  линейного программирования на практическом применении	11
2.1	Пример решения задачи линейного программирования симплекс-методом	11
2.2	Пример решения задачи линейного программирования графическим способом	14
2.3	Пример решения задачи линейного программирования с помощью MS EXCEL	16
3	Решение задач линейного  программирования	20
3.1	Решение задачи линейного  программирования графическим методом	20
3.2	Решение задачи линейного  программирования симплекс-методом	27
3.3	Решение транспортной задачи	31
	Заключение	36
	Список использованной литературы	37

 

 

 

 

 

 

 

Введение

 

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

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

Задачи:

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

2) на конкретных примерах  экономического содержания показать  все этапы нахождения оптимального  решения и его постоптимального  анализа.

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

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

1 Линейное программирование

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

 

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

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

Экономико-математическая модель – это математическое описание экономического процесса или объекта. Реализуя их обработку на ЭВМ, мы получаем выигрыш во времени и средствах, так как проведение опытов, как правило, более трудоёмкий и дорогостоящий процесс, кроме того, не всегда возможный. Не буду здесь вдаваться в теорию моделирования, скажу лишь, что именно реализация исследования экономических процессов с помощью ЭВМ для нас и представляет интерес, а проявляется это в машинном решении задач линейного программирования, которые в свою очередь и являются экономико-математическими моделями. [2]

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

• Задачи об использовании ресурсов, сырья, планирования производства
• Задачи составления рациона
• Задачи об использовании мощностей, загрузке оборудования
• Задачи о раскрое материалов
• Транспортные задачи

 

 

 

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

 

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

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

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

a₁₁x₁+a₁₂x₂+ … +a_1nx_n {≤, ≥, =}

a₂₁x₁+a₂₂x₂+ … +a_2nx_n {≤, ≥, =}                                                                      (1)

………

a_m1x₁+a_m2x₂+ … +a_mnx_n {≤, ≥, =} 

x₁ ≥ 0, x₂ ≥ 0, …, x_n ≥ 0                                                                                           (2)

F = c₁x₁ + c₂x₂ + … + c_nx_n → max                                                                    (3)

 

Коэффициенты ai, j, bi, cj, j = 1, 2,…, n, i =1, 2,…, m – любые действительные числа (возможно 0).

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

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

В канонической форме  задача является задачей на максимум (минимум) некоторой линейной функции F, ее система ограничений состоит  только из равенств (уравнений). При  этом переменные задачи х1, х2,…, хn являются неотрицательными:

 

a₁₁x₁+a₁₂x₂+ … +a_1nx_n =b₁

a₂₁x₁+a₂₂x₂+ … +a_2nx_n =b₂

………                                                                                             (4)

a_m1x₁+a_m2x₂+ … +a_mnx_n =b_n

x₁ ≥ 0, x₂ ≥ 0, …, x_n ≥ 0                                                                                  (5)

F = c₁x₁ + c₂x₂ + … + c_nx_n → max(min)                                                            (6)

 

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

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» – со знаком «–»

a₁₁x₁+a₁₂x₂+ … +a_1nx_n                                                                                                                                                   (7)

Вводим переменную x_n+1=b₁ – a₁₁x₁-a₁₂x₂+ … +a_1nx_n

Тогда неравенство  запишется в виде:

a₁₁x₁+a₁₂x₂+ … +a_1nx_n +x_n

В каждое из неравенств вводится своя «уравнивающая» переменная, после чего система ограничений становится системой уравнений.

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

 

xk = xk- xk ≥ 0, xl

l – свободный индекс

 

3. Если в ограничениях  правая часть отрицательна, то  следует умножить это ограничение  на (-1)

4. Наконец, если исходная  задача была задачей на минимум,  то введением новой целевой  функции F1 = – F мы преобразуем  нашу задачу на минимум функции  F в задачу на максимум функции  F1.

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

В стандартной форме  задача линейного программирования является задачей на максимум (минимум) линейной целевой функции. Система  ограничений ее состоит из одних  линейных неравенств типа «<=» или  «>=». Все переменные задачи неотрицательны.[2]

a₁₁x₁+a₁₂x₂+ … +a_1nx_n ≤ b₁

a₂₁x₁+a₂₂x₂+ … +a_2nx_n ≤ b₂

………                                                                                                                     (8)

a_m1x₁+a_m2x₂+ … +a_mnx_n ≤ b_n

F = c₁x₁ + c₂x₂ + … + c_nx_n → max

x₁ ≥ 0, x₂ ≥ 0, …, x_n ≥ 0

 

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

a_i1x₁+a_i2x₂+ … +a_inx_n =b_i =>

• a_i1x₁+a_i2x₂+ … +a_inx_n ≤ b_i,

          - a_i1x₁-a_i2x₂-… – a_inx_n ≤ b_i

 

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

Условие оптимальности  плана: если ЗЛП на максимум, то в F-строке не должно быть отрицательных элементов; если ЗЛП на минимум, то в F-строке не должно быть положительных элементов.

Алгоритм решения:

1. Исходную задачу линейного программирования приводим к каноническому виду путем введения базисных переменных.
2. Базисные переменные выражаем через свободные переменные.
3. Строим начальный план, полагая свободные переменные равными 
   нулю, тогда базисные переменные будут равны свободным членам.
4. Строим первую симплекс-таблицу.
5. Проверяем план на оптимальность. Если план не оптимален, то его улучшаем.
3. Улучшение плана.

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

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

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

г) переменную вводим в базис вместо переменной .

д) элементы новой симплекс-таблицы  пересчитываем по следующим формулам:

 

разрешающий элемент  ,

элементы разрешающего столбца  ,

элементы разрешающей  строки ,

 

остальные элементы симплекс-таблицы  по правилу прямоугольника:

 

 

4. Вновь полученный план проверяем на оптимальность. [2]

 

 

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

 

Алгоритм решения:

1. Используя систему ограничений и условия неотрицательности, строим область допустимых решений.
2. Строим линию уровня . Линией уровня функции двух переменных называется линия, вдоль которой функция сохраняет свое постояное значение.
3. Строим градиент целевой функции. Градиент функции – это вектор, имеющий своими координатами частные производные функции и показывающий направление наискорейшего роста значения функции. Так как целевая функция ЗЛП линейная, то линии уровня целевой функции – прямые и , п – вектор нормали к этим прямым.
4. Перемещаем линию уровня F=0 вдоль градиента функции. Если ЗЛП на минимум, то оптимальное решение находится в первой точке, принадлежащей ОДР; если ЗЛП на максимум, то оптимальное решения находится в последней точке, принадлежащей ОДР.

 

 

 

 

 

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

2.1 Решение задачи линейного  программирования Симплекс-методом

 

Трикотажная фабрика  использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.

 

Таблица 1.

Сорт материала	Свитер	Кофта	Запасы сырья
Шерсть	9	27	606
Силон	15	15	802
Нитрон	15	3	840
Прибыль (у. е.)	11	6	0

 

Математическая постановка задачи

Общая модель:

P₁ и P₂ – виды продукции: свитера и кофты.

s₁, s₂, s₃ – запасы сырья: шерсть, силон, нитрон.

α – прибыль от реализации единицы готовой продукции свитеров.

β – прибыль от реализации единицы готовой продукции кофт.

Решение задачи

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

Пусть х₁ – единица готовой продукции вида P₁,

x₂ – единица готовой продукции вида P₂,

Цель фабрики получить максимальную прибыль от реализации всей продукции  видов P₁ и P₂, тогда:

F=11x₁ +6x₂ → max

Система ограничений:

9x₁ + 27x₂ ≤ 606

15x₁ + 15x₂ ≤ 802

15x₁ + 3x₂ ≤ 840

x₁ ≥ 0, x₂ ≥ 0 условие неотрицательности.

2. Задачу приводим к каноническому виду:

F=11x₁ +6x₂ → max

9x₁ + 27x₂+x₃= 606

15x₁ + 15x₂ +x₄= 802

15x₁ + 3x₂+x₅ = 840

x₁ ≥ 0, x₂ ≥ 0, x₃≥0, x₄≥0, x₅≥0

3. Базисные переменные выражаем через свободные:

x₃=606 – 9x₁ - 27x₂

x₄=802 – 15x₁ - 15x₂

x₅=840 – 15x₁ - 3x₂

4. Записываем начальный план: X₀=(0; 0; 606; 802; 840)
5. Строим первую симплекс-таблицу:

 

 

 

 

 

 

 

 

 

Таблица 2.

Своб. перем. Базис. перем.	-x1	-x2	Свободные члены	Симплексные отношения
x3	9	27	606	≈-0,75
x4	15	15	802	≈0,030
x5	15	3	840	≈-0,090
F-строка	-11	-6	0

  

Начальный план не оптимален, так как в F-строке есть отрицательные элементы.

6. Улучшение плана. Строим вторую симплекс-таблицу, элементы которой пересчитываем по соответствующим формулам.

 

Таблица 3.

Своб. Перем Базис. перем.	Х4	X5	Свободные члены	Симплексные отношения
X3	-0,6	18	124,8
X1	0,07	1	46,5
X2	-1	-12	6,9
F-строка	0,73	5	552,9

 

7. План, соответствующий таблице 3, X₁=(46,5; 6,9; 124,8; 0; 0) оптимален, так как в F-строке нет отрицательных элементов.

Ответ: если предприятие  будет выпускать продукцию вида P₁ и P₂, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.

Максимальная прибыль  для x₁=46 и x₂=6 находится по формуле:

F _max=11*46+6*6=542 единицы.

 

 

2.2 Решение задачи линейного  программирования графическим способом

 

Трикотажная фабрика  использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.

 

Таблица 4.

Сорт материала	Свитер	Кофта	Запасы сырья
Шерсть	9	27	606
Силон	15	15	802
Нитрон	15	3	840
Прибыль (у. е.)	11	6	0

 

Решение задачи

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

Пусть х₁ – единица готовой продукции вида P₁,

x₂ – единица готовой продукции вида P₂,

Цель фабрики получить максимальную прибыль от реализации всей продукции видов P₁ и P₂, тогда:

F=11x₁ + 6x₂ → max

Система ограничений:

9x₁ + 27x₂ ≤ 606

15x₁ + 15x₂ ≤ 802

15x₁ + 3x₂ ≤ 840

x₁ ≥ 0, x₂ ≥ 0 условие неотрицательности.

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

F₁: 9x₁+27x₂=606

F₂: 15x₁+15x₂=802

F₃: 15x₁+3x₂=840

x₁=0, x₂=0

В системе координат  построим эти прямые. В результате будем иметь ОДР. В этой же системе координат строим линию уровня и вектор

 

Рис. 1. Система координат

 

Так как задача на максимум, будем  перемещать линию уровня F=0 вдоль вектора n до тех пор, пока она не пересечет ОДР в самом крайнем своем положении, т.е. при дальнейшем перемещении она не будет с ОДР иметь общие точки. Такой точкой оказалась точка пересечения прямых F_1.

Вычислим ее координаты.

9x₁+27x₂=606

15x₁+15x₂=802

x₁=46,5; x₂=6,9; F _max=11*46,5+6*6,9=552,9

Таким образом, если предприятие  будет выпускать продукцию вида P₁ и P₂, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.

Максимальная прибыль  для x₁=46 и x₂=6 находится по формуле:

F _max=11*46+6*6=542 единицы.

 

 

2.3 Решение задачи линейного  программирования с помощью MS EXCEL

 

Трикотажная фабрика  использует для производства свитеров и кофт чистую шерсть, силон и нитрон, запасы, которых составляют 606, 802 и 840 кг. На изготовление свитера расходуется 9 кг шерсти, 15 кг силона и 15 кг нитрона. На изготовление кофты расходуется 27 кг шерсти, 15 кг силона и 3 кг нитрона. От реализации одного свитера фабрика имеет прибыль 11 у. е., а от одной кофты прибыль составляет 6 у. е. Определить максимальную прибыль от реализации всей продукции производства свитеров и кофт.

 

Таблица 5.

Сорт материала	Свитер	Кофта	Запасы сырья
Шерсть	9	27	606
Силон	15	15	802
Нитрон	15	3	840
Прибыль (у. е.)	11	6	0

 

Решение задачи

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

Пусть х₁ – единица готовой продукции вида P₁,

x₂ – единица готовой продукции вида P₂,

Цель фабрики получить максимальную прибыль от реализации всей продукции видов

P₁ и P₂, тогда:

F=11x₁ +6x₂ → max

Система ограничений:

9x₁ + 27x₂ ≤ 606

15x₁ + 15x₂ ≤ 802

15x₁ + 3x₂ ≤ 840

x₁ ≥ 0, x₂ ≥ 0 условие неотрицательности.

2. Подготовка листа  рабочей книги MS Excel для вычислений – на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 2. Переменные задачи находятся, соответственно, в ячейках С3 и С4. Целевая функция находится в ячейке С6 и содержит формулу: =11*С3+6*С4.

Ограничения на задачу учтены в ячейках С8:D10.

Рис. 2. Рабочий лист MS Excel для решения задачи

 

3. Работа с надстройкой  Поиск решения – воспользовавшись  командой Сервис → Поиск решения,  вводим необходимые данные для  рассматриваемой задачи (установка  данных в окне Поиск решения  приведена на рис. 3)

Рис. 3. Установка необходимых параметров задачи в окне Поиск решения

 

Результат работы по поиску решения помещен на рис 4.

 

Рис. 4. Результат расчета надстройки Поиск решения

 

Если предприятие будет  выпускать продукцию вида P₁ и P₂, в количестве 46,5 и 6,9 единиц, то получит максимальную прибыль в размере 552,9 единиц, но так как продукция должна выпускаться только в целых единицах, то тогда предприятие будет выпускать продукцию в количестве 46 и 6 единиц, и получит максимальную прибыль в размере 542 единицы.