ГБОУ Школа 1101

Построение программного комплекса, реализующего симплекс метод в экономических и биологических задачах

10 «к»  10 «б»  10 «к»

Построение программного комплекса, реализующего симплекс метод в экономических и биологических задачах

       

Симплекс метод и линейное программирование в экономике

  10 «б»

3 слайд

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

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

4 слайд

Стандартная ЗЛП

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

Каноническая ЗЛП

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

5 слайд

Симплекс-метод

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

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

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

6 слайд

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

Возрастать убывать оставаться неизменной.

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

Практическое применение симплекс метода в задачах биолого-экономического содержания

10 «к» 

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

Слайд 18

На слайде представлен алгоритм симплекс-метода, по которому происходит решение задач на симплекс-метод

Cлайд 19

Задача  2. 

Для изготовления изделия А и В предприятие использует три вида сырья. На производство одного изделия А, требуется 2 единицы сырья первого вида и 2 единицы  – второго, а на производство одного изделия В соответственно 3 единицы первого, 1 единица второго и 3 единицы третьего. Производство обеспечено сырьем первого вида в количестве 19 единиц,  второго -  13 единиц и третьего -  15 .Производство одного изделия А дает предприятию 7 млн. руб. прибыли, а изделие В – 5 млн. руб. прибыли. Составить план производства изделий А и В, максимизирующий общую прибыль предприятия.

Решение:

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

Ресурсы	Товары	Запас ресурсов
А	Б
первый	2	3	19
второй	2	1	13
третий	0	3	15
Прибыль	7	5

Слайд 20

1. Составим план производства изделий А и В, максимизирующий общую прибыль предприятия.  Обозначим черезизапланированный объем производства товаров А и В. Из экономического смысла величин иследует, что , . Тогда, учитывая количество единиц ресурсов, затрачиваемых при производстве товаров А и В, а также запасы этих ресурсов, получим следующую систему ограничений:

    0

При этом реализация товаров А и В дает прибыль:

Функция F(max) - называется целевой функцией, которая совместно с описанной выше системой ограничений представляет собой математическую модель приведенной  задачи. Решим ее симплекс-методом.

Слайд 21

I итерация:

1 этап: формирование исходной симплекс-таблицы.

1. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной: S3, S4, S5.

2. В полученной системе уравнений примем в качестве разрешенных (базисных) переменные S3, S4, S5, тогда свободными переменными будут х1,х2. Выразим базисные переменные через свободные.

Приведем целевую функцию к следующему виду:

Слайд 23

2 этап: определение базисного решения.

Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т. е.:

.

3 этап: проверка совместности системы ограничений ЗЛП.

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

4 этап: проверка ограниченности целевой функции.

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

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности.

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

Слайд 24-25

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 1, таких колонок две: колонка «S4» и колонка «х1». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х1» содержит наименьший элемент (–7) в сравнении с колонкой «х2». Следовательно, ее принимаем в качестве разрешенной.

8.2. Определение разрешающей строки.

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

Cлайд 25

В таблице наименьшее положительное оценочное отношение соответствует строке «х1», следовательно, она будет разрешающей.

Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент (X1;S4)=2 , который расположен на пересечении строки «S4» и колонки «х1».

Слайд 26

9 этап: Преобразование симплекс-таблицы.

Разрешающий элемент показывает одну базисную и одну свободную переменные, меняем X1 и S4 местами в симплекс-таблице.

9.1. Преобразование разрешающего элемента.

(2)^(-1)=1/2

9.2. Преобразование разрешающей строки.

Элементы разрешающей строки таблицы 2 делим на разрешающий элемент данной симплекс-таблицы.

9.3. Преобразование разрешающей колонки

Элементы разрешающей колонки таблицы 1 делим на разрешающий элемент данной симплекс-таблицы, а результат берется с обратным знаком.

Слайд 27

9.4. Преобразование остальных элементов симплекс-таблицы.

Преобразование остальных элементов симплекс-таблицы осуществляется по правилу «прямоугольника».

К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «S3» и колонки «B», условно обозначим его «S3B». В таблице мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т. е. в клетке «S3B»), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «S3B» будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент, а в числителе произведение двух других неиспользованных вершин.

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

Слайд 28

2 этап: определение базисного решения.

Базисное решение: Fmax=(13,2,3,0,5)

Значение целевой функции улучшилось, но он неоптимальный, так в последней строке симплексной таблицы 2 имеется отрицательная оценка  (-3/2)

Проверяем все этапы снова, делаем заключение, что базисное решение допустимое.  Переходим к 8 этапу

Слайд 29

8.1. Определение разрешающей колонки.

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

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 2) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 3.

Слайд 30

Базисное решение: Fmax=(5,3,0,0,6) – оптимальное. Так как нулевых оценок в столбцах свободных переменных (на данном опорном плане это – S3 и S4) нет, то найденное оптимальное решение единственное. Оптимальное значение целевой функции Fmax=50.

Вывод: Следовательно оптимальным планом, дающим максимальную прибыль в 50 единиц является производство 5 единиц товара А и 3 единиц товара В.  При этом остается неиспользованным  из запасов ресурс третьего типа в размере 6 единиц. Решение задачи закончено.

Слайд 31

Задача 2

Условие: Средний дневной рацион хищника составляет 10 ед. пищи A, 12 ед.

пищи B и 12 ед. пищи C. Эти потребности удовлетворяются в процессе его питания

двумя видами жертвы. Одна жертва вида I дает соответственно 5, 2 и 1 ед. пищи

A, В и С, а вида II – соответственно 1, 2 и 4 ед. пищи А, В и С. На поимку и усвоение

жертвы вида I требуется в среднем 3 ед. энергии.  Аналогичные потребности для

вида II составляют 2 ед. энергии. Сколько жертв каждого вида следует поймать

хищнику, чтобы удовлетворить свои  пищевые потребности с наименьшими

затратами энергии?

Слайд 34

1) Начальное базисное решение:  Fmax=(X1,X2,X3,S1,S2)=(0,0,0, 3,2)

2) Разрешенная колонка: X2

3) Разрешенная строка: S2

Слайд 35

Преобразование симплекс-таблицы.

Разрешающий элемент показывает одну базисную и одну свободную переменные, меняем S2 и X2 местами в симплекс-таблице.

Преобразование разрешающего элемента.

(2)^(-1)=1/2

Преобразование разрешающей строки.

Элементы разрешающей строки таблицы 2 делим на разрешающий элемент данной симплекс-таблицы.

Преобразование разрешающей колонки

Элементы разрешающей колонки таблицы 1 делим на разрешающий элемент данной симплекс-таблицы, а результат берется с обратным знаком.

Преобразование остальных элементов симплекс-таблицы.

Правило «прямоугольника».

Слайд 36

Базисное решение: Fmax=(4,1,0,1,0)

Значение целевой функции на этом плане: Fmax=12

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

Разрешающая колонка: X1  Разрешающая строка: S3

Слайд 37

Базисное решение: Fmax=(0,0,9,1,5) – оптимальное. Так как нулевых оценок в столбцах свободных переменных нет, то найденное оптимальное решение единственное. Оптимальное значение целевой функции Fmax=13

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

Cлайд 38

Горное озеро в одном национальном парке заселяется каждой весной двумя видами рыб: S1 и S2. Средняя масса заселяемой рыбы равна 4 фунтам для S1 и 2 фунтам для S2. В озере имеется два вида пищи: F1 и F2. Среднее потребности одной рыбы вида S1 составляют 1 ед. F1 и 3 ед. F2 в день. Аналогичные потребности для S2 составляют 2 ед. F1 и 1 ед. F2. Если ежедневный запас пищи поддерживается на уровне 500 ед. F1 и 900 ед. F2, то как следует заселить озеро, чтобы максимизировать общую массу двух видов рыб?

Слайд 42

Базисное решение: Fmax=(120,340,0,0) – оптимальное. Так как нулевых оценок в столбцах свободных переменных нет, то найденное оптимальное решение единственное. Оптимальное значение целевой функции Fmax=1280

Ответ: В озере можно поддерживать максимальную массу 1280 фунтов, если заселить 260 рыб вида S1 и 120 рыб вида S2.