Программное решение задачи линейного программирования

kon7760

Более точно - транспортную задачу линейного программирования (по войне задача то есть
максимизировать sum { c(i,j) * x(i,j) }, когда x(i,j) >=0, и фиксированы суммы строк и столбцов матрицы иксов.
Не вручную я имею в виду - может ексель это умеет? Или в матлабе каком-нибудь. В нем не рюхаю, поэтому прошу поподробнее.

kachokslava

да, эксель умеет, если установлен пакет "поиск решения" - по умолчанию не ставится, как и редактор формул.
а так - симплекс-метод.

kon7760

А что это за пекет?
Где взять?

kachokslava

У меня Офис 2000 русский.
Эта штука была ещё в 97 офисе и в XP. про 2003 офис не в курсе.

kachokslava

Потом надо будет совершить некоторые дополнительные телодвижения:
=>
Вызывается эта штука так:
=>
Дальше интуитивно или по справке
В целевой ячейке можно (нужно) формулу писать - чтобы она зависела от изменяемых ячеек

kon7760

ВАУ
Спасибо!
Приду домой, буду с этим экспериментировать
Надеюсь, это будет решением проблемы!

kon7760

Не решает Ексель проблемы, так и пишет "Поиск не может найти подходящего решения".
Какие еще могут быть способы?

kachokslava

Пости конкретную задачу. может, ты чего-то не так в экселе вводил?

natalia

есть на ВМК такая приблуда, Lindo называется. Изучается принудительно в предмете ППП (вроде на 4м курсе 2го потока).
Так вот она решает задачи лп симплекс-методом.

kachokslava

пять к одному, что ты область не ограничил (например, не указал x_i>=0) - на неограниченной области экстремума может и не существовать

kachek-2003

Есть еще пакет древний, ПЭР называется, т.е. пакет экономических расчетов. Он в инете много где валяется, можно скачать - в свое время это делала, у меня тоже есть дистрибутив, могу залить. Там вроде все просто и понятно, мне решал задачки.

kon7760

Конкретно задача -
транспортная задача линейного программирования, то есть
максимизировать sum { c(i,j) * x(i,j) }, когда x(i,j) >=0, и фиксированы суммы строк и столбцов матрицы иксов : sum по i {x(i,j)} = a(j) ; sum по j {x(i,j)} = b(i)
Не знаю, что я не так вводил в екселе, галочку на неотрицательнось поставил, матрицу коэффициентов c(i,j) ввел, два вектора-ограничения тоже.
Но я для всех сумм заводил отдельные ячейки - для суммы каждой строки и каждого столбца, чтобы потом эти ячейки вставить в ограничения на равенство.
Может, это неправильно?

kon7760

А у тебя есть случайно так эта приблуда?
Дай пожалуйста

kon7760

Залей пожалуйста,
Эх, может он решит наконец эту военную проблему.

disepa

А может матрицу в студию?

kon7760

Имеет ли значение конкретный пример?
Я вводил для меньшего гемора матрицу коэффициентов
1 2
3 4
и ограничения на суммы столбцов (5,6 строк (7,8)

disepa

Просто у меня где-то есть программа, котороая считает что-то в этом роде. Только я не помню,
она для целочисленное решение ищет или нет. (Кстати у тебя какое решение должно быть?)
И еще,
>sum { c(i,j) * x(i,j) }
тут сумма по каким индексам?

kachek-2003

Не доступен твой комп, может IP напишешь?

disepa

.hackers (172.16.6.219)

kachek-2003

Залил

kon7760

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

kon7760

Вижу, спасибо.
А че там столько ехе-шников?
Вижу в списке решаемых задач транспортную. Как бы до нее добраться.
Как прогу юзать?

kachek-2003

Запускаешь per.exe. и юзаешь

kon7760

Ксати, зря я в екселе набирал матрицу 2 на 2, ща только понял
Получается, что не всегда вообще решение есть - 4 неизвестных, и 4 ограничения на равенство

kon7760

Почему-то он при решении фиктивный столбец добавляет
Странно это.

kachokslava

Это общая рекомендация - добавлять столбец.
запости задачу в таком виде:

(индекс вверху - не возведение в степень. просто ещё один индекс)

kon7760

ОК

А зачем добавляется столбец? Я так понимаю, решение подразумевается без фиктивного столбца.

kachokslava

как всегда эти военные извратили постановку задачи
запости пожалуйста конкретные данные (a_i,b_j, c_ij)
или приватом
вполне может быть, что она расходится для конкретных твоих данных

kachokslava

странный пример какой-то у тебя четыре неизвестных, x11, x12, x21, x22 и четыре уравнения на равенство:


x11+x12 = 5
x21+x22 = 6
x11+x21 = 7
x12+x22 = 8


вроде как область допустимых иксов состоит из одной точки. ессно алгоритмы ЛП там не работают
вот если одно из ограничений на равенство убрать, эксель нормально считает. (я убрал последнне) - за три шага всё находит..


x11= 5 x21= 0
x12= 2 x22= 8


Z=43

kon7760

Да, я уже понял, что нельзя брять матрицы 2 на 2 - 4 неизвестных, 4 линейных ограничения на равенство.
А как может не быть решения при бОльшей матрице? Ведь иксы-то все неотрицательны, и если целые, то их количество вообще конечно. А я так понимаю по смыслу задачи все целое.
Конкретные значения сейчас точно не помню - на работе сижу, но вроде
матрица
2 5 9 5
7 4 6 4
3 7 1 7
2 5 7 5
и вектор для строк - (9 6 1 7 столбцов (3 6 2 1)

kachokslava

хитро..
для равенств эксель почему-то искать не умеет.
для неравенств находит..

kon7760

Так что делать, помогите!
ЧТоб фиктивного столбца не было...

disepa

Переход от неравенств к равенствам получается с помощью добавления еще переменных, чтобы получилось что-то типа такого
a*x=b
a*x - c <=b
c<1
c>=0
Может из-за этого и добавляется твой "фиктивный столбец".
Оставить комментарий
Имя или ник:
Комментарий: