Принятие решений на основе методов целочисленного программирования

Нажмите для полного просмотра!

Принятие решений на основе методов целочисленного программирования, слайд №2

Принятие решений на основе методов целочисленного программирования, слайд №3

Принятие решений на основе методов целочисленного программирования, слайд №4

Принятие решений на основе методов целочисленного программирования, слайд №5

Принятие решений на основе методов целочисленного программирования, слайд №6

Принятие решений на основе методов целочисленного программирования, слайд №7

Принятие решений на основе методов целочисленного программирования, слайд №8

Принятие решений на основе методов целочисленного программирования, слайд №9

Принятие решений на основе методов целочисленного программирования, слайд №10

Принятие решений на основе методов целочисленного программирования, слайд №11

Принятие решений на основе методов целочисленного программирования, слайд №12

Принятие решений на основе методов целочисленного программирования, слайд №13

Принятие решений на основе методов целочисленного программирования, слайд №14

Принятие решений на основе методов целочисленного программирования, слайд №15

Принятие решений на основе методов целочисленного программирования, слайд №16

Принятие решений на основе методов целочисленного программирования, слайд №17

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Принятие решений на основе методов целочисленного программирования. Доклад-сообщение содержит 17 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Принятие решений на основе методов целочисленного программирования Выполнили: Дудкина Анастасия, Осипова Алена, Полякова Софья, Смирнова Анастасия

Слайд 2

Описание слайда:

История симплекс-метода Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Сущность метода: построение базисных решений, на которых монотонно убывает линейный функционал, до ситуации, когда выполняются необходимые условия локальной оптимальности. В работе Л. В. Канторовича "Математические методы организации и планирования производства" (1939 г.) были впервые изложены принципы новой отрасли математики, которая позднее получила название линейного программирования.

Слайд 3

Описание слайда:

Решение задачи симплекс-методом Пусть x1, x2, x3 - количество реализованных товаров, в тыс. руб., 1, 2, 3 - ей групп, соответственно. Тогда математическая модель задачи имеет вид: F = 4·x1 + 5·x2 + 4·x3 –>max

Слайд 4

Описание слайда:

В качестве базиса возьмем x4 = 240; x5 = 200; x6 = 160. В качестве базиса возьмем x4 = 240; x5 = 200; x6 = 160. Данные заносим в симплекс-таблицу

Слайд 5

Описание слайда:

Вычисляем оценки по формуле: Вычисляем оценки по формуле:

Слайд 6

Описание слайда:

Выводим переменную x6 из базиса Выводим переменную x6 из базиса

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

Получаем новую симплекс – таблицу 3 Получаем новую симплекс – таблицу 3

Слайд 11

Описание слайда:

Поскольку отрицательных оценок нет, то план оптимален. Поскольку отрицательных оценок нет, то план оптимален. Решение задачи: x1 = 40; x2 = 0; x3 = 0; x4 = 160; x5 = 40; x6 = 0; Fmax = 160 Ответ: x1 = 40; x2 = 0; x3 = 0; x4 = 160; x5 = 40; x6 = 0; Fmax = 160 То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит Fmax = 160 тыс. руб.

Слайд 12

Описание слайда:

На основе симплекс-метода задачу можно продолжить решать с помощью следующих методов Значительная часть задач, относящихся к задачам линейного программирования, требует численного решения. К ним относятся задачи, у которых переменные величины означают количество единиц неделимой продукции. Методы решения задач целочисленного программирования: Методы отсечений. К ним относится метод отсекающихся плоскостей Гомори. Комбинаторные методы. К ним относится метод ветвей и границ Эти методы используются только тогда когда целочисленные переменные являются булевыми (т.е. могут принимать только два значения 0 и 1)

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

Метод ветвей и границ Суть: упорядоченный перебор вариантов и рассмотрение лишь тех из них, которые оказываются по определенным признакам пересекающимися. Алгоритм: Решение непрерывной задачи. Если полученное значение является целочисленным то решение оптимальное. Формирование ветвей исследования. Выбор переменной на основе которой организуется процесс ветвлений влияет на эффективность решения задач Решение задачи Решение осуществляется на основе итоговой симплекс-таблицы.

Слайд 15

Описание слайда:

Условия задачи Найти оптимальное решение стандартной задачи максимизации для целевой функции L= X1 + 3Х2 + Х3 max с системой ограничений 5Х1 + 3Х2 ≤ 8, Х1 + 2Х2 + 4Х3 ≤ 4, Х2+Х3 ≤ 1 И условиями отрицательности Хj ≥ 0, j = 1, 2, 2.