Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Решение транспортной задачи в среде Maple

Содержание

СодержаниеФормулировка транспортной задачиМатематическая модель транспортной задачиНеобходимое и достаточное условия разрешимости транспортной задачиОпорное решение транспортной задачи. ЦиклыПостроение начального опорного решения методом минимальной стоимостиПереход от одного опорного решения к другомуМетод потенциаловРешение транспортной задачи методом потенциаловРешение транспортной задачи в
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ В СРЕДЕ MAPLEВыполнила: ученица 11М класса Владимирова О.М.Руководители: К.Ф.-М.Н., СодержаниеФормулировка транспортной задачиМатематическая модель транспортной задачиНеобходимое и достаточное условия разрешимости транспортной задачиОпорное Формулировка транспортной задачи Формулировка транспортной задачиА=(а1, а2, ..., аm)В=(b1, b2, ..., bn) Математическая модель транспортной задачи Математическая модель транспортной задачи Математическая модель транспортной задачиZ (X) = 3x11 + 5x12 + 7x13 + Необходимое и достаточное условия разрешимости транспортной задачи  Теорема. Для того чтобы Опорное решение транспортной задачи. Циклы   Теорема (о взаимосвязи линейной зависимости Построение начального опорного решения методом минимальной стоимости  Теорема. Решение транспортной задачи, Построение начального опорного решения методом минимальной стоимостиЧисло занятых клеток таблицы равно N =m +n –1=3+2–1=4. Переход от одного опорного решения к другому  Теорема ( о существовании Переход от одного опорного решения к другому Метод потенциалов Теорема (признак оптимальности опорного решения). Если допустимое решение X = Решение транспортной задачи методом потенциалов Решение транспортной задачи методом потенциаловZ (Х1) = 40*6+110*4+20*12+70*2 = 1060 Решение транспортной задачи методом потенциаловΔ12 = u1 +v2 –c12 = 0–4–10 = Решение транспортной задачи методом потенциалов Решение транспортной задачи методом потенциалов Решение транспортной задачи методом потенциаловZ (Х2) = 60 *6+90 *4+70 *2+20 *8 = 1020 Решение транспортной задачи в среде Maplestandardize – приведение заданной системы уравнений или Решение транспортной задачи в среде Maple  Для решения транспортной задачи в Решение транспортной задачи в среде Maplewith(simplex):standardize({x11+x12+x13=150,x21+x22+x23=90,x11+x21=60,x12+x22=70,x13+x23=110});Conversions → Make into List.[-x11-x21 with(simplex):minimize(6*x11+10*x12+4*x13+12*x21+2*x22+8*x23,{-x11-x21 Огромное  спасибо!!!
Слайды презентации

Слайд 2 Содержание
Формулировка транспортной задачи
Математическая модель транспортной задачи
Необходимое и достаточное

СодержаниеФормулировка транспортной задачиМатематическая модель транспортной задачиНеобходимое и достаточное условия разрешимости транспортной

условия разрешимости транспортной задачи
Опорное решение транспортной задачи. Циклы
Построение начального

опорного решения методом минимальной стоимости
Переход от одного опорного решения к другому
Метод потенциалов
Решение транспортной задачи методом потенциалов
Решение транспортной задачи в среде Maple

Слайд 3 Формулировка транспортной задачи

Формулировка транспортной задачи

Слайд 4 Формулировка транспортной задачи
А=(а1, а2, ..., аm)
В=(b1, b2, ...,

Формулировка транспортной задачиА=(а1, а2, ..., аm)В=(b1, b2, ..., bn)

Слайд 5 Математическая модель транспортной задачи

Математическая модель транспортной задачи

Слайд 6 Математическая модель транспортной задачи

Математическая модель транспортной задачи

Слайд 7 Математическая модель транспортной задачи
Z (X) = 3x11 +

Математическая модель транспортной задачиZ (X) = 3x11 + 5x12 + 7x13

5x12 + 7x13 + 4x21 + 6x22 + 10x23


Слайд 8 Необходимое и достаточное условия разрешимости транспортной задачи

Необходимое и достаточное условия разрешимости транспортной задачи Теорема. Для того чтобы

Теорема. Для того чтобы транспортная задача линейного программирования имела

решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запасам потребителей:

т.е. задача должна быть с правильным балансом.
Ранг системы векторов-условий транспортной задачи равен N =m +n –1.


Слайд 9 Опорное решение транспортной задачи. Циклы
Теорема

Опорное решение транспортной задачи. Циклы  Теорема (о взаимосвязи линейной зависимости

(о взаимосвязи линейной зависимости векторов-условий и возможности образования цикла).

Для того, чтобы система векторов-условий транспортной задачи была линейно зависимой, необходимо и достаточно, чтобы из соответствующих клеток таблицы можно было выделить часть, которая образует цикл.
Следствие. Допустимое решение транспортной задачи X = (xij), i =1, 2, ..., m, j =1, 2, ..., n является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

Слайд 10 Построение начального опорного решения методом минимальной стоимости

Построение начального опорного решения методом минимальной стоимости Теорема. Решение транспортной задачи,

Теорема. Решение транспортной задачи, построенное методом минимальной стоимости, является

опорным.

Слайд 11 Построение начального опорного решения методом минимальной стоимости
Число занятых

Построение начального опорного решения методом минимальной стоимостиЧисло занятых клеток таблицы равно N =m +n –1=3+2–1=4.

клеток таблицы равно N =m +n –1=3+2–1=4.


Слайд 12 Переход от одного опорного решения к другому

Переход от одного опорного решения к другому Теорема ( о существовании

Теорема ( о существовании и единственности цикла). Если таблица

транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением.
Цикл называется означенным, если его угловые клетки пронумерованы по порядку и нечетным клеткам приписан знак «+», а четным знак «–».

Слайд 13 Переход от одного опорного решения к другому

Переход от одного опорного решения к другому

Слайд 14 Метод потенциалов
Теорема (признак оптимальности опорного решения). Если

Метод потенциалов Теорема (признак оптимальности опорного решения). Если допустимое решение X

допустимое решение X = (xij ), i = 1,

2, ..., m, j = 1, 2, ..., n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков ui, i = 1, 2, …, m и потребителей vj, j = 1, 2, …, n, удовлетворяющие следующим условиям:
ui + vj = cij при xij > 0,
ui + vj ≤cij при xij = 0.
Δij = ui +vj –cij при xij =0

Опорное решение является оптимальным, если для всех векторов-условий (клеток таблицы) оценки неположительные.


Слайд 15 Решение транспортной задачи методом потенциалов

Решение транспортной задачи методом потенциалов

Слайд 16 Решение транспортной задачи методом потенциалов
Z (Х1) = 40*6+110*4+20*12+70*2

Решение транспортной задачи методом потенциаловZ (Х1) = 40*6+110*4+20*12+70*2 = 1060

= 1060


Слайд 17 Решение транспортной задачи методом потенциалов
Δ12 = u1 +v2

Решение транспортной задачи методом потенциаловΔ12 = u1 +v2 –c12 = 0–4–10

–c12 = 0–4–10 = –14
Δ23 = u2 +v3 –c23

= 6+4–8 = 2.

Слайд 18 Решение транспортной задачи методом потенциалов

Решение транспортной задачи методом потенциалов

Слайд 19 Решение транспортной задачи методом потенциалов

Решение транспортной задачи методом потенциалов

Слайд 20 Решение транспортной задачи методом потенциалов
Z (Х2) = 60

Решение транспортной задачи методом потенциаловZ (Х2) = 60 *6+90 *4+70 *2+20 *8 = 1020

*6+90 *4+70 *2+20 *8 = 1020


Слайд 21 Решение транспортной задачи в среде Maple
standardize – приведение

Решение транспортной задачи в среде Maplestandardize – приведение заданной системы уравнений

заданной системы уравнений или неравенств к стандартной форме неравенств

типа «меньше или равно».
minimize - вычисление минимума функции;
simplify (expr, n1, n2, …) – возвращает упрощенное выражение expr с учетом параметров с именами n1, n2, … (в том числе заданных списком или множеством);

Слайд 22 Решение транспортной задачи в среде Maple
Для

Решение транспортной задачи в среде Maple Для решения транспортной задачи в

решения транспортной задачи в программе Maple 7 имена ячеек

должны быть указаны в виде х11, х12 и т.д.

Слайд 23 Решение транспортной задачи в среде Maple
with(simplex):standardize({x11+x12+x13=150,x21+x22+x23=90,x11+x21=60,x12+x22=70,x13+x23=110});
Conversions → Make

Решение транспортной задачи в среде Maplewith(simplex):standardize({x11+x12+x13=150,x21+x22+x23=90,x11+x21=60,x12+x22=70,x13+x23=110});Conversions → Make into List.[-x11-x21

into List.
[-x11-x21

x12+x22<=70,-x12-x22<=-70];

Слайд 24 with(simplex):minimize(6*x11+10*x12+4*x13+12*x21+2*x22+8*x23,{-x11-x21

with(simplex):minimize(6*x11+10*x12+4*x13+12*x21+2*x22+8*x23,{-x11-x21

x12+x22

[x13=90, x22=70, x23=20, x11=60, x12=0, x21=0]);

  • Имя файла: reshenie-transportnoy-zadachi-v-srede-maple.pptx
  • Количество просмотров: 98
  • Количество скачиваний: 0