Элемент а В том же столбце где и рассматриваемый элемент аij и В той же строке где и разрешающий элемент а*.

↑

Стр 1 из 2Следующая ⇒

Выполнил: Ислямов Н.Р.

Студент группы №1309

  Проверила: Клочкова К.В.

Лабораторная работа №1

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

Вариант 17

Задача

Предприятие выпускает два вида продукции А и В, при жтом используется сырьё трёх типов. На изготовление единицы изделия А необходимо затратить:

 = 4 кг cырья первого типа,

 = 1 кг cырья второго типа,

 = 5 кг cырья третьего типа.

Для изготовление единицы изделия B тратится:

 = 2 кг cырья первого типа,

 = 2 кг cырья второго типа,

 = 4 кг cырья третьего типа.

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

 = 440 кг cырья первого типа,

 = 400 кг cырья второго типа,

 = 655 кг cырья третьего типа.

Прибыль от реализации единицы изделия А составляет  = 32 денежных единиц, единицы изделия B -  = 24 денежных единиц.

Составить план производства изделий А и B, обеспечивающий максимальную прибыль при их реализации.

Контрольные вопросы:

1. Математическая формулировка ЗЛП?

2. Какие неизвестные в системе называются базисными и как их выбирать?

3. В чем заключается идея симплексного метода?

4. Каковы содержание и последовательность шагов симплекс – алгоритма,  реализованного на симплекс таблицах?

5. Формулировка критерия оптимальности решения ЗЛП для симплексного метода?

6. Каково назначения искусственного базиса и когда он вводится?

7. В чем сущность зацикливания при решение ЗЛП и как оно устраняется? 

Решение

Сформулируем задачу математически: пусть  – количество изделий А и  – количество изделий B, спланированных к производству. Тогда потребуется:

 кг cырья первого типа,

 кг cырья второго типа,

 кг cырья третьего типа.

Таким образом, система ограничений будет иметь вид:

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

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

Рассматриваемая ЗЛП в каноническом виде:

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

В индексной строке таблицы 1 находятся два отрицательных элемента, следовательно, решение  не оптимально.

Таблица 1.

Базисные

пременные

Оценочное

отношение

440/4=110

400/1=400

655/5=131

F

-32

-24

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

𝐵 — элемент, стоящий в одном столбце с  и в одной строке с . 𝐴 — элемент, стоящий в одной строке с  и в одном столбце с . В таблице 2 на место элемента  ставим

Считаем остальные элементы таблицы 2.

2 строка:

3 строка:

Индексная строка:

Таблица 2.

Базисные

пременные

Оценочное

отношение

1/2

1/4

110/(1/2)=220

3/2

-1/4

290/(3/2)=193,33

3/2

-5/4

105/(3/2)=70

F

-8

Опорное решение  является допустимым, значение целевой функции . Полученное решение не является оптимальным, так как в индексной строке есть отрицательный элемент: -8.

Таблица 3.

Базисные

пременные

8/12

-1/3

-1

-5/6

2/3

F

4/3

16/3

Опорное решение Х₃ = (0;70;75;185;0) является допустимым и оптимальным, так как в индексной строке нет отрицательных элементов и все свободные члены положительны. Х_max = (0;70;75;185;0) и значение целевой функции F_max = F (X_max) = 4080.

Экономический вывод: продукцию вида А необходимо произвести 0 единиц, вида В – 70 единиц. При этом прибыль будет максимальна и равна 4080 денежных единиц. Значение переменной х₃=75, следовательно, сырья первого типа осталось неиспользованным 75 кг. Значение переменной х₄=185, следовательно, сырья второго типа осталось неиспользованным 185 кг. Значение переменной х₅=0, следовательно, сырьё третьего типа израсходовано полностью.

Ответы на контрольные вопросы.

1.Математическая формулировка ЗЛП.

Пусть х₁ количество изделий А планируемых к производству, х₂ количество изделий В.

Обеспечение сырьем I типа: b₁

Обеспечение сырьем II типа: b₂

Обеспечение сырьем III типа: b₃

Сырья I типа потребуется: а₁₁ × х₁ + а₁₂ × х₂

Сырья II типа потребуется: а₂₁ × х₁ + а₂₂ × х₂

Сырья III типа потребуется: а₃₁ × х₁ + а₃₂ × х₂

а_ij – количество сырья

Получим:

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

2.Какие неизвестные в системе называются базисными и как их выбирать?

За базисные перемены удобно взять такие переменные, которые входят только в одно уравнения и нет уравнения, в которых бы они не входили. Таким свойством обладают дополнительные переменные.

3.В чем заключается идея симплексного метода?

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

4.Каковы содержание и последовательность шагов симплекс – алгоритма, реализованного на симплекс таблицах?

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

Последняя строка таблицы соответствует – F + × x1 + x2 = 0.

Запишем первое опорное решение:

Если среди базисных переменных нет каких-то переменных, то ноль, в данном случае это x₁ и x₂

Х₁ = (0; 0; /; /; /)

F = 0

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

Данный план не является оптимальным, так как прибыль является нулевой.

Необходимо сделать пересчёт таблицы в индексной строке находим максимально положительный элемент () и соответствующий столбик будем называть ключевым.

Вычисляем оценочные отношения b_i / a_ij, где a_ij – элементы ключевого столбца.

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

Элемент стоящий на пересечении ключевой строки и ключевого столбца называется разрешающим и обозначается а^*.

Перейдём к составлению таблицы 2.

Переменную соответствующую ключевому столбцу переводим в базисную на месте переменной соответствующей ключевой строке.

Остальные оставляем на месте.

перемен.

базис

x₁

x₂

x₃

x₄

x₅

b_i

Оценочное отношение

x₃

x₄

x₅

- F

В ключевом столбце на месте разрешающего элемента ставится единица, все остальные элементы в данном столбце = 0. Все элементы ключевой строки таблицы 1 делим на разрешающий элемент и ставим на соответствующее место.

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

а_ij               B

A                a^*

Познавательные статьи:



Организация работы процедурного кабинета

Статус республик в составе РФ

Понятие финансов, их функции и особенности

Сущность демографической политии