Методы оптимальных решений в линейном программировании

Нажмите для полного просмотра!

Методы оптимальных решений в линейном программировании, слайд №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

Методы оптимальных решений в линейном программировании, слайд №33

Методы оптимальных решений в линейном программировании, слайд №34

Методы оптимальных решений в линейном программировании, слайд №35

Методы оптимальных решений в линейном программировании, слайд №36

Методы оптимальных решений в линейном программировании, слайд №37

Методы оптимальных решений в линейном программировании, слайд №38

Методы оптимальных решений в линейном программировании, слайд №39

Методы оптимальных решений в линейном программировании, слайд №40

Методы оптимальных решений в линейном программировании, слайд №41

Методы оптимальных решений в линейном программировании, слайд №42

Методы оптимальных решений в линейном программировании, слайд №43

Методы оптимальных решений в линейном программировании, слайд №44

Методы оптимальных решений в линейном программировании, слайд №45

Методы оптимальных решений в линейном программировании, слайд №46

Методы оптимальных решений в линейном программировании, слайд №47

Методы оптимальных решений в линейном программировании, слайд №48

Методы оптимальных решений в линейном программировании, слайд №49

Методы оптимальных решений в линейном программировании, слайд №50

Методы оптимальных решений в линейном программировании, слайд №51

Методы оптимальных решений в линейном программировании, слайд №52

Методы оптимальных решений в линейном программировании, слайд №53

Методы оптимальных решений в линейном программировании, слайд №54

Методы оптимальных решений в линейном программировании, слайд №55

Методы оптимальных решений в линейном программировании, слайд №56

Методы оптимальных решений в линейном программировании, слайд №57

Методы оптимальных решений в линейном программировании, слайд №58

Методы оптимальных решений в линейном программировании, слайд №59

Методы оптимальных решений в линейном программировании, слайд №60

Методы оптимальных решений в линейном программировании, слайд №61

Методы оптимальных решений в линейном программировании, слайд №62

Методы оптимальных решений в линейном программировании, слайд №63

Методы оптимальных решений в линейном программировании, слайд №64

Методы оптимальных решений в линейном программировании, слайд №65

Методы оптимальных решений в линейном программировании, слайд №66

Методы оптимальных решений в линейном программировании, слайд №67

Методы оптимальных решений в линейном программировании, слайд №68

Методы оптимальных решений в линейном программировании, слайд №69

Методы оптимальных решений в линейном программировании, слайд №70

Методы оптимальных решений в линейном программировании, слайд №71

Методы оптимальных решений в линейном программировании, слайд №72

Методы оптимальных решений в линейном программировании, слайд №73

Методы оптимальных решений в линейном программировании, слайд №74

Методы оптимальных решений в линейном программировании, слайд №75

Методы оптимальных решений в линейном программировании, слайд №76

Методы оптимальных решений в линейном программировании, слайд №77

Методы оптимальных решений в линейном программировании, слайд №78

Методы оптимальных решений в линейном программировании, слайд №79

Методы оптимальных решений в линейном программировании, слайд №80

Методы оптимальных решений в линейном программировании, слайд №81

Методы оптимальных решений в линейном программировании, слайд №82

Методы оптимальных решений в линейном программировании, слайд №83

Методы оптимальных решений в линейном программировании, слайд №84

Методы оптимальных решений в линейном программировании, слайд №85

Методы оптимальных решений в линейном программировании, слайд №86

Методы оптимальных решений в линейном программировании, слайд №87

Методы оптимальных решений в линейном программировании, слайд №88

Методы оптимальных решений в линейном программировании, слайд №89

Методы оптимальных решений в линейном программировании, слайд №90

Методы оптимальных решений в линейном программировании, слайд №91

Методы оптимальных решений в линейном программировании, слайд №92

Методы оптимальных решений в линейном программировании, слайд №93

Методы оптимальных решений в линейном программировании, слайд №94

Методы оптимальных решений в линейном программировании, слайд №95

Методы оптимальных решений в линейном программировании, слайд №96

Методы оптимальных решений в линейном программировании, слайд №97

Методы оптимальных решений в линейном программировании, слайд №98

Методы оптимальных решений в линейном программировании, слайд №99

Методы оптимальных решений в линейном программировании, слайд №100

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Методы оптимальных решений в линейном программировании. Доклад-сообщение содержит 100 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Слайд 2

Описание слайда:

ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Общая задача математического программирования: найти экстремум целевой функции F(X) =f (х1, х2, ..., хп) → max (min) (1.1) при системе ограничений

Слайд 3

Описание слайда:

Если целевая функция (1.1) и система ограничений (1.2) линейны, то задача математического программирования называется задачей линейного программирования. Если целевая функция (1.1) и система ограничений (1.2) линейны, то задача математического программирования называется задачей линейного программирования. Математическая модель задачи на нахождения максимального значения целевой функции записывается в виде:

Слайд 4

Описание слайда:

F(X) = с1 х1 + с2 х2 + ... + сп хп→max, F(X) = с1 х1 + с2 х2 + ... + сп хп→max,

Слайд 5

Описание слайда:

В задаче на нахождение минимального значения целевой функции математическая модель её запишется в виде F(X) = с1 х1 + с2 х2 + ... В задаче на нахождение минимального значения целевой функции математическая модель её запишется в виде F(X) = с1 х1 + с2 х2 + ... + сп хп→min,

Слайд 6

Описание слайда:

РАССМОТРИМ ВАРИАНТЫ СОСТАВЛЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ДЛЯ СЛЕДУЮЩИХ ЗАДАЧ Задача 1. (Планирование производства.) Некоторое предприятие выпускает три типа продукции П1,П2,П3 двумя технологическими способами S1 и S2. Количество продукции j-гo вида (j = 1,2,3), произведенного i -м способом (i = 1,2) за единицу времени задано таблицей

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Необходимо так организовывать производство, чтобы получить наибольшую прибыль при реализации продукции по указанной стоимости. Необходимо так организовывать производство, чтобы получить наибольшую прибыль при реализации продукции по указанной стоимости.

Слайд 9

Описание слайда:

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ Обозначим через хi j — время, затраченное на изготовление продукции Пj (j = 1,2,3) i -м способом. Тогда план производства будет иметь вид:

Слайд 10

Описание слайда:

При этом продукции 1-го вида будет выпущено 20х11+ 30х21 , 2-го вида 25х12+20х22 , 3-го вида 30х13+ 15х23. При этом продукции 1-го вида будет выпущено 20х11+ 30х21 , 2-го вида 25х12+20х22 , 3-го вида 30х13+ 15х23. Стоимость всей продукции (обозначим ее за F) равна 5(20х11+ 30х21)+3(25х12+20х22)+6(30х13+ 15х23) и она должна быть максимальной. Но при этом есть ограничения по времени: х11+ х12 + х13 ≤10, х21+ х22 + х23 ≤8 и очевидно, все хi j ≥ 0.

Слайд 11

Описание слайда:

ОКОНЧАТЕЛЬНО ПОЛУЧАЕМ МАТЕМАТИЧЕСКУЮ МОДЕЛЬ ЗАДАЧИ F=5(20х11+ 30х21)+3(25х12+20х22)+6(30х13+ 15х23) → max,

Слайд 12

Описание слайда:

ЗАДАЧА 2. (ЗАДАЧА О СМЕСИ.) Известно, что при правильном питании человек должен получать в день не менее 20 единиц витамина А, не менее 15 единиц витамина В. Содержание этих витаминов в одной единице каждого из продуктов П1, П2, П3 задано таблице. Составить наиболее дешевый рацион питания. Все данные занесены в таблицу.

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Математическая модель задачи Математическая модель задачи Пусть хi — количество продукта Пi, потребляемого в день (i=1,2,3), тогда стоимость всех продуктов (обозначим F) будет равна F=25х1 +30x2 + +20х3. При этом количество витамина А равно 4x1 + 5х2 + 2х3 , витамина В — 5x1 + 2х2 + 6х3, получаем математическую модель:

Слайд 15

Описание слайда:

Слайд 16

Описание слайда:

ЗАДАЧА 3. (О РАСКРОЕ МАТЕРИАЛА.)

Слайд 17

Описание слайда:

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ РАССМОТРИМ ВОЗМОЖНЫЕ ВАРИАНТЫ РАСПИЛИВАНИЯ ДОСОК.

Слайд 18

Описание слайда:

Обозначим через хi— количество досок, распиленных i-м способом, тогда заготовок по 2 м получится 3x1+ 2х2 + 2х3 + х4, по 2,5 м — x2 + 2x4 + х5; по 3 м — х 3 + x5 + 2x6. Обозначим через к — число полученных изделий, тогда Обозначим через хi— количество досок, распиленных i-м способом, тогда заготовок по 2 м получится 3x1+ 2х2 + 2х3 + х4, по 2,5 м — x2 + 2x4 + х5; по 3 м — х 3 + x5 + 2x6. Обозначим через к — число полученных изделий, тогда

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Слайд 21

Описание слайда:

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Слайд 22

Описание слайда:

Алгоритм решения ЗЛП с двумя переменными графическим методом: Алгоритм решения ЗЛП с двумя переменными графическим методом: Строится область допустимых решений. Строится вектор = (с1, с2) с точкой приложения в начале координат. Перпендикулярно вектору проводится одна из линий уровня, например линия уровня, соответствующая уравнению с1х1 + с2х2 = 0. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находиться максимум или минимум функции.

Слайд 23

Описание слайда:

Пример 1. Решить задачу линейного программирования графическим методом: F(X)=2x1+4x2→ max, Пример 1. Решить задачу линейного программирования графическим методом: F(X)=2x1+4x2→ max,

Слайд 24

Описание слайда:

Решение. Изобразим на плоскости систему координат Ох1х2 и построим граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе). Область допустимых решений определяется многоугольником OABCD (рис.). Решение. Изобразим на плоскости систему координат Ох1х2 и построим граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе). Область допустимых решений определяется многоугольником OABCD (рис.).

Слайд 25

Описание слайда:

Перпендикулярно вектору построим одну из линий уровня (на рис. она проходит через начало координат). Так как задача на максимум, то перемещаем линию Перпендикулярно вектору построим одну из линий уровня (на рис. она проходит через начало координат). Так как задача на максимум, то перемещаем линию уровня в направлении вектора до опорной прямой.

Слайд 26

Описание слайда:

Слайд 27

Описание слайда:

В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L1 и L2, т.е. через точку В = L1∩L2. Для определения координат точки В решаем систему уравнений В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L1 и L2, т.е. через точку В = L1∩L2. Для определения координат точки В решаем систему уравнений

Слайд 28

Описание слайда:

Пример 2. Найти минимум функции F(X)=2x1+x2→ min при ограничениях Пример 2. Найти минимум функции F(X)=2x1+x2→ min при ограничениях

Слайд 29

Описание слайда:

Слайд 30

Описание слайда:

ДВОЙСТВЕННАЯ ЗАДАЧА В теории двойственности используются четыре пары двойственных задач (приведем их в матричной форме записи):

Слайд 31

Описание слайда:

Слайд 32

Описание слайда:

Слайд 33

Описание слайда:

Слайд 34

Описание слайда:

Слайд 35

Описание слайда:

Решение. Умножим первое ограничение-неравенство на -1. Задача примет вид исходной задачи симметричной пары двойственных задач: Решение. Умножим первое ограничение-неравенство на -1. Задача примет вид исходной задачи симметричной пары двойственных задач: F(X) = х1 + 4х2 +3 х3→min,

Слайд 36

Описание слайда:

Слайд 37

Описание слайда:

Первая теорема двойственности Первая теорема двойственности Теорема. Если одна из пары двойственных задач имеет оптимальное решение, то и двойственная к ней имеет оптимальное решение; причем значения целевых функций задач на своих оптимальных решениях совпадают. Если же одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.

Слайд 38

Описание слайда:

Слайд 39

Описание слайда:

Слайд 40

Описание слайда:

Слайд 41

Описание слайда:

Слайд 42

Описание слайда:

Слайд 43

Описание слайда:

Слайд 44

Описание слайда:

Слайд 45

Описание слайда:

Слайд 46

Описание слайда:

Слайд 47

Описание слайда:

Слайд 48

Описание слайда:

ТРАНСПОРТНАЯ ЗАДАЧА Формулировка транспортной задачи Однородный груз сосредоточен у т поставщиков в объемах a1, a2,..., ат. Данный груз необходимо доставить п потребителям в объемах b1, b2, ..., bn. Известны сij, i= 1, 2, ..., m, j = 1, 2, ..., п — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи обычно записываются в таблице:

Слайд 49

Описание слайда:

Слайд 50

Описание слайда:

Слайд 51

Описание слайда:

Слайд 52

Описание слайда:

ОПОРНОЕ РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

Слайд 53

Описание слайда:

Свойство системы ограничений транспортной задачи: Свойство системы ограничений транспортной задачи: ранг системы векторов ― условий транспортной задачи равен N=т + п — 1.

Слайд 54

Описание слайда:

Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные — незанятыми или свободными. Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные — незанятыми или свободными.

Слайд 55

Описание слайда:

Слайд 56

Описание слайда:

Слайд 57

Описание слайда:

МЕТОДЫ ПОСТРОЕНИЯ НАЧАЛЬНОГО ОПОРНОГО РЕШЕНИЯ МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА Существует ряд методов построения начального опорного решения, наиболее простым из которых является метод северо-западного угла. В данном методе запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика. Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель.

Слайд 58

Описание слайда:

Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно т + п — 1 и векторы-условия, соответствующие этим клеткам, линейно независимы. Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно т + п — 1 и векторы-условия, соответствующие этим клеткам, линейно независимы. Теорема. Решение транспортной задачи, построенное методом северо-западного угла, является опорным.

Слайд 59

Описание слайда:

Слайд 60

Описание слайда:

Слайд 61

Описание слайда:

ПЕРЕХОД ОТ ОДНОГО ОПОРНОГО РЕШЕНИЯ К ДРУГОМУ В транспортной задаче переход от одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок. Перевозка загружается в выбранную свободную клетку, и освобождается одна из занятых клеток, получается новое опорное решение.

Слайд 62

Описание слайда:

Теорема (о существовании и единственности цикла). Теорема (о существовании и единственности цикла). Если таблица транспортной задачи содержит опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением.

Слайд 63

Описание слайда:

Слайд 64

Описание слайда:

Сдвигом по циклу на величину θ называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на θ и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «—», на θ. Сдвигом по циклу на величину θ называется увеличение объемов перевозок во всех нечетных клетках цикла, отмеченных знаком «+», на θ и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «—», на θ. Теорема. Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину θ = получится опорное решение.

Слайд 65

Описание слайда:

МЕТОД ПОТЕНЦИАЛОВ

Слайд 66

Описание слайда:

Слайд 67

Описание слайда:

Числа Δij называются оценками свободных клеток таблицы или векторов ― условий транспортной задачи, Числа Δij называются оценками свободных клеток таблицы или векторов ― условий транспортной задачи,

Слайд 68

Описание слайда:

Слайд 69

Описание слайда:

ОСОБЕННОСТИ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ С НЕПРАВИЛЬНЫМ БАЛАНСОМ

Слайд 70

Описание слайда:

Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами bn+1, равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного потребителя с запросами bn+1, равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза

Слайд 71

Описание слайда:

Слайд 72

Описание слайда:

Следовательно, чтобы в этом случае задача имела решение, необходимо ввести фиктивного поставщика с запасами ат+1, равными разно суммарным запросам потребителей и запасам поставщиков, и нулевыми стоимостями перевозок единиц груза Следовательно, чтобы в этом случае задача имела решение, необходимо ввести фиктивного поставщика с запасами ат+1, равными разно суммарным запросам потребителей и запасам поставщиков, и нулевыми стоимостями перевозок единиц груза

Слайд 73

Описание слайда:

Алгоритм решения транспортной задачи методом потенциалов Алгоритм решения транспортной задачи методом потенциалов Проверяют выполнение необходимого и достаточного условия разрешимости задачи. Если задача имеет неправильный баланс, то вводят фиктивного поставщика или потребителя с недостающими запасами или запросами и нулевыми стоимостями перевозок. 2. Строят начальное опорное решение и проверяют правильность его построения, для чего подсчитывают количество занятых клеток (их должно быть т+п—1) и убеждаются в линейной независимости векторов-условий.

Слайд 74

Описание слайда:

Слайд 75

Описание слайда:

Слайд 76

Описание слайда:

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

Слайд 77

Описание слайда:

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

Слайд 78

Описание слайда:

Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину θ=

Слайд 79

Описание слайда:

Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным т+п—1. Возвращаются к пункту 3. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным т+п—1. Возвращаются к пункту 3.

Слайд 80

Описание слайда:

ПРИМЕР. РЕШИТЬ ТРАНСПОРТНУЮ ЗАДАЧУ, ДАННЫЕ ПРИВЕДЕНЫ В ТАБЛИЦЕ

Слайд 81

Описание слайда:

Слайд 82

Описание слайда:

2. Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей С: 2. Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей С:

Слайд 83

Описание слайда:

Слайд 84

Описание слайда:

3. Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равна стоимости 3. Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равна стоимости ( ). Записываем систему уравнений для нахождения потенциалов:

Слайд 85

Описание слайда:

Слайд 86

Описание слайда:

Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть и2 = 0. Остальные потенциалы находятся однозначно: Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть и2 = 0. Остальные потенциалы находятся однозначно:

Слайд 87

Описание слайда:

Слайд 88

Описание слайда:

Слайд 89

Описание слайда:

Слайд 90

Описание слайда:

Слайд 91

Описание слайда:

Слайд 92

Описание слайда:

Положительные оценки записываем в левые нижние углы соответствующих клеток таблицы, вместо отрицательных ставим знак «—». Начальное опорное решение не является оптимальным, так как имеются положительные оценки. Положительные оценки записываем в левые нижние углы соответствующих клеток таблицы, вместо отрицательных ставим знак «—». Начальное опорное решение не является оптимальным, так как имеются положительные оценки.

Слайд 93

Описание слайда:

В данном случае минимум перевозок в клетках, отмеченных знаком «-», достигался сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно т + п — 1 = 7, в клетки с номерами (1, 1) и (2, 3) поставлены нулевые базисные перевозки. Следует освобождать клетку с большей стоимостью перевозки, т.е. клетку (3, 4). Вычисляем значение целевой функции на втором опорном решении: В данном случае минимум перевозок в клетках, отмеченных знаком «-», достигался сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно т + п — 1 = 7, в клетки с номерами (1, 1) и (2, 3) поставлены нулевые базисные перевозки. Следует освобождать клетку с большей стоимостью перевозки, т.е. клетку (3, 4). Вычисляем значение целевой функции на втором опорном решении: F(X) = 0·1 + 100·1 + 100·2 + 100·3 + 0·4 + 300·7 + 200·0 = 2700.

Слайд 94

Описание слайда:

6. Проверяем второе опорное решение Х2 на оптимальность. Находим, потенциалы и оценки. Решение не является оптимальным, так как имеются положительные оценки Δ31=2, Δ32=2, Δ42=1 и Δ43=2. Наибольшая из них равна 2 одновременно для трех клеток (3, 1), (3, 2) и (4, 3). В одну из них, пусть в клетку (3, 2), ставим знак «+». Для этой клетки строим цикл и находим величину груза по циклу: θ=min{100,300}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем третье опорное решение Х3. 6. Проверяем второе опорное решение Х2 на оптимальность. Находим, потенциалы и оценки. Решение не является оптимальным, так как имеются положительные оценки Δ31=2, Δ32=2, Δ42=1 и Δ43=2. Наибольшая из них равна 2 одновременно для трех клеток (3, 1), (3, 2) и (4, 3). В одну из них, пусть в клетку (3, 2), ставим знак «+». Для этой клетки строим цикл и находим величину груза по циклу: θ=min{100,300}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем третье опорное решение Х3.

Слайд 95

Описание слайда:

Слайд 96

Описание слайда:

Вычисляем значение целевой функции на третьем опорном решении: Вычисляем значение целевой функции на третьем опорном решении: F(X3)= 0·1 + 100·1 + 100·2 + 100·4 + 100·4 + 200·7 + 200·0 =2500. 7. Решение не является оптимальным, так как имеются положительные оценки Δ31=2 и Δ43=2. Ставим знак «+» пусть в клетку (3, 1), Для этой клетки строим цикл и находим величину груза для перераспределения по циклу: θ=min{100,200}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем четвертое опорное решение Х4:

Слайд 97

Описание слайда:

Слайд 98

Описание слайда:

Вычисляем значение целевой функции на четвертом опорном решении: F(Х4) = 0·l + 100·1 +200·4+ 100·3 + 100·4+ 100·7 + 200·0 =2300. Вычисляем значение целевой функции на четвертом опорном решении: F(Х4) = 0·l + 100·1 +200·4+ 100·3 + 100·4+ 100·7 + 200·0 =2300. 8. Проверяем решение Х4 на оптимальность. Находим потенциалы и оценки. Они приведены в таблице. Положительными являются оценки Δ13=2, Δ42=1 и Δ43=4. Для клетки (4, 3), которой соответствует наибольшая оценка, строим цикл и находим величину груза для перераспределения по циклу: θ=min{200,0,100}=0. Осуществляем сдвиг по циклу на величину θ=0. Получаем пятое опорное решение Х5:

Слайд 99

Описание слайда:

Слайд 100

Описание слайда:

Решение Х5 является оптимальным, так как все оценки отрицательные. Значение целевой функции F(X5) = F(X4) = 2300. Решение Х5 является оптимальным, так как все оценки отрицательные. Значение целевой функции F(X5) = F(X4) = 2300. Ответ: min F(Х)=2300 при