Принципы решения некоторых задач математического программирования
Контрольная работа - Математика и статистика
Другие контрольные работы по предмету Математика и статистика
b>03011/2101/7А403003/71-2/7А15/3310-1/705/7?600-12/2105/73-я итерацияА208/3010-1/911/63А31/370017/3-2/3А45/341001/31/3?100004/31/3
Отсюда следует, что:
5. Решение двойственной задачи с помощью второй основной теоремы теории двойственности
Вторая теорема двойственности также позволяет решить двойственную задачу, используя решение первой задачи и используя ограничения.
Разделим переменные на базисные и свободные методом полного исключения (см. Графический метод) и возьмем точку А (см. Графический метод) получим:
А=(4; 7)
Отсюда следует, что необходимо искать и .
Решив, систему уравнений получим: .
Отсюда
Ответ: Максимальная прибыль будет равна 10.
Задача №2
1.Построение математической модели транспортной задачи
Транспортные задачи - это задачи в которых нужно решить проблему: доставку продукции от множества поставщиков к множеству потребителей с минимальными затратами на транспортировку.
Для решения этих задач нужно знать матрицу поставщиков , матрицу потребителей и матрицу перевозок . Матрица перевозок показывает стоимость перевозки от i поставщика к j потребителю.
Обычно условие такой задачи задается или сводится к таблице перевозок. Верхняя строчка таблицы показывает ресурсы поставщиков, самый левый столбец указывает потребности потребителя. Остальная матрица таблицы показывает затраты на доставку продукции от поставщиков к потребителям.
Решение задачи будет определение количество товара, которое необходимо поставить от каждого поставщика к каждому потребителю.
Исходя из условий задачи получаем:
Матрица поставщиков имеет вид:
Матрица потребителей имеет вид:
Матрица перевозок имеет вид:
Система ограничений по поставки имеет вид:
Система ограничений по потреблению имеет вид:
Функция цели имеет вид:
2.Поиск опорного плана транспортной задачи методом северо-западного угла
Выбираем первую пустую северо-западную клетку, и заполняем ее максимальным допустимым значением. После выбираем следующую северо-западную клетку и заполняем. Процедура повторяется до тех пор, пока не будут удовлетворены все поставщики и потребители. В итоге получаем опорный план методом северо-западного угла:
i / j40256025501 402 10217022 151 55230121 53 25
Стоимость перевозок: L=40+20+30+55+5+75=225
3. Поиск опорного плана транспортной задачи методом минимального элемента
Выбираем клетку с наименьшей стоимостью перевозки и заполняем ее максимально допустимым значением. После выбираем следующую клетку и заполняем ее. Процедура повторяется до тех пор, пока не будут удовлетворены все поставщики и потребители. В итоге получаем опорный план методом минимального элемента.
i / j40256025501 40221 1070221 602 103012 2513 5
Стоимость перевозок: L=40+50+60+10+20+15=195
4. Решение транспортной задачи методом потенциалов
Введем для обозначения потенциалов буквы: для обозначения потенциала строки букву U, обозначения потенциалов столбца букву V. Возьмем опорный план, найденный в третьем пункте задачи, и заполним таблицу с учетом потенциалов. Причем для потенциалов будет выполняться условие: .
i / j40256025U501 40221 10U170221 602 10U23012 2513 5U3VV1V2V3V4Составить систему уравнений по заполненным клеткам.
Поскольку уравнений шесть, а неизвестных переменных семь, зададим потенциал . Отсюда , , и , , , .
Составляем косвенные стоимости () для пустых клеток по найденным потенциалам.
Определяем оценки (г) для пустых клеток по формуле: прямая минус косвенная стоимость.
Поскольку отрицательных оценок есть, то данный план не оптимален. Составляем новый план с другим позиционированием коэффициентов.
i / j40256025U501 25221 25U17022 101 602U2301 152 1513U3VV1V2V3V4
Составить систему уравнений по заполненным клеткам.
Поскольку уравнений шесть, а неизвестных переменных семь, зададим потенциал . Отсюда , , и , , , .
Составляем косвенные стоимости () для пустых клеток по найденным потенциалам.
Определяем оценки (г) для пустых клеток по формуле: прямая минус косвенная стоимость.
Так как отрицательных оценок нет, то план перевозок оптимален. L=175
Ответ: Себестоимость перевозок равна L=175.