Содержание
Основные понятия: сеть, исток, сток, поток, пропускная способность. Теорема Форда-Фалкерсона. 3
Вычислительная процедура симплекс метода. 5
Практическое задание. 8
Список использованных источников. 12
1. Основные понятия: сеть, исток, сток, поток, пропускная способность. Теорема Форда-Фалкерсона
Сеть – это взвешенный конечный граф без циклов и петель, ориентированный в одном общем направлении от вершины I, являющейся входом (истоком) графа, к вершине S, являющейся выходом (стоком) графа.
Для наглядности – по дугам из истока I в сток S направляется некоторое вещество (груз, ресурс, информация и т.п.)
Количество xij вещества, проходящего через дугу из вершины xi в xj в единицу времени, называется потоком по дуге.
Предполагается, что если из вершины xi в xjнаправляется поток величиной xij , то величина потока изxj в xi равна –xij , то есть ......
2. Вычислительная процедура симплекс метода
Суть симплекс-метода заключается в том, что решение задачи линейного программирования (ЗЛП) осуществляется итерационно и основывается на переходе от одного допустимого базисного решения к другому, при котором значение целевой функции улучшается. Этот процесс длится до тех пор, пока дальнейшее улучшение целевой функции станет невозможно.
В алгебраических терминах симплекс-метод предполагает:
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходить к нехудшему опорному плану.....
3. Практическое задание
В m пунктах производства находится однородный продукт (уголь, картофель и т. д.) в количествах соответственно единиц, который должен быть доставлен n потребителям в количествах единиц. Известны транспортные издержки (расходы), связанные с перевозкой единицы продукта из пункта в пункт . Требуется составить такой план перевозок, который обеспечивал бы при минимальных транспортных издержках удовлетворение спроса всех пунктов потребления за счет распределения всего продукта, произведенного всеми пунктами поставки.
|
Номер варианта |
– запас единиц груза i-го поставщика |
– потребность единиц груза j-го потребителя |
Матрица стоимости |
|
18 |
Решение.
Обозначим через xij – объем перевозки готовой продукции пункта производства Аi к потребителю Вj , а через f – общие затраты.
Перед формированием ограничений сравним суммарную мощность производителей – запас груза (160 + 400 + 240 = 800 ед.) с суммарной...
Список использованной литературы:
Кузнецов А.В. и др. Высшая математика. Математическое программирование. – Мн.: Выш. школа, 2001. Минюк С.А и др. Математические методы и модели в экономике. - Мн.: Тетрасистемс, 2002. Шило А.Ф. Экономико-математические методы и модели. Учебное пособие. – Мн.: ИПП, 2005. Экономико-математические методы и модели / Под ред. А.В. Кузнецова. – Мн.: БГЭУ, 2003. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию. – Мн.: Выш. шк., 2001.
