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

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

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

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

 

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

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

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

 

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

 

 

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 единицы.