Транспортная задача (методом потенциалов) - C++ - Ответ 7685587

@Hikezp · Регистрация: 03.10.2014

Студворк — интернет-сервис помощи студентам

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

условие было матрица 4х4
коэффициенты матрицы
1 3 3 4
5 2 7 5
6 4 8 2
7 1 5 7

a= 50 20 30 20
b= 40 30 35 15

Матрица заполняется методом двойного предпочтения
40 0 30 0
0 10 10 0
0 0 15 15
0 20 0 0

потом находятся потенциалы v={1,-2,3,-3} u={0,4,5,3}
проверяется условие для пустых клеток U[i]+V[j]<=C[i][j]
в клеточке {3,2} условие не выполняется ( 3+3 <= 5)

в этой точке надо условно поставить + а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Должно получится
{3,2 +} {3,1 -} {1,1 +} {1,2 -}
Из MATRij стоящих в минусовых клетках, выбираем наименьшее, т.е. min (1, 2) = 10 и матрица будет выглядеть так
40 0 30 0
0 20 0 0
0 0 15 15
0 10 10 0

C++

#include <cstdlib>
#include <iostream>
#include <math.h>
using namespace std;
 
int main(int argc, char *argv[])
{
    setlocale( LC_ALL,"Russian" );
    int n,m,F=0,min2=0;
    int min,i,j,sum_a=0,sum_b=0,ind_i=0,ind_j=0;
    cout<<"Количество строк: ";
    cin>>n;
    cout<<"Количество столбцов: ";
    cin>>m;
    int u[n],v[m];
    int matr[m][n];
    int matr_ind[m][n];
    int matr_pm[m][n];
    int matr_koef[m][n];
    int a[n];
    int b[m];
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
    matr_ind[i][j]=0;
    matr_pm[i][j]=0;
}
}
    for(i=0;i<n;i++)
    {
    u[i]=100;
}
    for(j=0;j<m;j++)
    {
    v[j]=100;
}
    cout<<"Коэф матрицы"<<"\n";
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    cin>>matr_koef[i][j];
}
    cout<<"введите a:"<<"\n";
    for(i=0;i<m;i++)
    cin>>a[i];
    cout<<"введите  b:"<<"\n";
    for(i=0;i<n;i++)
    cin>>b[i];
    for(i=0;i<m;i++)
    sum_a+=a[i];
    for(i=0;i<n;i++)
    sum_b+=b[i];
    if(sum_a==sum_b)
    {
     cout<<"матрица сходится";
     cout<<"\n";
     }              
    if(sum_a>sum_b)
    {
     cout<<"матрица не сходится";
     system("PAUSE");
     return EXIT_SUCCESS;
     }
    if(sum_a<sum_b)
    {
     cout<<"матрица не сходится";
     system("PAUSE");
     return EXIT_SUCCESS;
     }
    cout<<"\n";
    
    for(i=0;i<n;i++)
    {
    min = 500;
    for(j=0;j<m;j++)
    {
    if(matr_koef[i][j]<min)
    {
    min=matr_koef[i][j];
    ind_i=i;
    ind_j=j;
    }
    }
    matr_ind[ind_i][ind_j]++;
    }
 
    for(j=0;j<m;j++)
    {
    min=500;
    for(i=0;i<n;i++)
    {
    if(matr_koef[i][j]<min)
    {
    min=matr_koef[i][j];
    ind_i=i;
    ind_j=j;
    }
    }
    matr_ind[ind_i][ind_j]++;
    }
    
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
        if(matr_ind[i][j]==2)
        if(a[i]>=b[j])
        {
        matr[i][j]=a[i]-(a[i]-b[j]);
        a[i]=a[i]-b[j];
        b[j]=0;
        }
        else
        {
        matr[i][j]=b[j]-(b[j]-a[i]);
        b[j]=b[j]-a[i];
        a[i]=0;
        }
    }
    }
    
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
        if(matr_ind[i][j]==1)
        if(a[i]>=b[j])
        {
        matr[i][j]=a[i]-(a[i]-b[j]);
        a[i]=a[i]-b[j];
        b[j]=0;
        }
        else
        {
        matr[i][j]=b[j]-(b[j]-a[i]);
        b[j]=b[j]-a[i];
        a[i]=0;
        }
    }
    }
    
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
        if(matr_ind[i][j]==0)
        if(a[i]>=b[j])
        {
        matr[i][j]=a[i]-(a[i]-b[j]);
        a[i]=a[i]-b[j];
        b[j]=0;
        }
        else
        {
        matr[i][j]=b[j]-(b[j]-a[i]);
        b[j]=b[j]-a[i];
        a[i]=0;
        }
    }
    }
    
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
    cout<<matr[i][j]<<" ";
    }
    cout<<"\n";
    }
    
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
    F+=matr[i][j]*matr_koef[i][j];
    }
    }
    cout<<"F(x)="<<F<<"\n";
    
    u[0]=0;
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
                    if((matr[i][j]!=0)&&(v[j]==100)&(u[i]!=100))
                    {
                                     v[j]=matr_koef[i][j]-u[i];
                                     }
                    if((matr[i][j]!=0)&&(v[j]!=100)&(u[i]==100))
                    {
                                     u[i]=matr_koef[i][j]-v[j];
                                     }
                                     }
                                     }                                                              
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
                    if((u[i]==100)&&(v[j]!=100)&&(matr[i][j]!=0))
                    u[i]=matr_koef[i][j]-v[j];
                    if((u[i]!=100)&&(v[j]==100)&&(matr[i][j]!=0))
                    v[j]=matr_koef[i][j]-u[i];
                    }
                    }
    cout<<"Потенциал V:";
    for(i=0;i<n;i++)
    {
    cout<<v[i]<<" ";
}
    cout<<"\n"<<"Потенциал U:";
    for(j=0;j<m;j++)
    {
    cout<<u[j]<<" ";
}
    cout<<"\n";
    
    for(i=0;i<n;i++)
    {
    for(j=0;j<m;j++)
    {
                    if((matr[i][j]==0)&&(u[i]+v[j]-matr_koef[i][j]>0.1))
                    {
                    cout<<"Опорный план является не оптимальным в строке "<<i<<" и в столбце "<<j<<"\n";
                    matr_pm[i][j]++;
                    }
                    }
                    }             
    system("PAUSE");
    return EXIT_SUCCESS;
}

Вернуться к обсуждению:
Транспортная задача (методом потенциалов) C++

Следующий ответ

Другие темы раздела
C++ Потоки в C++ Господа, можете посоветовать хорошую книгу по потокам в C++ или мануалы какие-то что ли ? Не советуйте материал найденный в поисковике, посоветуйте то чем пользовались или проверяли. Не предлагайте... https://www.cyberforum.ru/ cpp-beginners/ thread1461690.html	C++ Составить алгоритм и программу, которые формируют список фамилий рабочих Помогите, будьте так добры. Известны фамилии и месячные заработки 10 рабочих бригады в течение года. Составить алгоритм и программу, которые формируют список фамилий рабочих, имевших хотя бы раз...
C++ Получить двоичную матрицу с единицами на главных диагоналях Получить матрицу: 1 0 ... 0 1 0 1 ... 1 0 . . ... . . 0 1 ... 1 0 1 0 ... 0 1 https://www.cyberforum.ru/ cpp-beginners/ thread1461680.html	C++ Дописать код - уничтожить N элементов, начиная с номера K в динамическом массиве https://www.cyberforum.ru/ cpp-beginners/ thread1461677.html Мне нужно использовать именно динамические массивы. У меня создается массив, удаляется, но как в коде написать алгоритм удаления N чисел, начиная с номера К? Помогите #include "stdafx.h"...
C++ Библиотека для обработки звукового сигнала Добрый вечер, уважаемые форумчане. Меня интересует написание программы Осциллографа на базе звуковой карты. Для себя я вывел основные этапы работы. И в самом начале у меня возникла загвоздка....	C++ Перевод из int в LPTSTR https://www.cyberforum.ru/ cpp-beginners/ thread1461657.html вот функция WriteSlot BOOL WriteSlot(HANDLE hSlot, LPTSTR lpszMessage) { BOOL fResult; DWORD cbWritten; fResult = WriteFile(hSlot, lpszMessage, ...
C++ Как вывести отдельную строку? // PR7.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include <locale.h> #include <stdlib.h> #include <stdio.h> #include <iostream> #include <cstdlib>... https://www.cyberforum.ru/ cpp-beginners/ thread1461626.html	C++ Простой сервер С++ для обработки HTTP запросов Здравствуйте, недавно начал изучать с++.Стала задача поставить сервер под linox. Может кто-то скинуть нормальную статью, или пример сервера с некоторым описанием.
C++ Написать программу, в которой задана произвольная функция вызывается из функции main () https://www.cyberforum.ru/ cpp-beginners/ thread1461591.html 5. Написать программу, в которой задана произвольная функция вызывается из функции main ().	C++ Написать программу, которая выводит на экран среднее арифметическое введенных положительных чисел 4. Написать программу, которая выводит на экран среднее арифметическое введенных положительных чисел, количество которых произвольная. https://www.cyberforum.ru/ cpp-beginners/ thread1461590.html
Написать программу, которая преобразует введен в минутах интервал времени в интервал в часах и минутах C++ 3. Написать программу, которая преобразует введен в минутах интервал времени в интервал в часах и минутах.	C++ Написать программу, которая выводит на экран четверостишие (произвольный), все строки которого разного цвета 2. Написать программу, которая выводит на экран четверостишие (произвольный), все строки которого разного цвета. https://www.cyberforum.ru/ cpp-beginners/ thread1461588.html