Задача. Построить двухиндексную (транспортную) модель задачи линейного программирования, найти опорные планы методами северо-западного угла и минимального элемента. Решить транспортную задачу линейного программирования, используя метод потенциалов.
Составьте план перевозок продуктов из n пунктов отправления (Аi) в m пункты назначения (Bj). План должен обеспечить минимальные транспортные издержки и полностью удовлетворить спрос потребителей на продукты. Запас (аi), потребность (bj) и стоимость перевозки 1 единицы измерения продуктов (сij) приведены в таблице 1.
URL=http://www.radikal.ru](IMG:http://s018.radikal.ru/i525/1202/f3/78a14af600c3.jpg)[/URL]
Модель я построила. Решила задачу методом северо-западного угла, получила таблицу 2.
Стала решать Методом потенциалов.
Нашла потенциалы поставщиков и потребителей для имеющегося решения.
Нашла оценки свободных ячеек. Получила таблицу 4:
(IMG:http://s017.radikal.ru/i415/1202/d2/d4483bb561d5.jpg)
Из свободных ячеек (незадействованных маршрутов), имеющих отрицательные оценки, остановим свой выбор на ячейке А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? если только в обратном порядке те же ячейки взять.
(IMG:http://s44.radikal.ru/i103/1202/af/4b01cfd739c0.jpg)
А как правильно выбрать цикл? Выбираем ячейку с наименьшей отрицательной оценкой, затем по ближайшим базовым ячейкам, шагая по горизонтали, по вертикали, "даем круг" из выбранной ячейки в нее же? Или я что-то не правильно понимаю?
Может быть, нужно обязательно все базисные ячейки задействовать? просто нигде про это ничего не написано...

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

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

Возможно (IMG:style_emoticons/default/smile.gif)

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

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

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

Чуть раньше, у меня из такой таблицы:
(IMG:http://i037.radikal.ru/1202/e7/c5f89b621d2b.jpg)

получиласть такая:
(IMG:http://i051.radikal.ru/1202/b6/4df0636fd1fe.jpg)

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

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



Т.е. здесь нет
(IMG:http://s017.radikal.ru/i413/1202/99/e7b8c7619bda.jpg)
а здесь есть
(IMG:http://i037.radikal.ru/1202/e7/c5f89b621d2b.jpg)

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

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

Да нет, сейчас покажу, куда девается эта сотня. Была таблица
(IMG:http://s40.radikal.ru/i089/1202/b1/01043e88f6bc.jpg)

Получилась:
(IMG:http://s44.radikal.ru/i106/1202/c7/3b9c79c0fe31.jpg)

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

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


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

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

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

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

(IMG:style_emoticons/default/smile.gif)

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

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

(IMG:style_emoticons/default/thumbsup.gif) Пожалуйста! (IMG:style_emoticons/default/smile.gif)