АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Для решения задачи использовать методы северо-западного угла и потенциалов

Читайте также:
  1. I Психологические принципы, задачи и функции социальной работы
  2. I. ГИМНАСТИКА, ЕЕ ЗАДАЧИ И МЕТОДИЧЕСКИЕ ОСОБЕННОСТИ
  3. I. ЗАДАЧИ ПЕДАГОГИЧЕСКОЙ ПРАКТИКИ
  4. I. Ситуационные задачи и тестовые задания.
  5. II Съезд Советов, его основные решения. Первые шаги новой государственной власти в России (октябрь 1917 - первая половина 1918 гг.)
  6. II. Методы непрямого остеосинтеза.
  7. II. Основные задачи и функции
  8. II. Основные задачи и функции
  9. II. Рыночные методы.
  10. II. ЦЕЛИ, ЗАДАЧИ И ПРИНЦИПЫ ДЕЯТЕЛЬНОСТИ ВОИ
  11. II. Цель и задачи государственной политики в области развития инновационной системы
  12. III. Параметрические методы.
7x. 90, 70, 110,
50, 60, 50, 40, 70.

Решение. Согласно указанию 1) требуется минимизировать стоимость перевозок (суммарные затраты) S = S dijxij. Далее расстояние dij будем обозначать через cij и называть тарифом.

Первое базисное решение найдем по методу северо-западного угла.

П Б           ai
  50 40        
    20   0    
             
  bj         -1   -5  

 

В клетку с тарифом 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.

П Б           ai
  30     4    
            -7  
  20         - 2
  bj              

 

 

s13 = 7 – (0+9)= - 2; s14 = 4 – (0+8)= - 4;

 

П Б           ai
             
            -3
            -2
  bj              

Так как для всех свободных клеток 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) написать функцию Лагранжа данной задачи и найти ее седловую точку, используя решение задачи, полученное графически.

8х. ,
 

Решение. 1) найдем решение графическим методом.

 

 


Система неравенств определяет область D допустимых значений, ограниченную тремя прямыми и координатными осями. График целевой функции j представляет собой окружность переменного радиуса с центром в точке P (6, 7) (линии уровня целевой функции). Значение целевой функции графически представляет собой квадрат радиуса этой окружности. Минимальным радиусом, удовлетворяющим системе ограничений, будет такой радиус, который обеспечивает касание окружности с границей области так, как это показано на рисунке. Точка М (4; 3) – точка входа линий уровня целевой функции в область D, поэтому jmin(М) =

 

Искомая точка M определяется при решении системы уравнений:

 

 

 

 

В этой системе 1-е уравнение определяет прямую (2), а 2-е – прямую, проходящую через точку P перпендикулярно прямой (2).

 

2) Запишем задачу в стандартном виде:

 

Функция называется функцией Лагранжа, а переменные - коэффициентами Лагранжа.

Точка S называется седловой точкой функции Лагранжа, если для любых выполняются неравенства:

 

(*)

 

Если функции дифференцируемы, то условия, определяющие седловую точку (условия Куна-Таккера) следующие:

 

 

 

Найдем седловую точку S(x10, x20, l10, l20, l30), используя решение задачи, полученное графически.


1 | 2 | 3 | 4 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)