- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Методы оптимальных решений в линейном программировании презентация
Содержание
- 1. Методы оптимальных решений в линейном программировании
- 2. ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Общая задача
- 3. Если целевая функция (1.1) и система ограничений
- 4. F(X) = с1 х1 + с2 х2 + ... + сп хп→max,
- 5. В задаче на нахождение минимального значения целевой
- 6. РАССМОТРИМ ВАРИАНТЫ СОСТАВЛЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ДЛЯ СЛЕДУЮЩИХ
- 8. Необходимо так организовывать производство, чтобы получить наибольшую прибыль при реализации продукции по указанной стоимости.
- 9. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ Обозначим через хi j
- 10. При этом продукции 1-го вида будет выпущено
- 11. ОКОНЧАТЕЛЬНО ПОЛУЧАЕМ МАТЕМАТИЧЕСКУЮ МОДЕЛЬ ЗАДАЧИ F=5(20х11+ 30х21)+3(25х12+20х22)+6(30х13+ 15х23) → max,
- 12. ЗАДАЧА 2. (ЗАДАЧА О СМЕСИ.) Известно,
- 14. Математическая модель задачи Пусть хi
- 15. F=25х1 +30x2 +20х3 → min,
- 16. ЗАДАЧА 3. (О РАСКРОЕ МАТЕРИАЛА.) Для
- 17. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ЗАДАЧИ РАССМОТРИМ ВОЗМОЖНЫЕ ВАРИАНТЫ РАСПИЛИВАНИЯ ДОСОК.
- 18. Обозначим через хi— количество досок, распиленных i-м
- 19. х 3 + x5 + 2x6=к.
- 20. Окончательно получим математическую модель к=х 3 +
- 21. ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Задача
- 22. Алгоритм решения ЗЛП с двумя переменными графическим
- 23. Пример 1. Решить задачу линейного программирования графическим методом: F(X)=2x1+4x2→ max,
- 24. Решение. Изобразим на плоскости систему координат Ох1х2
- 25. Перпендикулярно вектору построим
- 27. В данном случае опорной прямой является прямая,
- 28. Пример 2. Найти минимум функции F(X)=2x1+x2→ min при ограничениях
- 29. А (6/7; 25/7) и Fmin = 37/7.
- 30. ДВОЙСТВЕННАЯ ЗАДАЧА В теории двойственности используются четыре
- 31. Исходная задача
- 32. Несимметричные пары 1. F(X)=CX→max,
- 33. Здесь С=(с1, с2,…, сn), Y= (у1, у2,… …,ут),
- 34. Пример 1. Составить задачу, двойственную к данной
- 35. Решение. Умножим первое ограничение-неравенство на -1. Задача
- 36. Окончательно двойственная задача имеет вид Z(Y) = -10у1 + 6у2 + 12у3→ max,
- 37. Первая теорема двойственности Теорема. Если одна
- 38. Вторая теорема двойственности Пусть имеется симметричная пара двойственных задач
- 39. Теорема. Для того чтобы допустимые решения Х=
- 40. Пример 1. Для данной задачи составить двойственную,
- 41. Решение. Составим двойственную задачу: Z(Y) = 2у1 + 3у2→ max,
- 42. Решим эту задачу графическим методом. На
- 44. 2у1=6 у1*=3, у2*=4. Y *=(3,4). Z(Y *)=2·3+3·4=18.
- 45. Подставим оптимальное решение Y *= (3, 4)
- 46. По второй теореме двойственности следует, что соответствующие
- 47. Отсюда находим х3*= 1, х4* = 2.
- 48. ТРАНСПОРТНАЯ ЗАДАЧА Формулировка транспортной задачи Однородный груз
- 50. Исходные данные задачи могут быть представлены также
- 52. ОПОРНОЕ РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ
- 53. Свойство системы ограничений транспортной задачи: ранг
- 54. Клетки таблицы транспортной задачи, в которых находятся
- 57. МЕТОДЫ ПОСТРОЕНИЯ НАЧАЛЬНОГО ОПОРНОГО РЕШЕНИЯ МЕТОД
- 58. Во избежание ошибок после построения начального опорного
- 61. ПЕРЕХОД ОТ ОДНОГО ОПОРНОГО РЕШЕНИЯ К ДРУГОМУ
- 62. Теорема (о существовании и единственности цикла).
- 64. Сдвигом по циклу на величину θ называется
- 65. МЕТОД ПОТЕНЦИАЛОВ
- 67. Числа Δij называются оценками свободных клеток таблицы или векторов ― условий транспортной задачи,
- 69. ОСОБЕННОСТИ РЕШЕНИЯ ТРАНСПОРТНЫХ ЗАДАЧ С НЕПРАВИЛЬНЫМ БАЛАНСОМ
- 70. Следовательно, чтобы задача в рассматриваемом случае имела
- 72. Следовательно, чтобы в этом случае задача имела
- 73. Алгоритм решения транспортной задачи методом потенциалов
- 74. 3.Строят систему потенциалов, соответствующих опорному решению. Для
- 75. при если известен потенциал .
- 76. 4. Проверяют, выполняется ли условие оптимальности для
- 77. 5. Переходят к новому опорному решению, на
- 78. Строят цикл, включающий в свой состав данную
- 79. Если минимум достигается в нескольких клетках, то
- 80. ПРИМЕР. РЕШИТЬ ТРАНСПОРТНУЮ ЗАДАЧУ, ДАННЫЕ ПРИВЕДЕНЫ В ТАБЛИЦЕ
- 81. Решение. 1. Проверяем выполнение необходимого и достаточного
- 82. 2. Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей С:
- 83. Полученное решение Х1 имеет т + п
- 84. 3. Для проверки оптимальности опорного решения необходимо
- 86. Система состоит из семи уравнений и имеет
- 88. 4. Проверяем опорное решение Х1 на оптимальность.
- 90. 5. Переходим к новому опорному решению. Находим
- 91. Х1
- 92. Положительные оценки записываем в левые нижние углы
- 93. В данном случае минимум перевозок в клетках,
- 94. 6. Проверяем второе опорное решение Х2 на
- 95. v1=1
- 96. Вычисляем значение целевой функции на третьем опорном
- 97. v1=1
- 98. Вычисляем значение целевой функции на четвертом опорном
- 99. Х5
- 100. Решение Х5 является оптимальным, так как все
ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Общая задача математического программирования: найти экстремум целевой функции F(X) =f (х1, х2, ..., хп) → max (min)
Слайд 2ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Общая задача математического программирования: найти экстремум целевой
функции F(X) =f (х1, х2, ..., хп) → max (min) (1.1)
при системе ограничений
при системе ограничений
(1.2)
Слайд 3Если целевая функция (1.1) и система ограничений (1.2) линейны, то задача
математического программирования называется задачей линейного программирования.
Математическая модель задачи на нахождения максимального значения целевой функции записывается в виде:
Математическая модель задачи на нахождения максимального значения целевой функции записывается в виде:
Слайд 5В задаче на нахождение минимального значения целевой функции математическая модель её
запишется в виде F(X) = с1 х1 + с2 х2 + ...
+ сп хп→min,
+ сп хп→min,
Слайд 6РАССМОТРИМ ВАРИАНТЫ СОСТАВЛЕНИЯ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ДЛЯ СЛЕДУЮЩИХ ЗАДАЧ
Задача 1. (Планирование производства.)
Некоторое
предприятие выпускает три типа продукции П1,П2,П3 двумя технологическими способами S1 и S2. Количество продукции j-гo вида (j = 1,2,3), произведенного i -м способом (i = 1,2) за единицу времени задано таблицей
Слайд 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.
Стоимость всей продукции (обозначим ее за 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.
Стоимость всей продукции (обозначим ее за 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 задано таблице. Составить наиболее дешевый рацион питания.
Все данные занесены в таблицу.
Все данные занесены в таблицу.
Слайд 14Математическая модель задачи
Пусть хi — количество продукта Пi, потребляемого в день
(i=1,2,3), тогда стоимость всех продуктов (обозначим F) будет равна F=25х1 +30x2 + +20х3. При этом количество витамина А равно 4x1 + 5х2 + 2х3 , витамина В — 5x1 + 2х2 + 6х3, получаем математическую модель:
Слайд 16ЗАДАЧА 3. (О РАСКРОЕ МАТЕРИАЛА.)
Для изготовления некоторого изделия требуется 2
планки по 2 м, 3 — по 2,5 м и одна трехметровая. Для этого используют 100 досок по 7 м длиной. Как распилить доски, чтобы получить возможно большее число комплектов?
Слайд 18Обозначим через хi— количество досок, распиленных i-м способом, тогда заготовок по
2 м получится 3x1+ 2х2 + 2х3 + х4, по 2,5 м — x2 + 2x4 + х5; по 3 м — х 3 + x5 + 2x6. Обозначим через к — число полученных изделий, тогда
3x1+ 2х2 + 2х3 + х4 =
или 2(3x1+ 2х2 + 2х3 + х4 )=к,
x2 + 2x4 + х5 =
или 3(x2 + 2x4 + х5 )=к,
Слайд 19 х 3 + x5 + 2x6=к. Исключим к.
2(3x1+
2х2 + 2х3 + х4 )= 3(x2 + 2x4 + х5 )
или 6x1+ х2 + 4х3 -4х4 -3х5 =0,
2(3x1+ 2х2 + 2х3 + х4 )= х 3 + x5 + 2x6
или 6x1+ 4х2 + 3х3 +2х4 -х5-2х6=0.
или 6x1+ х2 + 4х3 -4х4 -3х5 =0,
2(3x1+ 2х2 + 2х3 + х4 )= х 3 + x5 + 2x6
или 6x1+ 4х2 + 3х3 +2х4 -х5-2х6=0.
Слайд 21ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задача с двумя переменными
Пусть требуется найти
максимальное значение функции F(X) = с1 х1 + с2 х2
при ограничениях
при ограничениях
Слайд 22Алгоритм решения ЗЛП с двумя переменными графическим методом:
Строится область допустимых решений.
Строится
вектор = (с1, с2) с точкой приложения в начале координат.
Перпендикулярно вектору проводится одна из линий уровня, например линия уровня, соответствующая уравнению с1х1 + с2х2 = 0.
Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находиться максимум или минимум функции.
Перпендикулярно вектору проводится одна из линий уровня, например линия уровня, соответствующая уравнению с1х1 + с2х2 = 0.
Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находиться максимум или минимум функции.
Слайд 24Решение. Изобразим на плоскости систему координат Ох1х2 и построим граничные прямые
области допустимых решений (номера прямых соответствуют их порядковому номеру в системе). Область допустимых решений определяется многоугольником OABCD (рис.).
Для линий уровня 2х1 + 4х2 = с (с = const) строим нормальный вектор
= (2, 4).
Слайд 25Перпендикулярно вектору построим одну из линий уровня
(на рис. она проходит через начало координат). Так как задача на максимум, то перемещаем линию
уровня в направлении вектора до опорной прямой.
уровня в направлении вектора до опорной прямой.
Слайд 27В данном случае опорной прямой является прямая, проходящая через точку пересечения
граничных прямых L1 и L2, т.е. через точку В = L1∩L2. Для определения координат точки В решаем систему уравнений
Получаем х1 = 3, х2 = 6. Это и будет оптимальное решение данной задачи, которому соответствует максимальное значение целевой функции
max F(X) = 2 · 3 + 4 · 6 = 30.
Слайд 30ДВОЙСТВЕННАЯ ЗАДАЧА
В теории двойственности используются четыре пары двойственных задач (приведем их
в матричной форме записи):
Слайд 31Исходная задача
Двойственная задача
Симметричные пары
1. F(X)=CX→max, Z(Y)=YA0→min
AX≤ A0 , YA≥ C,
X≥θ; Y≥θ.
2. F(X)=CX→min, Z(Y)=YA0→ max,
AX≥ A0 , YA≤ C,
X≥θ; Y≥θ.
Симметричные пары
1. F(X)=CX→max, Z(Y)=YA0→min
AX≤ A0 , YA≥ C,
X≥θ; Y≥θ.
2. F(X)=CX→min, Z(Y)=YA0→ max,
AX≥ A0 , YA≤ C,
X≥θ; Y≥θ.
Слайд 32Несимметричные пары
1. F(X)=CX→max,
Z(Y)=YA0→min
AX= A0 , YA≥ C.
X≥θ;
2. F(X)=CX→min, Z(Y)=YA0→ max,
AX=A0 , YA≤ C.
X≥θ;
AX= A0 , YA≥ C.
X≥θ;
2. F(X)=CX→min, Z(Y)=YA0→ max,
AX=A0 , YA≤ C.
X≥θ;
Слайд 35Решение. Умножим первое ограничение-неравенство на -1. Задача примет вид исходной задачи
симметричной пары двойственных задач:
F(X) = х1 + 4х2 +3 х3→min,
F(X) = х1 + 4х2 +3 х3→min,
Слайд 37Первая теорема двойственности
Теорема. Если одна из пары двойственных задач имеет оптимальное
решение, то и двойственная к ней имеет оптимальное решение; причем значения целевых функций задач на своих оптимальных решениях совпадают. Если же одна из пары двойственных задач не имеет решения ввиду неограниченности целевой функции, то другая не имеет решения ввиду несовместности системы ограничений.
Слайд 39Теорема. Для того чтобы допустимые решения Х= (х1, х2, ..., хп),
Y=(y1, y2, ..., yт) являлись оптимальными решениями пары двойственных задач, необходимо и достаточно, чтобы выполнялись следующие равенства:
Слайд 40Пример 1. Для данной задачи составить двойственную, решить ее графическим методом
и, используя вторую теорему двойственности, найти решение исходной задачи:
F(X) = -2x1 + 2х2 + 10х3 + 4х4 + 2х5→ min,
F(X) = -2x1 + 2х2 + 10х3 + 4х4 + 2х5→ min,
Слайд 42
Решим эту задачу графическим методом. На рис. изображены область допустимых решений
задачи, нормаль п = (2, 3) линий уровня, линии уровня 2у1 + 3у2 = с и оптимальное решение задачи Y* = (3, 4).
Слайд 45Подставим оптимальное решение Y *= (3, 4) в систему ограничений. Получим,
что первое, второе и пятое ограничения выполняются как строгие неравенства:
Слайд 46По второй теореме двойственности следует, что соответствующие координаты оптимального решения двойственной
задачи, т.е. исходной задачи, равны нулю: х1* = х2* = х5*=0. Учитывая это, из системы ограничений исходной задачи получим
Слайд 47Отсюда находим х3*= 1, х4* = 2. Окончательно записываем X*=(0,0,1,2,0).
Ответ: min
F(X) = 18 при X* = (0, 0, 1, 2, 0).
Слайд 48ТРАНСПОРТНАЯ ЗАДАЧА
Формулировка транспортной задачи
Однородный груз сосредоточен у т поставщиков в объемах
a1, a2,..., ат. Данный груз необходимо доставить п потребителям в объемах b1, b2, ..., bn. Известны сij, i= 1, 2, ..., m, j = 1, 2, ..., п — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.
Исходные данные транспортной задачи обычно записываются в таблице:
Исходные данные транспортной задачи обычно записываются в таблице:
Слайд 50Исходные данные задачи могут быть представлены также в виде вектора запасов
поставщиков А=(a1,a2,...,ат), вектора запросов потребителей В=(b1,b2, ..., bn) и матрицы стоимостей
Слайд 53Свойство системы ограничений транспортной задачи:
ранг системы векторов ― условий транспортной
задачи равен N=т + п — 1.
Слайд 54Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или
базисные нулевые перевозки, называются занятыми, остальные — незанятыми или свободными.
Слайд 57МЕТОДЫ ПОСТРОЕНИЯ НАЧАЛЬНОГО ОПОРНОГО РЕШЕНИЯ
МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА
Существует ряд методов построения начального
опорного решения, наиболее простым из которых является метод северо-западного угла. В данном методе запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель.
Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель.
Слайд 58Во избежание ошибок после построения начального опорного решения необходимо проверить, что
число занятых клеток равно т + п — 1 и векторы-условия, соответствующие этим клеткам, линейно независимы.
Теорема. Решение транспортной задачи, построенное методом северо-западного угла, является опорным.
Теорема. Решение транспортной задачи, построенное методом северо-западного угла, является опорным.
Слайд 61ПЕРЕХОД ОТ ОДНОГО ОПОРНОГО РЕШЕНИЯ К ДРУГОМУ
В транспортной задаче переход от
одного опорного решения к другому осуществляется с помощью цикла. Для некоторой свободной клетки таблицы строится цикл, содержащий часть клеток, занятых опорным решением. По этому циклу перераспределяются объемы перевозок. Перевозка загружается в выбранную свободную клетку, и освобождается одна из занятых клеток, получается новое опорное решение.
Слайд 62Теорема (о существовании и единственности цикла).
Если таблица транспортной задачи содержит
опорное решение, то для любой свободной клетки таблицы существует единственный цикл, содержащий эту клетку и часть клеток, занятых опорным решением.
Слайд 64Сдвигом по циклу на величину θ называется увеличение объемов перевозок во
всех нечетных клетках цикла, отмеченных знаком «+», на θ и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «—», на θ.
Теорема.
Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину θ = получится опорное решение.
Теорема.
Если таблица транспортной задачи содержит опорное решение, то при сдвиге по любому циклу, содержащему одну свободную клетку, на величину θ = получится опорное решение.
Слайд 67Числа Δij называются оценками свободных клеток таблицы или векторов ― условий
транспортной задачи,
Слайд 70Следовательно, чтобы задача в рассматриваемом случае имела решение, необходимо ввести фиктивного
потребителя с запросами bn+1, равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза
Слайд 72Следовательно, чтобы в этом случае задача имела решение, необходимо ввести фиктивного
поставщика с запасами ат+1, равными разно суммарным запросам потребителей и запасам поставщиков, и нулевыми стоимостями перевозок единиц груза
Слайд 73Алгоритм решения транспортной задачи методом потенциалов
Проверяют выполнение необходимого и достаточного условия
разрешимости задачи. Если задача имеет неправильный баланс, то вводят фиктивного поставщика или потребителя с недостающими запасами или запросами и нулевыми стоимостями перевозок.
2. Строят начальное опорное решение и проверяют правильность его построения, для чего подсчитывают количество занятых клеток (их должно быть т+п—1) и убеждаются в линейной независимости векторов-условий.
2. Строят начальное опорное решение и проверяют правильность его построения, для чего подсчитывают количество занятых клеток (их должно быть т+п—1) и убеждаются в линейной независимости векторов-условий.
Слайд 743.Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений
Для того чтобы найти частное решение системы, одному из потенциалов задают произвольно некоторое значение (чаще нуль). Остальные потенциалы однозначно определяются по формулам:
при
если известен потенциал
Слайд 764. Проверяют, выполняется ли условие оптимальности для свободных клеток таблицы. Для
этого вычисляют оценки для всех свободных клеток по формулам.
Если для всех свободных клеток < 0, то вычисляют значение целевой функции, и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, то опорное решение не является оптимальным.
Если для всех свободных клеток < 0, то вычисляют значение целевой функции, и решение задачи заканчивается, так как полученное решение является оптимальным. Если же имеется хотя бы одна клетка с положительной оценкой, то опорное решение не является оптимальным.
Слайд 775. Переходят к новому опорному решению, на котором значение целевой функции
будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка
Слайд 78Строят цикл, включающий в свой состав данную клетку и часть клеток,
занятых опорным решением. В клетках цикла расставляют поочередно знаки «+» и «-», начиная с «+» в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину
θ=
θ=
Клетка со знаком «-», в которой достигается
Слайд 79Если минимум достигается в нескольких клетках, то одна из них остается
пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным т+п—1. Возвращаются к пункту 3.
Слайд 81Решение. 1. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим
суммарные запасы поставщиков и запросы потребителей:
= 100 + 200 + 300 = 600,
= 100 + 100 + 300 + 300 = 800.
Задача с неправильным балансом. Вводим четвертого, фиктивного поставщика с запасами а4 = 800 — 600 = 200 и нулевыми стоимостями перевозки единиц груза
Слайд 822. Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей
С:
Слайд 83Полученное решение Х1 имеет т + п — 1=4 + 4
— 1 = 7 базисных переменных. Опорное решение является вырожденным, так как одна из его координат равна нулю. Вычислим значение целевой функции на этом опорном решении F(X1)=100·1+0·2+100·3+100·4+200·7+100·12+200·0=3400.
Слайд 843. Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку
оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равна стоимости
( ).
Записываем систему уравнений для нахождения потенциалов:
( ).
Записываем систему уравнений для нахождения потенциалов:
Слайд 86Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная.
Одному из потенциалов задаем значение произвольно: пусть и2 = 0. Остальные потенциалы находятся однозначно:
Слайд 884. Проверяем опорное решение Х1 на оптимальность. С этой целью вычисляем
оценки
для всех незаполненных клеток таблицы
Слайд 905. Переходим к новому опорному решению. Находим клетку таблицы, которой соответствует
наибольшая положительная оценка:
для клетки (1,4). Для этой клетки строим цикл. Ставим в нее знак «+»
max{7,3,2,2}=7
Цикл изображен в таблице.
Слайд 92Положительные оценки записываем в левые нижние углы соответствующих клеток таблицы, вместо
отрицательных ставим знак «—». Начальное опорное решение не является оптимальным, так как имеются положительные оценки.
Слайд 93В данном случае минимум перевозок в клетках, отмеченных знаком «-», достигался
сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно т + п — 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.
F(X) = 0·1 + 100·1 + 100·2 + 100·3 + 0·4 + 300·7 + 200·0 = 2700.
Слайд 946. Проверяем второе опорное решение Х2 на оптимальность. Находим, потенциалы и
оценки. Решение не является оптимальным, так как имеются положительные оценки Δ31=2, Δ32=2, Δ42=1 и Δ43=2. Наибольшая из них равна 2 одновременно для трех клеток (3, 1), (3, 2) и (4, 3). В одну из них, пусть в клетку (3, 2), ставим знак «+». Для этой клетки строим цикл и находим величину груза по циклу: θ=min{100,300}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем третье опорное решение Х3.
Слайд 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:
7. Решение не является оптимальным, так как имеются положительные оценки Δ31=2 и Δ43=2. Ставим знак «+» пусть в клетку (3, 1), Для этой клетки строим цикл и находим величину груза для перераспределения по циклу: θ=min{100,200}=100. Осуществляем сдвиг по циклу на величину θ=100. Получаем четвертое опорное решение Х4:
Слайд 98Вычисляем значение целевой функции на четвертом опорном решении: 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:
8. Проверяем решение Х4 на оптимальность. Находим потенциалы и оценки. Они приведены в таблице. Положительными являются оценки Δ13=2, Δ42=1 и Δ43=4. Для клетки (4, 3), которой соответствует наибольшая оценка, строим цикл и находим величину груза для перераспределения по циклу: θ=min{200,0,100}=0. Осуществляем сдвиг по циклу на величину θ=0. Получаем пятое опорное решение Х5:
Слайд 100Решение Х5 является оптимальным, так как все оценки отрицательные. Значение целевой
функции F(X5) = F(X4) = 2300.
Ответ: min F(Х)=2300 при
Ответ: min F(Х)=2300 при
Х*=
.
