Задача. Построить двухиндексную (транспортную) модель задачи линейного программирования, найти опорные планы методами северо-западного угла и минимального элемента. Решить транспортную задачу линейного программирования, используя метод потенциалов.
Составьте план перевозок продуктов из n пунктов отправления (Аi) в m пункты назначения (Bj). План должен обеспечить минимальные транспортные издержки и полностью удовлетворить спрос потребителей на продукты. Запас (аi), потребность (bj) и стоимость перевозки 1 единицы измерения продуктов (сij) приведены в таблице 1.
URL=http://www.radikal.ru][/URL]
Модель я построила. Решила задачу методом северо-западного угла, получила таблицу 2.
Стала решать Методом потенциалов.
Нашла потенциалы поставщиков и потребителей для имеющегося решения.
Нашла оценки свободных ячеек. Получила таблицу 4:

Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке А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).

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




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

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

Я правильно выбрала ячейку А3В2? Выбираем же с наименьшей отрицательной оценкой? Серым цветом я выделила базисные ячейки, а цветом темнее те, что составляют цикл. А как еще можно попасть из А3 в В2? если только в обратном порядке те же ячейки взять.

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

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

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

Возможно

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

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

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

Чуть раньше, у меня из такой таблицы:


получиласть такая:


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

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



Т.е. здесь нет

а здесь есть

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

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

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


Получилась:

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

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


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

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

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

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

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

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

Пожалуйста!