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

Нахождение базиса угловой точки. Пример

Читайте также:
  1. A)нахождение средней из двух соседних средних, для отнесения полученного результата к определенной дате
  2. I. 1.1. Пример разработки модели задачи технического контроля
  3. IV. ТИПОВОЙ ПРИМЕР РАСЧЕТОВ.
  4. X. примерный перечень вопросов к итоговой аттестации
  5. Алг «нахождение минимума»
  6. Алгоритм метода средней точки.
  7. Б2. Пример №2
  8. Билет 23 Существование ортогонального базиса в евклидовом пространстве.
  9. Билет28 Матрица перехода от одного ортонормированного базиса к другому.
  10. Буду на работе с драконом примерно до 21:00.
  11. Булевы функции. Способы задания. Примеры.
  12. В нашем примере каждый доллар первоначального депозита обеспечил 5 дол. средств на банковских счетах.

Рассм след вспомог задачу: Введем в рассм искусств перемен , ()=y≥0. (1) Т.к. мн-во : (2). И рассм задачу: .

Если Г1(z*)<0?,то исх задача имеет несовместную с-му ограничений. Далее будем считать Г1(z*)=0

1 случай: В симплекс-табл в мн-ве базисных пер-нных отсутсв.искуственные, то полученную таблицу можно исп. в кач-ве исходной для применения симплек-метода в реш первонач зад.. 2 случай: В с-т в соответ точке z* присутствуют искуственные переменные в списке базисных, но при этом все коэф, стоящие в строке, соответ этой искуств перем-ой и столбцам, соотв основным, перем =0, то соответс-ющие огра-ия явл линейной комбинацией ур-ний из с-мы Ах=в и это огр-ия следует удалить. Если в с-т реш зад (2,3)искуственные переменные присутствуют в мн-ве базисных и при этом в строке соответ. Этой искуственной переменной найдется положительный элемент, стоящий в столбцах соотв основ небаз пер-ным, то выбрав этот элемент в кач-ве разреш, следует перещитать с-т с целью перехода к другому базису, рассматрив угл точки.

В оставшихся сл в мн-ве осн. Перем, по опред правилам выделяем переменные, значение которых для выполнения задачи могут быть только =0

Пример 1.

Угловая точка мн-ва планов вспомогательной задачи легко определяется. Это точка x=(0; 0; 0; 80; 0; 4), она имеет единичный базис.

                -1  
Сб СЧ  
                14/3
-1           -1   4/7->
    -5   -7 -2          

 

                -1
Сб СЧ
  500/7 23/7   96/7   15/7 -15/7
  4/7 5/7   2/7   -1/7 1/7
               

;

Базис точки не содержит искусственной переменной поэтому совпадает с базисом угловой точки мн-ва X.

Для завершения решения задачи, во второй таблице удаляем ∆-оценки, заменяем коэффициент целевой функции на коэффициент целевой функции исходной задачи. Если не предполагается дополн. анализ задачи, то столбцы искуссст. перем. можно удалить.

      -3 -2 -6    
Сб СЧ
  500/7 23/7   96/7   15/7
  4/7 5/7   2/7   -1/7
  J=-8/7   11/7   38/7   2/7

; ; Минимум целевой ф-ции достигается в точке x=(0; 4/7; 0) мин знач равно 8/7.

12. Постановка ТЗ. Построение нач. плана перевозок методом северо-западного угла, методом мин. элемента.

Пусть имеется m пунктов пр-ва однородной продукции с объемами пр-ва аi, i=1,m, и n пункт.потребления этой продукции с потребностями bj, j=1,n и i=1mai=∑j=1nbj.

Известны стоимости cij перевозки одной еденицы продукции из i -го пункта производства в j -ый пункт потребления. Требуется определить объем перевозок xij≥0 чтобы i=1mj=1nсijxij→min при усл, что j=1nxij=ai и i=1mxij=bj

ТЗ решается с использованием таблицы спец вида, кот. наз трансп таблицей. Строки соотв пунктам производ, столбцы- пунктам потребления.В правом нижнем углу каждой клетки записыв стоим перев ед прод из i-ого в j-ый.В левй верхний угол запис перевозки, если эти перевозки не нулевые. Сумма перевозки по строкам должны = объему производства, а сумма перевозок по столбцам = объему потребления.

Положим x11=min{a1,b1}. Если a1>b1, то излишек a1-b1 завозим из А1 в пункт В2, т. е. полагаем x12=min{a1-b1,b2}. Если a1<b1, то остаток b1-a1 завозим из пункта А2, т. е. полагаем x21=min{b1-a12}. Продолжая действовать по той же схеме, постепенно исчерпаем запасы в пунктах А1, …, Аn и удовлетворим запасы в пунктах В1, …, Вm т. е. получим допустимый план перевозок. Т. к. заполнение таблицы начинается с клетки {1,1} (с северо-западного угла), то метод получил название «Северо-западного угла».

Метод минимального эл-та отличается только способом выбора клетки для заполнения очередной перевозки: на каждом шаге выбирается клетка с минимальной стоимостью перевозки.


 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |

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



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