当前位置:   article > 正文

C : 线性规划例题求解

C : 线性规划例题求解

Submit Page   TestData   Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 93     Solved: 49    


Description

求解下述线性规划模型的最优值min �1�1+�2�2+�3�3�.�. �11�1+�12�2+�13�3≤�1>0�21�1+�22�2+�23�3≤�2>0�31�1+�32�2+�33�3≤�3>0�1,�2,�3≥0

Input

依次输入�1�2�3�11�12�13�1�21�22�23�2�31�32�33�3

Output

目标函数最优值,保留小数点后两位有效数字。若无最优解,输出“No solution”。

Sample

#0
Input

Copy

1 -2 0
1 -1 0 1
-2 1 0 4
1 1 1 10
Output

Copy

-14.00

Hint

  1. #include <iostream>
  2. #include <cmath>
  3. #include "stdio.h"
  4. using namespace std;
  5. #define M 10000
  6. double kernel[110][310];
  7. int m = 0, n = 0, t = 0;
  8. void input()
  9. {
  10. // cin >> n;
  11. // cin >> m;
  12. m = 3;
  13. n = 3;
  14. int i, j;
  15. // 初始化核心向量
  16. for (i = 0; i <= m + 1; i++)
  17. for (j = 0; j <= n + m + m; j++)
  18. kernel[i][j] = 0;
  19. for (i = 1; i <= n; i++)
  20. cin >> kernel[0][i];
  21. for (i = 1; i <= m; i++)
  22. {
  23. // cout<<" 不等式"<<i<<" ";
  24. for (j = 1; j <= n + 2; j++)
  25. {
  26. if (j == n + 1)
  27. {
  28. kernel[i][j] = 1;
  29. }
  30. else
  31. {
  32. cin >> kernel[i][j];
  33. }
  34. }
  35. }
  36. for (i = 1; i <= m; i++)
  37. {
  38. kernel[i][0] = kernel[i][n + 2];
  39. kernel[i][n + 2] = 0;
  40. }
  41. t = 1;
  42. if (t == -1)
  43. for (i = 1; i <= n; i++)
  44. kernel[0][i] = (-1) * kernel[0][i];
  45. for (i = 1; i <= m; i++)
  46. {
  47. kernel[i][n + i] = kernel[i][n + 1];
  48. if (i != 1)
  49. kernel[i][n + 1] = 0;
  50. }
  51. }
  52. // 算法函数
  53. void comput()
  54. {
  55. int i, j, flag, temp1, temp2, h, k = 0, temp3[100];
  56. double a, b[110], temp, temp4[110], temp5[110], f = 0, aa, d, c;
  57. for (i = 1; i <= m; i++)
  58. temp3[i] = 0.0000;
  59. for (i = 0; i < 11; i++)
  60. {
  61. temp4[i] = 0.000;
  62. temp5[i] = 0.0000;
  63. }
  64. for (i = 1; i <= m; i++)
  65. {
  66. if (kernel[i][n + i] == -1)
  67. {
  68. kernel[i][n + m + i] = 1;
  69. kernel[0][n + m + i] = M;
  70. temp3[i] = n + m + i;
  71. }
  72. else
  73. temp3[i] = n + i;
  74. }
  75. for (i = 1; i <= m; i++)
  76. temp4[i] = kernel[0][temp3[i]];
  77. do
  78. {
  79. for (i = 1; i <= n + m + m; i++)
  80. {
  81. a = 0;
  82. for (j = 1; j <= m; j++)
  83. a += kernel[j][i] * temp4[j];
  84. kernel[m + 1][i] = kernel[0][i] - a;
  85. }
  86. for (i = 1; i <= n + m + m; i++)
  87. {
  88. if (kernel[m + 1][i] >= 0)
  89. flag = 1;
  90. else
  91. {
  92. flag = -1;
  93. break;
  94. }
  95. }
  96. if (flag == 1)
  97. {
  98. for (i = 1; i <= m; i++)
  99. {
  100. if (temp3[i] <= n + m)
  101. temp1 = 1;
  102. else
  103. {
  104. temp1 = -1;
  105. break;
  106. }
  107. }
  108. if (temp1 == 1)
  109. {
  110. // cout << " 此线性规划的最优解存在!" << endl << endl << " 最优解为:" << endl << endl << " ";
  111. for (i = 1; i <= m; i++)
  112. temp5[temp3[i]] = kernel[i][0];
  113. for (i = 1; i <= n; i++)
  114. f += t * kernel[0][i] * temp5[i];
  115. for (i = 1; i <= n; i++)
  116. {
  117. // cout << "x" << i << " = " << temp5[i];
  118. // if (i != n)
  119. // cout << ", ";
  120. }
  121. // cout << " ;" << endl << endl << " 最优目标函数值f= " << f << endl << endl;
  122. printf("%.2f\n", f);
  123. return;
  124. }
  125. else
  126. {
  127. // cout << " 此线性规划无解" << endl << endl;
  128. cout<<"No solution"<<endl;
  129. return;
  130. }
  131. }
  132. if (flag == -1)
  133. {
  134. temp = 100000;
  135. for (i = 1; i <= n + m + m; i++)
  136. if (kernel[m + 1][i] < temp)
  137. {
  138. temp = kernel[m + 1][i];
  139. h = i;
  140. }
  141. for (i = 1; i <= m; i++)
  142. {
  143. if (kernel[i][h] <= 0)
  144. temp2 = 1;
  145. else
  146. {
  147. temp2 = -1;
  148. break;
  149. }
  150. }
  151. }
  152. if (temp2 == 1)
  153. {
  154. cout<<"No solution"<<endl;
  155. // cout << "此线性规划无约束";
  156. return;
  157. }
  158. if (temp2 == -1)
  159. {
  160. c = 100000;
  161. for (i = 1; i <= m; i++)
  162. {
  163. if (kernel[i][h] != 0)
  164. b[i] = kernel[i][0] / kernel[i][h];
  165. if (kernel[i][h] == 0)
  166. b[i] = 100000;
  167. if (b[i] < 0)
  168. b[i] = 100000;
  169. if (b[i] < c)
  170. {
  171. c = b[i];
  172. k = i;
  173. }
  174. }
  175. temp3[k] = h;
  176. temp4[k] = kernel[0][h];
  177. d = kernel[k][h];
  178. for (i = 0; i <= n + m + m; i++)
  179. kernel[k][i] = kernel[k][i] / d;
  180. for (i = 1; i <= m; i++)
  181. {
  182. if (i == k)
  183. continue;
  184. aa = kernel[i][h];
  185. for (j = 0; j <= n + m + m; j++)
  186. kernel[i][j] = kernel[i][j] - aa * kernel[k][j];
  187. }
  188. }
  189. } while (1);
  190. return;
  191. }
  192. int main()
  193. {
  194. input();
  195. for (int i = 1; i < n; i++)
  196. {
  197. for (int j = 1; j < m + 2; j++)
  198. {
  199. // cout<<kernel[i][j]<<" ";
  200. }
  201. // cout<<endl;
  202. }
  203. comput();
  204. // int a = 0;
  205. // scanf("%d", &a);
  206. // cout<<f<<endl;
  207. return 0;
  208. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/代码探险家/article/detail/775191
推荐阅读
相关标签
  

闽ICP备14008679号