Версия для печати темы

Автор: Faina 19.2.2012, 8:34

Задача. Построить двухиндексную (транспортную) модель задачи линейного программирования, найти опорные планы методами северо-западного угла и минимального элемента. Решить транспортную задачу линейного программирования, используя метод потенциалов.
Составьте план перевозок продуктов из n пунктов отправления (Аi) в m пункты назначения (Bj). План должен обеспечить минимальные транспортные издержки и полностью удовлетворить спрос потребителей на продукты. Запас (аi), потребность (bj) и стоимость перевозки 1 единицы измерения продуктов (сij) приведены в таблице 1.
URL=http://www.radikal.ru][/URL]
Модель я построила. Решила задачу методом северо-западного угла, получила таблицу 2.
Стала решать Методом потенциалов.
Нашла потенциалы поставщиков и потребителей для имеющегося решения.
Нашла оценки свободных ячеек. Получила таблицу 4:
http://www.radikal.ru
Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке А3В2(Δ32=-3). Поставим курсор мыши в выбранную свободную ячейку. Используя горизонтальные и вертикальные перемещения курсора, соединим непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку. Базисные ячейки, расположенные в вершинах построенной ломаной линии, образуют цикл для выбранной нами ячейки. Цикл будет состоять из ячеек
A3B2, A2B4, A2B3, A2B2. Из четных ячеек этого цикла найдем ячейку, обладающую наименьшим значением: {150,100,325,25}=25.
Вводим новый маршрут доставки продукции от поставщика A3 к потребителю B2. В итоге получаем:
Общие расходы на доставку продукции от поставщиков к потребителям изменятся на 3*25-9*25+5*25-2*25+2*25=(3-9+5-2+2)*25=(-1)*25=-25.
Выражение, стоящее в скобках, должно быть равно оценке свободной ячейки (незадействованного маршрута), для которой мы строили цикл. А оно не равно ей: в скобках, согласно полученной таблице, должно получиться (-3), а у меня в скобках получается (-1).

Понимаю, что тут много написано. Но, может, кто увидит мою ошибку?




Сразу говорю: Я не дорешала эту задачу, застряла на этом месте...

Автор: tig81 19.2.2012, 8:42

а почему из таких? Нарисуйте указанный цикл?

Автор: Faina 19.2.2012, 17:58

Я правильно выбрала ячейку А3В2? Выбираем же с наименьшей отрицательной оценкой? Серым цветом я выделила базисные ячейки, а цветом темнее те, что составляют цикл. А как еще можно попасть из А3 в В2? если только в обратном порядке те же ячейки взять.
http://www.radikal.ru
А как правильно выбрать цикл? Выбираем ячейку с наименьшей отрицательной оценкой, затем по ближайшим базовым ячейкам, шагая по горизонтали, по вертикали, "даем круг" из выбранной ячейки в нее же? Или я что-то не правильно понимаю?
Может быть, нужно обязательно все базисные ячейки задействовать? просто нигде про это ничего не написано...

Автор: tig81 19.2.2012, 18:36

нет, просто вы должны брать лишь угловые ячейки, а не все, что попадаются на пути, т.е. работаете только с ячейками А2В2, А2В4, А3В4 и А3В2.

Автор: Faina 19.2.2012, 19:53

так вот в чем дело!

Автор: tig81 19.2.2012, 20:08

Возможно

Автор: Faina 24.2.2012, 22:00

Подскажите, пожалуйста.
Вот мы видим, что среди оценок свободных ячеек есть отрицательные, и делаем вывод, что решение не является оптимальным, тогда из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, обязательно выбираем ячейку с самой наименьшей оценкой? Дело в том, что, когда я выбрала с самой наименьшей, то никак не могу построить для нее цикл. Невозможно, используя только горизонтальные и вертикальные перемещения курсора, соединить непрерывной линией базисные ячейки так, чтобы вернуться в исходную ячейку.
http://www.radikal.ru

Автор: tig81 24.2.2012, 22:18

У вас план недопустимый (вырожденный), т.к. число m+n-1=3+5-1=7 (m - кол-во поставщиков, n - кол-во потребителей) не равно числу k=6 - число занятых клеток в таблице.

Когда переносили груз видно получалась клетка с 0, и вы его просто не написали. Лучше его оставить. Либо сейчас ввести клетку с 0 грузом.

Автор: Faina 25.2.2012, 9:44

Чуть раньше, у меня из такой таблицы:
http://www.radikal.ru

получиласть такая:
http://www.radikal.ru

Но тогда, в этом случае, если в ячейке оставить "0", то получится: m+n-1=3+5-1=7 не равно числу k=8 - число занятых клеток в таблице.
Или я не про тот ноль говорю?

Автор: tig81 25.2.2012, 10:32

В предоставленной вчера таблице нет в клетке А1В2 100. В последнем вашем сообщении эта клетка занята. Не потеряли это значение?



Т.е. здесь нет
http://www.radikal.ru
а здесь есть
http://www.radikal.ru

Автор: Faina 25.2.2012, 10:55

сейчас все перепроверю. Вот что значит, свежий взгляд на задачу!

Автор: tig81 25.2.2012, 10:58

Но обычно такие задачи легче сделать самому, чем перепроверять
Но, возможно, вы показали не две подряд идущие таблицы (?), так что может груз где-то и ушел по назначению, а не его "съели" пираты.

Автор: Faina 25.2.2012, 11:14

Да нет, сейчас покажу, куда девается эта сотня. Была таблица
http://www.radikal.ru

Получилась:
http://www.radikal.ru

Автор: tig81 25.2.2012, 11:17

Скорее всего в ячейке А3В5 надо оставить 0, т.е. сделать ее занятой

Автор: Faina 25.2.2012, 11:26

Вчера и сегодня я отправляла таблицы из разных мест решения. Я все-таки не пойму, если оставлять нули в ячейках вместо этих "100-100", "25-25", как вы говорите, то потом эти нулевые клетки тоже считать, как базовые? А ведь базовых становится больше, когда, например, в ячейку с отрицательной оценку приходит, например, 100 единиц продукции (как в ячейке А1В5 последней таблицы).
Может, я не про тот нуль говорю?


А тогда в А1В2 что ставить? Тоже нуль? Или же мы делаем занятыми более выгодные для нас ячейки, чтобы потом по ним прокладывать "пути-дорожки-новые маршруты"?

Автор: tig81 25.2.2012, 11:27

нет, ту ячейку, которую разгружаете, оставляете пустой, но у вас совпало, что обе разгружаемые ячейки содержат одинаковое кол-во груза, поэтому оставляете одну пустой, а во второй 0. Ну а так надо смотреть решение подряд.

но пока не присылайте, попробуйте доделать до конца.

Автор: Faina 25.2.2012, 11:35

хорошо, попробую

Автор: tig81 25.2.2012, 11:43

Автор: Faina 25.2.2012, 13:37

Ура!!!! Я сделала это!!!! Конечно, не без вашей помощи
Наконец-то! Две недели, каждый день понемногу, но.... я смогла это! Впервые в жизни решила Транспортную задачу! Пойду, маме похвастаюсь

Ой, совсем забыла... Спасибо огромное!

Автор: tig81 25.2.2012, 13:44

Пожалуйста!