Симплекс метод решения задачи линейного программирования
Задача №1 (Симплекс метод решения задачи линейного программирования.)
Найти Fmax = 9x1 + 10x2 + 16x3, при ограничениях:
Запишем задачу в каноническом виде:
F=9x1 + 10x2 + 16x3 →max
Заполним начальную таблицу:
Таблица 0.
| 0 | 9 | 10 | 16 | 0 | 0 | 0 | Отношение, θ | ||
| i | Базис | ||||||||
| 1 | 0 | 360 | 18 | 15 | 12 | 1 | 0 | 0 | 30 |
| 2 | 0 | 192 | 6 | 4 | 8 | 0 | 1 | 0 | 24 |
| 3 | 0 | 180 | 5 | 3 | 3 | 0 | 0 | 1 | 60 |
| ∆j | 0 | -9 | -10 | -16 | 0 | 0 | 0 | ||
| Zj | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
Zj вычисляется по формуле
Оценки (∆j) вычисляются по формуле , где - коэффициент из первой строки таблицы.
Выбираем минимальную (отрицательную) оценку. Она определяет направляющий столбец.
Заполняем столбец «θ», по минимальному значению определяем направляющую строку.
На пересечение строки и столбца находится направляющий элемент.
Заполняем новую таблицу
Таблица 1.
| 0 | 9 | 10 | 16 | 0 | 0 | 0 | Отношение, θ | |
| i | Базис | |||||||
| 1 | 0 | 72 | 9 | 9 | 0 | 1 | 0 | 8 |
| 2 | 16 | 24 | 1 | 0 | 0 | 48 | ||
| 3 | 0 | 108 | 0 | 0 | - | 1 | 72 | |
| ∆j | 384 | 3 | -2 | 0 | 0 | 2 | 0 | |
| Zj | 384 | 12 | 8 | 0 | 0 | 2 | 0 | |
Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т. е.
Столбец становится базисным, то есть единичным.
Новые значения в направляющей строке получаем делением элементов этой строки на направляющий элемент.
Остальные элементы в небазисных столбцах и в столбце вычисляем по правилу треугольника.
Выбираем минимальную отрицательную оценку. Она определяет направляющий столбец.
Заполняем столбец «θ»
По минимальному значению определяем направляющую строку.
На пересечении направляющей строки и столбца находится направляющий элемент.
Заполнение второй таблицы осуществляется по аналогии с предыдущей.
Таблица 2.
| 0 | 9 | 10 | 16 | 0 | 0 | 0 | Отношение, θ | |
| i | Базис | |||||||
| 1 | 10 | 8 | 1 | 1 | 0 | - | 0 | ______ |
| 2 | 16 | 20 | 0 | 1 | - | 0 | ______ | |
| 3 | 0 | 96 | 0 | 0 | - | 1 | ______ | |
| ∆j | 400 | 5 | 0 | 0 | 0 | |||
| Zj | 400 | 14 | 10 | 16 | 0 | |||
Так как нет отрицательных оценок ∆j, значит выполняется признак оптимальности и не вводились искусственные переменные, то получено оптимальное решение.
Ответ:
Максимальное значение функции Fmax =400 достигается в точке с координатами:
=0
=8
=20
=0
=0
=96
Задача №2 (Метод Литтла)
Найти кратчайший путь в графе, заданном графически в виде чертежа, методом Литтла.
Из чертежа запишем матрицу расстояний. (Расстояние от т.1 до т.2 равно:
, и т.д.)
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | ∞ | 18,87 | 49,48 | 51,86 | 80,51 | 97,42 |
| 2 | 18,87 | ∞ | 32,06 | 34,48 | 65,15 | 84,01 |
| 3 | 49,48 | 32,06 | ∞ | 31,76 | 61,19 | 83,20 |
| 4 | 51,86 | 34,48 | 31,76 | ∞ | 32,14 | 53,15 |
| 5 | 80,51 | 65,15 | 61,19 | 32,14 | ∞ | 22,14 |
| 6 | 97,42 | 84,01 | 83,20 | 53,15 | 22,14 | &
Оценок: 1000 (Средняя 5 из 5)
Наверняка у вас есть товары или услуги, продажа которых приносит вам максимальную прибыль. Для быстрого старта в сети вам необходимо создание посадочной страницы (одностраничного сайта), на которой будет размещена информация о маржинальных товарах/услугах интернет магазина. За 8 лет опыта разработки конверсионных страниц мы выработали оптимальную структуру, которая позволит привлекать через landing page больше продаж. На такую структуру «одевается» ваш контент — фирменный стиль, тексты, фотографии, уникальные торговые предложения, после чего страница выходит в свет. Разработка лендинга и запуск в сети — до 7 рабочих дней. Стоит отметить, что в разработку самой посадочной страницы входит и написание копирайтером продающих текстов для вашего бизнеса, чтобы каждый посетитель страницы захотел совершить покупку именно у вас. Результат: качественно разработаная продающая посадочная страница, которая готова приносить вам новых клиентов. © 2016 - 2022 BigEdu.ru
|