![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Графический способ решения линейных оптимизационных моделей
Рассмотрим линейнуюоптимизационную модель в общей форме записи:
с геометрической точки зрения. Целевая функция (1.8) определяет семейство параллельных гиперплоскостей уровня цели, каждой из которых соответствует определенное значение функции Так как планы линейнойоптимизационной модели – это упорядоченные совокупности n чисел ( Теорема 1.1. Множество планов линейнойоптимизационной модели является выпуклым. Доказательство (для канонической линейнойоптимизационной модели). Линейнуюоптимизационную модель можно записать и в матричном виде:
где
Пусть
также является планом данной задачи. Действительно, подставив
что и требовалось доказать. Введением дополнительного неравенства:
задачу с неограниченной областью планов формально можно преобразовать в задачу с ограниченной областью. Поэтому в дальнейшем будем предполагать, что множество планов линейнойоптимизационной модели является выпуклым многогранником и называть его многогранником планов. Таким образом, линейнуюоптимизационную модель на геометрическом языке можно сформулировать следующим образом: найти точку Пусть
через которую проходит прямая семейства
соответствующая наибольшему (наименьшему) значению функции Прямые 1) нужно построить многоугольник (многоугольную область) планов, т. е. множество допустимых решений Ω с учетом системы ограничений (1.13); 2) построить вектор 3) параллельным перемещением прямой 4) решая совместно уравнения прямых, пересекающихся в точке оптимума, найти ее координаты, а затем При определении оптимального плана возможны случаи: 1) функция 2) максимум может достигаться в одной точке, минимума не имеет ( 3) функция Таким образом, оптимальный план может быть единственным; оптимальных планов может быть бесконечное множество; целевая функция может быть не ограничена; задача не имеет решения (см. рисунок 1.1). Анализируя рассмотренные случаи, можно сделать вывод: если целевая функция Отметим, что графическим методом можно решать линейнуюоптимизационную модель со многими переменными. Нужно, чтобы в канонической записи задачи разность между числом неизвестных (
Рисунок 1.1.
Пример 1.7. Две базы поставляют продукцию трем потребителям. Объемы запасов, потребности и затраты на перевозку единицы продукции с баз представлены в таблице 1.3: Таблица 1.3
Необходимо спланировать перевозки таким образом, чтобы затраты на них были минимальными. Решение. Обозначим через Таблица 1.4
Составим математическую модель. Определим план перевозок таким образом, чтобы минимизировать стоимость перевозок:
При этом должны выполняться следующие ограничения: 1) продукция с баз должна быть вывезена:
2) заявки потребителей должны быть удовлетворены полностью:
3) должны быть исключены обратные перевозки:
Это модель закрытой транспортной задачи. Так как
nm – (n + m – 1) = 2 · 3 – (2 + 3 – 1) = 2,
то задача может быть решена графически. Выберем две свободные неизвестные, например,
Подставим значения
Из требования неотрицательности всех переменных (
Целевая функция 1) построим область Ω – множество допустимых решений, удовлетворяющих системе ограничений:
Для построения области соответствующие данным неравенствам (см. рисунок 1.2).
25 20
10
0 10 15 20
Рисунок 1.2.
Каждая из них делит плоскость на две полуплоскости, одна из которых является решением соответствующего неравенства. Для выбора полуплоскости, являющейся решением неравенства, подставляем начало координат Стрелки указывают полуплоскости, являющиеся областями решений данных неравенств. Пересечение отмеченных полуплоскостей – заштрихованный многоугольник на рисунке 1.2 – область решения данной системы. 2) построим вектор 3) проведем линию 4) так как ищется максимум 5) решаем систему из уравнений прямых, пересекающихся в точке оптимума:
6) находим координаты точки оптимума:
7) далее находим значения остальных неизвестных
Тогда минимум целевой функции: Оптимальный план перевозок записывается в виде таблицы 1.5:
Таблица 1.5
или матрицы
|