|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Для решения задачи использовать методы северо-западного угла и потенциалов
Решение. Согласно указанию 1) требуется минимизировать стоимость перевозок (суммарные затраты) S = S dijxij. Далее расстояние dij будем обозначать через cij и называть тарифом. Первое базисное решение найдем по методу северо-западного угла.
В клетку с тарифом d11 = c11 = 7 помещаем наибольший возможный груз x = 50, далее выбираем клетку с тарифом 1 и помещаем туда груз 40 и т.д. При этом следим за тем, чтобы на каждом шаге, кроме последнего, из рассмотрения выбывали только одна строка или столбец, в противном случае в одном из выбывающих рядов (в строке или в столбце) ставим ноль в клетку с наименьшим тарифом (в данном случае в клетку (2, 4) с тарифом 1 ставим 0). Проверим является ли полученное базисное решение оптимальным с помощью метода потенциалов. Составим уравнения для всех базисных (загруженных) клеток:
cij = ai + bj (1)
Так как число уравнений m + n – 1 = 3 + 5 –1 = 7, а число потенциалов ai, bj равно m + n = 8, то пусть a1 = 0. Далее находим потенциалы из следствий уравнений (1):
bj = cij - ai или ai = cij - bj.
Результаты заносим в таблицу. Далее находим алгебраические суммы тарифов sij для всех свободных клеток из уравнений: sij = cij – (ai + bj ) (2)
(Запишем только sij < 0, если есть)
s21 = 4 – (2+7)= - 5; s31 = 5 – (7+7)= - 9; s32 = 6 – (7+1)= - 2.
Так как не все sij ³ 0, то базисное решение не является оптимальным. Выбираем клетку (3, 1) с наименьшей из отрицательных алгебраических сумм тарифов - 9 и строим цикл пересчета для получения нового базисного решения.
Перераспределяемый груз xij = min (50; 20; 40) = 20 Запишем новое базисное решение в таблицу и проделаем процедуру пункта до тех пор пока не получим для всех свободных клеток sij ³ 0.
s13 = 7 – (0+9)= - 2; s14 = 4 – (0+8)= - 4;
Так как для всех свободных клеток sij ³ 0, то полученное базисное решение является оптимальным. Наименьшие суммарные затраты Smin = S cijxij = 10 · 7 + 60 · 1 + 20 · 4 + 50 ·2 + 20 · 1 + 40 · 5 + 70 · 2 = 670 Замечание. Данное решение не является единственным, так как клетка (2, 1) имеет
s21 = 4 – (-3+7)= 0. - нулевая алгебраическая сумма тарифов. С помощью цикла пересчета клетки (2, 1) можно получить еще одно оптимальное решение.
81 - 90. Дана задача выпуклого программирования. Требуется: 1) найти решение графическим методом; 2) написать функцию Лагранжа данной задачи и найти ее седловую точку, используя решение задачи, полученное графически.
Решение. 1) найдем решение графическим методом.
Система неравенств определяет область D допустимых значений, ограниченную тремя прямыми и координатными осями. График целевой функции j представляет собой окружность переменного радиуса с центром в точке P (6, 7) (линии уровня целевой функции). Значение целевой функции графически представляет собой квадрат радиуса этой окружности. Минимальным радиусом, удовлетворяющим системе ограничений, будет такой радиус, который обеспечивает касание окружности с границей области так, как это показано на рисунке. Точка М (4; 3) – точка входа линий уровня целевой функции в область D, поэтому jmin(М) =
Искомая точка M определяется при решении системы уравнений:
В этой системе 1-е уравнение определяет прямую (2), а 2-е – прямую, проходящую через точку P перпендикулярно прямой (2).
2) Запишем задачу в стандартном виде:
Функция называется функцией Лагранжа, а переменные - коэффициентами Лагранжа. Точка S называется седловой точкой функции Лагранжа, если для любых выполняются неравенства:
(*)
Если функции дифференцируемы, то условия, определяющие седловую точку (условия Куна-Таккера) следующие:
Найдем седловую точку S(x10, x20, l10, l20, l30), используя решение задачи, полученное графически. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.008 сек.) |