p align="left">В итоге получим:|
| bi | x5 | x3 | | L | 14 | 5 | 4 | | x2 | 3 | 1 | 1 | | x4 | -5 | -1 | 0 | | x1 | 4 | 2 | 1 | | |
Коэффициенты при свободных переменных в целевой функции положительны, значит, найденное решение является оптимальным. Ответ: x1=4 x2=3 x3=0 x4=-5 x5=0 L=14 2.3 Решение задачи 3Условие задачи задано в виде транспортной таблицы:|
ПН ПО | B1 | B2 | B3 | запасы | | A1 | 50 | 15 | 10 | 300 | | A2 | 21 | 30 | 20 | 100 | | A3 | 18 | 40 | 25 | 200 | | A4 | 23 | 22 | 12 | 800 | | A5 | 25 | 32 | 45 | 200 | | заявки | 500 | 300 | 800 | | | |
Применим к задаче метод «Северо-Западного угла». Для этого заполним таблицу начиная с левого верхнего угла без учёта стоимости перевозок: |
ПН ПО | B1 | B2 | B3 | запасы | | A1 | 300 | | | 300 | | A2 | 100 | | | 100 | | A3 | 100 | 100 | | 200 | | A4 | | 200 | 600 | 800 | | A5 | | | 200 | 200 | | заявки | 500 | 300 | 800 | | | |
В таблице заполнено n+m-1=7 клеток, значит найденное решение является опорным. Далее необходимо улучшить план перевозок в соответствии со стоимостями доставки грузов. Для этого используем циклические перестановки в тех циклах, где цена отрицательна. |
ПН ПО | B1 | B2 | B3 | запасы | | A1 | 50 300 | 15 | 10 | 300 | | A2 | 21 100 | 30 | 20 | 100 | | A3 | 18 100 | 40 100 | 25 | 200 | | A4 | 23 | 22 200 | 12 600 | 800 | | A5 | 25 | 32 | 45 200 | 200 | | заявки | 500 | 300 | 800 | | | |
В данной таблице в верхней части ячейки указана стоимость перевозки, а в нижней количество перевозимого груза. Прямоугольником выделен отрицательный цикл г1=25+22-40-12=-5. Минимальное значение перевозок, стоящих в отрицательных вершинах равно k1=100. В итоге получим уменьшение стоимости перевозки: ДL1=-5*100=-500 Транспортная таблица примет следующий вид: |
ПН ПО | B1 | B2 | B3 | запасы | | A1 | 50 300 | 15 | 10 | 300 | | A2 | 21 100 | 30 | 20 | 100 | | A3 | 18 100 | 40 | 25 100 | 200 | | A4 | 23 | 22 300 | 12 500 | 800 | | A5 | 25 | 32 | 45 200 | 200 | | заявки | 500 | 300 | 800 | | | |
г2=12+32-45-22=-23 k2=200 ДL2=-23*200=-4600 |
ПН ПО | B1 | B2 | B3 | запасы | | A1 | 50 300 | 15 | 10 | 300 | | A2 | 21 100 | 30 | 20 | 100 | | A3 | 18 100 | 40 | 25 100 | 200 | | A4 | 23 | 22 100 | 12 700 | 800 | | A5 | 25 | 32 200 | 45 | 200 | | заявки | 500 | 300 | 800 | | | |
г3=10+18-50-25=-47 k3=100 ДL3=-47*100=-4700 |
ПН ПО | B1 | B2 | B3 | запасы | | A1 | 50 200 | 15 | 10 100 | 300 | | A2 | 21 100 | 30 | 20 | 100 | | A3 | 18 200 | 40 | 25 | 200 | | A4 | 23 | 22 100 | 12 700 | 800 | | A5 | 25 | 32 200 | 45 | 200 | | заявки | 500 | 300 | 800 | | | |
г4=10+23-12-50=-29 k4=200 ДL4=-29*200=-6800 |
ПН ПО | B1 | B2 | B3 | запасы | | A1 | 50 | 15 | 10 300 | 300 | | A2 | 21 100 | 30 | 20 | 100 | | A3 | 18 200 | 40 | 25 | 200 | | A4 | 23 200 | 22 100 | 12 500 | 800 | | A5 | 25 | 32 200 | 45 | 200 | | заявки | 500 | 300 | 800 | | | |
Отрицательных циклов в транспортной таблице больше нет. Следовательно, можно предположить, что найденное решение является оптимальным. Для проверки применим метод потенциалов. Составим систему: Положим в2=0, тогда б4=-22 в1=1, б2=-20 в3=-10, б2=-22 б1=-20, б5=-32 Все коэффициенты б отрицательны, значит, найденный план перевозок является оптимальным. Ответ: x21=100; x31=200; x41=200; x42=100; x52=200; x13=300; x43=500. 2.4 Решение задачи 4Составим математическую модель поставленной задачи.Найти минимум функции f(x1,x2) При ограничениях Заменив знак функции f(x1,x2) на противоположный, перейдем к поиску максимума функции:Теперь задача приведена к стандартному виду задачи квадратичного программирования. Приступим к решению.1) Определим стационарную точкуРешив систему, получим: x1=10x2=7Очевидно, что данные координаты не удовлетворяют условиям ограничений. Поэтому проверять стационарную точку на относительный максимум нет необходимости.2) Составим функцию Лагранжа: Применив к функции Лагранжа теорему Куна-Таккера, будем иметь систему:3) Преобразуем полученную систему: Из уравнения 3 системы следует, что x2=6-x1:Для обращения неравенств системы в равенства введём V1, V2, W и преобразуем систему:4) Запишем условия дополняющей нежесткости:5) Введем в систему уравнений искусственные переменные z1,z2:Поставим задачу максимизации функции .Для решения этой задачи воспользуемся Симплекс-методом. Примем переменные z1 и z2 в качестве базисных:Составим Симплекс таблицу:|
| bi | x1 | U1 | U2 | V1 | V2 | | ц | -17M 0 | -5M 0 | 0 0 | M 0 | M 0 | -M 0 | | z1 | 9 8 | 2 3 | -1 1 | 2 -3 | -1 0 | 0 1 | | z2 | 8 8 | 3 3 | 1 1 | -3 -3 | 0 0 | 1 1 | | W | 0 0 | -1 0 | 0 0 | 0 0 | 0 0 | 0 0 | | |
|
| bi | x1 | z2 | U2 | V1 | V2 | | ц | -17M 17M | -5M M | 0 M | M -M | M -M | -M M | | z1 | 17 17/5 | 5 1/5 | 1 1/5 | -1 -1/5 | -1 -1/5 | 1 1/5 | | U1 | 8 -51/5 | 3 -3/5 | 1 -3/5 | -3 3/5 | 0 3/5 | 1 -3/5 | | W | 0 17/5 | -1 1/5 | 0 1/5 | 0 -1/5 | 0 -1/5 | 0 1/5 | | |
|
| bi | z1 | z2 | U2 | V1 | V2 | | ц | 0 | M | M | 0 | 0 | 0 | | x1 | 17/5 | 1/5 | 1/5 | -1/5 | -1/5 | 1/5 | | U1 | -11/5 | -3/5 | -2/5 | 1/2 | 3/5 | -2/5 | | W | 17/5 | 1/5 | 1/5 | -1/5 | -1/5 | 1/5 | | |
В итоге получим x1=17/5 x2=6-x1=13/5 Как видно, координаты стационарной точки сильно отличаются от координат, полученных в качестве ответа. Это можно объяснить тем, что стационарная точка не удовлетворяет условиям ограничений. Условия дополняющей нежесткости выполняются. Следовательно, найденное решение является оптимальным. Найдем значения целевой функции: =- 51/5 - 52/5 + 289/50 - 221/25 + 169/25 = = -16.9 Ответ: x1 = 17/5 x2 = 13/5 f(x1,x2) = -16.9
Страницы: 1, 2
|
