Слайды и текст доклада
Pic.1
Симплекс-метод Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 году, однако еще в 1939 году идеи метода были разработаны российским ученым А. В. Канторовичем. СМ …
Pic.2
Из линейной алгебры известно: Из линейной алгебры известно: Равенства называются линейно независимыми, если никакое из них нельзя получить из других путем умножения на какие-то коэффициенты и …
Pic.3
Для реализации СМ необходимо 3 основных момента: Для реализации СМ необходимо 3 основных момента: Необходимо отыскать способ отыскания исходного допустимого решения. Должен быть описан механизм …
Pic.5
Алгоритм решения задачи : Стандартная задача ЛП сводится к основной задаче. F= c1x1+…+cnxnmax a11x1+…+a1nxn+xn+1=b1 a11x1+…+a1nxn +xn+2=b2 …. am1x1+…+amnxn+ xn+m=bm xj 0 j=1,n
Pic.6
Определяется начальное допустимое решение Для этого запишем систему ограничений в векторной форме x1A1+x2A2+…+ xnAn+xn+1An+1+…+ xn+mAn+m =A0 , где
Pic.7
По данным задачи составляется симплекс-таблица:
Pic.8
В (m+1) –й строке в столбцах векторов Aj записываются значения В (m+1) –й строке в столбцах векторов Aj записываются значения
Pic.9
Полученное допустимое решение проверяется на оптимальность (в случае максимизации). Полученное допустимое решение проверяется на оптимальность (в случае максимизации). Используются теоремы: Теорема2 …
Pic.10
Наличие оптимальности проверяется по следующему признаку: Наличие оптимальности проверяется по следующему признаку: Согласно теорем выясняется, имеется ли хотя бы одно отрицательное ∆j (ЦФ …
Pic.11
В случае исследования целевой функции на минимум допустимое решение является оптимальным, если все разности ∆j ≤ 0 . Если хотя бы одно ∆j>0 , тогда в базис включается вектор, соответствующий этой …
Pic.12
Находится направляющий столбец и направляющая строка. Находится направляющий столбец и направляющая строка. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом ∆j …
Pic.13
Определяются положительные компоненты нового допустимого решения и коэффициенты разложения векторов Aj по векторам нового базиса и числа F0 ∆j по следующим формулам: Определяются положительные …
Pic.14
Полученные данные записываются в новую симплекс–таблицу:
Pic.15
Проверяют найденное допустимое решение на оптимальность Проверяют найденное допустимое решение на оптимальность Если решение не является оптимальным то возвращаются к п. 5 , если оптимальное или …
Pic.16
Пример Для изготовления изделий A, B и C предприятие использует три вида сырья. Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является …
Pic.17
Составим математическую модель задачи.
Pic.18
Запишем эту задачу в форме основной задачи линейного программирования.
Pic.19
Полученную систему уравнений запишем в векторной форме:
Pic.20
Среди векторов имеются три единичных вектора , которые образуют базис трехмерного векторного пространства. Среди векторов имеются три единичных вектора , которые образуют базис трехмерного векторного …
Pic.21
Составим первую симплексную таблицу и проверим исходное решение на оптимальность.
Pic.22
Значения, стоящие в четвертой строке симплексной таблицы вычисляются следующим образом:
Pic.23
Исходное решение не является оптимальным, т. к. в 4-й строке таблицы имеются три отрицательных числа: Исходное решение не является оптимальным, т. к. в 4-й строке таблицы имеются три отрицательных …
Pic.25
Составим новую симплексную таблицу:
Pic.26
Заполняем строку A3, разделив все элементы на разрешающий а22 =8
Pic.27
Вычисление остальных элементов таблицы производим по рекуррентным формулам:
Pic.28
Тогда компоненты вектора A0 находятся
Pic.30
Вычислим компоненты вектора A1:
Pic.32
Аналогично находятся элементы столбцов векторов A2, A5.
Pic.33
Теперь заполним четвертую строку симплексной таблицы.
Pic.35
Решение X2 не является оптимальным, т. к. в 4-ой строке последней симплекс–таблице в столбце вектора A2 стоит отрицательное число –2. В базис вводится вектор A2,
Pic.38
Ответ Это решение соответствует плану выпуска продукции, включающего изготовление 8 изделий B и 20 изделий C. При этом сырье I и II видов используется полностью и остается неиспользованным 96 кг …
Pic.39
Вопросы В чем смысл симплекс-метода? Что необходимо для реализации СМ? Теорема о соответствии допустимых решений задачи и многоугольника решений. С чего начинается решение задачи СМ? Как определяется …
Pic.40
Что меняется при определении минимального решения? Что меняется при определении минимального решения? Как определяется направляющий столбец? Как определяется направляющая строка? Как рассчитать …
Скачать презентацию
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!