Форум программистов, компьютерный форум, киберфорум
PHP для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 173

Оптимизация методом потенциалов

15.05.2015, 22:42. Показов 1881. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый вечер, оптимизирую ТЗ методом потенциалов. Нашел псевдостоимости, дальше нужно выбрать минимальную псеводостоимость, которая не удовлетворяет условию, и от нее начать движение через базисные клетки, чередуя "+" "-".
Есть ли у вас алгоритм этого цикла? Если нужно, выложу код. Заранее, спасибо

Добавлено через 2 часа 48 минут
помогите, осталось только с этим циклом пересчета справиться.

Добавлено через 2 часа 20 минут
может блок - схема есть у кого-нибудь?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
15.05.2015, 22:42
Ответы с готовыми решениями:

Транспортная ЗЛП методом северо-западного угла и методом потенциалов
здравствуйте! нужно создать программу, которая реализует транспортную задачу двумя методами. в интернете куча информации, но нормального...

Расчёт схемы методом узловых потенциалов (методом Кирхгофа внутри)
Помогите пожалуйста сделать расчёт схемы методом узловых потенциалов и проверьте пожалуйста моё решение методом Кирхгофа.

Расчет разветвлённой цепи постоянного тока методом узловых потенциалов и методом эквивалентного генератора
Дайте списать. Значит задача такая. Даже две. 1. Расчет разветвлённой цепи постоянного тока методом узловых потенциалов. 2. Расчет...

12
Заблокирован
15.05.2015, 23:12
Цитата Сообщение от Beezy Посмотреть сообщение
оптимизирую ТЗ методом потенциалов. Нашел псевдостоимости, дальше нужно выбрать минимальную псеводостоимость, которая не удовлетворяет условию, и от нее начать движение через базисные клетки, чередуя "+" "-".
Как говорил кто то, а после него, - многие:
Будь проще! И люди к тебе потянутся! ©
Либо используй другую ветку, ту где обсуждают алгоритмы.
0
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 173
16.05.2015, 10:45  [ТС]
Trukl, я даже не знаю как это объяснить нормально. Решил транспортную задачу методом северо-западного угла, теперь нужно найти оптимальное решение методом потенциалов. Для этого нужно найти псевдостоимости, а далее циклом пересчета подгонять другие значения, чтобы в итоге суммарная стоимость плана была меньше исходной, вот на этом я и застрял.
На скриншоте показано, что мне нужно: получить ограниченную фигуру, только как сделать это программно даже не знаю
Миниатюры
Оптимизация методом потенциалов  
0
Заблокирован
16.05.2015, 13:57
Нееее, проще ты не стал. Однако прогресс на лицо. Теперь нам известно что ТЗ - это оказывается транспортная задача, а не техническое задание.
Давай друже, углубляйся. Чё за задача, чё за методы, чё за псевдостоимости, по каким формулам формируются цифры на скриншоте?
0
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 173
16.05.2015, 14:30  [ТС]
Trukl, сейчас все подробно объясню(с самого начала).
Есть html - форма, в которую вносятся данные потребителей, складов, стоимости.
Далее в php уже формируем начальный массив значений(см. скриншот 1):
Кликните здесь для просмотра всего текста
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
<?php
    //значения высоты и ширины матрицы
    $height = $_GET['matr'][0];
    $width = $_GET['matr'][1];
    $matrix = array();
    $arr_sklad = array();//массив значений склада
    $arr_potreb = array();//массив значений потребителей
    $arr_perevozka = array();//массив значений перевозок
    $arr_opora = array();//массив значений опорного плана
    $arr_a = array();//массив значений платежей a[i](для метода потенциалов!)
    $arr_b = array();//массив значений платежей b[i](для метода потенциалов!)
    $arr_perevozka_poten = array();//массив значений перевозок методом потенциалов
?>
<div class="content">
    <?php
        if (isset($_REQUEST['information'])) {
            //обрабатываем данные формы, заносим значения в двумерный массив 
            for($i = 0; $i < $height; $i++) {
                $k = $z;// $k = $z = 0 - начальное значение
                for($j = 0; $j < $width; $j++) {
                    if ($i == 0 & $j == 0) {
                        $matrix[$i][$j] = 0;//первый элемент неактивен = 0;
                    }
                    else {
                        $matrix[$i][$j] = $_GET['text'][$i+$k]; 
                        $k++; $z = $k-1;
                    };
                };
            };
            //------------------------------------------
        };
        for ($j = 1; $j < $width; $j++) {
            $arr_sklad[$j] = $matrix[0][$j];//заполняем массив значений склада
            $sum_sklad += $arr_sklad[$j];//сумма всех элементов массива arr_sklad
        };
        for ($i = 1; $i < $height; $i++) { 
            $arr_potreb[$i] = $matrix[$i][0];//заполняем массив значений потребителей
            $sum_potreb += $arr_potreb[$i];//сумма всех элементов массива arr_potreb
        };
        for ($i = 1; $i < $height; $i++) { 
            for ($j = 1; $j < $width; $j++) { 
                $arr_perevozka[$i][$j] = $matrix[$i][$j];//заполняем массив значений перевозок
            };
        };
?>

Выводим эту информацию в таблицу. Дальше нам необходимо найти опорный план методом северо-западного угла.
Записывает значения опорного плана в массив $arr_opora[$i][$j] (см. скриншот 2)
Кликните здесь для просмотра всего текста
PHP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?php 
            $k = 1;//счетчик
            //массивы значений потребителей и складов
            $arr_sklad_opor = $arr_sklad;
            $arr_potreb_opor = $arr_potreb;
            for ($i = 1; $i <= count($arr_sklad_opor); $i++) {
                for ($j = $k; $j <= count($arr_potreb_opor); $j++) {
                    if ($arr_sklad_opor[$i]-$arr_potreb_opor[$j] >= 0) {//если потребности удовлетворены: 
                        $arr_opora[$j][$i] = $arr_potreb_opor[$j];//записываем потребность в массив
                        $arr_sklad_opor[$i] = $arr_sklad_opor[$i]-$arr_potreb_opor[$j];//считаем текущее количество единиц на складе
                        if ($arr_sklad_opor[$i] > 0) $k += 1;//если склад не пуст, используем следующего потребителя
                        if ($arr_sklad_opor[$i] == 0) {//если пуст, используем другой склад
                            $k += 1;
                            continue(2);
                        };
                    }
                    else {//если потребности не удовлетворены: 
                        $arr_opora[$j][$i] = $arr_sklad_opor[$i];//записываем количество единиц на складе в массив
                        $arr_potreb_opor[$j] = $arr_potreb_opor[$j]-$arr_sklad_opor[$i];//считаем текущую потребность
                        if ($arr_potreb_opor[$j] > 0) { continue(2); }//если имеется потребность, но склад пуст, используем другой
                            else $k += 1;
                    };
                };
            };
        ?>

Находим стоимость перевозок :
Кликните здесь для просмотра всего текста
PHP
1
2
3
4
5
6
for($i = 1; $i <= count($arr_sklad); $i++) {//находим стоимость перевозки для дальнейшей оптимизации
                for($j = 1; $j <= count($arr_potreb); $j++) {
                    $sum = $arr_opora[$i][$j] * $arr_perevozka[$i][$j];//умножаем соответствующие значения в массивах
                    $cost += $sum;//накапливаем сумму
                };
            };

Вот теперь переходим к методу потенциалов. Сначала необходимо найти a[i], b[i] - коэф(платежи потребителей и платежи складов):
Кликните здесь для просмотра всего текста
PHP
1
2
3
4
5
6
7
8
9
10
11
// Методом ПОТЕНЦИАЛОВ находим оптмальное решение
            $arr_a[1] = 0;//первый элемент a[i] равен 0
            for($i = 1; $i <= count($arr_potreb); $i++) {
                for($j = 1; $j <= count($arr_sklad); $j++) {
                    if (!empty($arr_opora[$i][$j])) {//вычисляем значения массива arr_b только в базисных ячейках
                        $arr_b[$j] = $arr_perevozka[$i][$j] - $arr_a[$i];//значение массива платежа b[i]
                        //вычисляем со второй строки, т.к. на первой a[i] = 0
                        $arr_a[$i+1] = $arr_perevozka[$i+1][$j] - $arr_b[$j];//находим остальные значение платежа a[i]
                    };
                };
            };

А после находим псевдостоимости, в левом верхнем углу ячеек таблицы(оранжевым цветом) (см. скриншот 3 ):
Кликните здесь для просмотра всего текста
PHP
1
2
3
4
5
6
//Находим псевдостоимость
            for($i = 1; $i <= count($arr_potreb); $i++) {
                for($j = 1; $j <= count($arr_sklad); $j++) {
                    $arr_perevozka_poten[$i][$j] = $arr_b[$j] + $arr_a[$i];
                };
            };

В итоге у меня получилось вот что (См. скриншот 3), пример взял из учебника(самый первый скриншот), поэтому данные совпадают. Осталась самая тяжелая часть: по контуру искать базисные ячейки, переписывая их значение для изменения общей стоимости перевозок. вот.
Чтобы было еще понятней, приложу проект.
Миниатюры
Оптимизация методом потенциалов   Оптимизация методом потенциалов   Оптимизация методом потенциалов  

Вложения
Тип файла: rar www.rar (25.9 Кб, 11 просмотров)
0
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 173
16.05.2015, 14:36  [ТС]
этот пример рассмотрен в книге(c. 99):
Вложения
Тип файла: rar Вентцель Е.С. Исследование операций.rar (4.39 Мб, 16 просмотров)
0
Заблокирован
16.05.2015, 15:45
Это что теория какая то?
начнём с начала рис. №1 по какой формуле выводятся цифра 10 на пересечении 17 и 25?

Дальше ясно ты их убираешь в угол (рис. №2) но опять не ясно по какой формуле выводятся цифра 17 на пересечении 17 и 25 с 10 в углу...
и почему на пересечении 17 и 32 с 5 в углу пустота?... тоже не ясно

Дальше. Наконец очевидна формула (рис. №3) это a[i]+b[i] по которой ты формируешь второй угол. Но опять не ясно что ты хочешь получить дальше.
0
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 173
16.05.2015, 22:29  [ТС]
Trukl,
Цитата Сообщение от Trukl Посмотреть сообщение
начнём с начала рис. №1 по какой формуле выводятся цифра 10 на пересечении 17 и 25?
10 и все остальные числа на скриншоте 1 вводятся самостоятельно через html - форму
Цитата Сообщение от Trukl Посмотреть сообщение
Дальше ясно ты их убираешь в угол (рис. №2) но опять не ясно по какой формуле выводятся цифра 17 на пересечении 17 и 25 с 10 в углу...
и почему на пересечении 17 и 32 с 5 в углу пустота?... тоже не ясно
Здесь по методу Северо-западного угла находится опорный план, посмотрите в этом учебнике(с.87), там на примере подробно описано, понятней я не смогу объяснить. По сути, моя задача - это компьютерная реализация метода Северо-западного угла и метода Потенциалов.
Цитата Сообщение от Trukl Посмотреть сообщение
Дальше. Наконец очевидна формула (рис. №3) это a[i]+b[i] по которой ты формируешь второй угол. Но опять не ясно что ты хочешь получить дальше.
Дальше мы оцениваем оптимальность этого опорного плана(скрин 2) плана. Что мы делаем: находим псевдостоимости(оранжевым цветом помечены) и отнимаем их от реальной стоимости(верхний правый угол ячеек). Если есть отрицательная разница при вычитании этих величин, то, используя метод потенциалов, переставляем значения базисных ячеек по контуру. В этом и проблема

Добавлено через 2 часа 57 минут
Даже не знаю, как цикл пересчета организовать.
0
Заблокирован
16.05.2015, 23:07
Цитата Сообщение от Beezy Посмотреть сообщение
10 и все остальные числа на скриншоте 1 вводятся самостоятельно через html - форму
а на кой ляд там тогда цифры сверху и сбоку таблицы?
Цитата Сообщение от Beezy Посмотреть сообщение
Здесь по методу Северо-западного угла находится опорный план, посмотрите в этом учебнике(с.87), там на примере подробно описано, понятней я не смогу объяснить.
формула у тебя есть? лично мне учебник читать в лом, из всего этого учебника мне нужна для работы только формула.
Цитата Сообщение от Beezy Посмотреть сообщение
Дальше мы оцениваем оптимальность этого опорного плана(скрин 2) плана.
что опять вручную? формулы опять нету?
Цитата Сообщение от Beezy Посмотреть сообщение
Что мы делаем: находим псевдостоимости(оранжевым цветом помечены) и отнимаем их от реальной стоимости(верхний правый угол ячеек)
это как раз просто.
Цитата Сообщение от Beezy Посмотреть сообщение
Если есть отрицательная разница при вычитании этих величин, то, используя метод потенциалов
я у тя долго буду формулы клянчить?
Цитата Сообщение от Beezy Посмотреть сообщение
переставляем значения базисных ячеек по контуру
что значит по контуру? Будь проще никто в твою терминологию вникать не будет.
0
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 173
16.05.2015, 23:22  [ТС]
Trukl, если не вникнуть в этот метод, не получится сделать, я не смогу нормально объяснить
0
Заблокирован
17.05.2015, 00:07
Цитата Сообщение от Beezy Посмотреть сообщение
если не вникнуть в этот метод, не получится сделать, я не смогу нормально объяснить
Ясно. Значит формул у тя нет. И просишь ты тут не решение на PHP а сам алгоритм. С этем я думаю, возникнут проблемы. Хотя чем чёрт не шутит вдруг занесёт кого, кто в теме.
0
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 173
17.05.2015, 09:33  [ТС]
Я немного сбился с курса, метод потенциалов реализовать не могу, там как таковых формул нет.
Вот конкретная ситуация из моей задачи. Я нашел ячейку, где разница между стоимостями и псевдостоимостями будет минимальна. В данном случае, это ячейка 2.1(см. скриншот). Т.е. необходимо от стартовой ячейки очертить фигуру с вершинами в базисных ячейках(те, в которых есть числа). У меня все эти числа забиты в массивы, а не знаю как подступиться, как начать движение.
Миниатюры
Оптимизация методом потенциалов  
0
0 / 0 / 0
Регистрация: 14.09.2014
Сообщений: 173
17.05.2015, 13:07  [ТС]
Нашел ту самую минимальную точку(старт), от которой нужно двигаться, как теперь цикл оформить?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
17.05.2015, 13:07
Помогаю со студенческими работами здесь

Оптимизация методом Ньютона (нахождение точки минимума). Оптимизация кода
MATLAB только начал осваивать. Попытался реализовать нахождение точки минимума методом Ньютона для функции 2*X12 - X1*X2 + 3*X22 -...

Транспортная задача (методом потенциалов)
Доброго времени суток форумчане! Нужна прога по вычислению транспортной задачи методом потенциалов. Пытался сам сделать, но как-то не...

Задача методом узловых потенциалов
Здравствуйте,извиняюсь,что так часто прошу помощи,но у меня вопрос по задаче снова. Нужно решить задачу методом узловых потенциалов,схему...

Транспортная задача (методом потенциалов)
В универе задали сделать транспортную задачу. Знания только одного семестра ОП. Сделал заполнение таблицы поиск потенциала и проверку...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
Команды "Заполнить" и "Очистить" на форме документа
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". На примере нетипового документа разработанного в конфигурации КА2. В качестве источника данных указан регистр накопления, в который записываются данные о. . .
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при изменении наименования справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++
8Observer8 24.03.2026
Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip
Жизнь в неопределённости
kumehtar 23.03.2026
Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения.
anaschu 23.03.2026
geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru