М-метод - История изменений

Logic-samara в 18:16, 2 февраля 2016

2016-02-02T18:16:00Z

Logic-samara в 18:15, 2 февраля 2016

2016-02-02T18:15:23Z

Logic-samara в 18:12, 2 февраля 2016

2016-02-02T18:12:28Z

Logic-samara в 05:45, 14 января 2016

2016-01-14T05:45:46Z

Logic-samara в 05:39, 14 января 2016

2016-01-14T05:39:19Z

Ws: Восстановление статей Logic-samara

2015-11-15T15:05:52Z

Восстановление статей Logic-samara

Новая страница

[[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]]
[[файл:ММ01.JPG|thumb|300|Математическая модель эквивалентной КЗ]]
== Определение ==
'''M-метод''' — метод решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.

Суть '''M'''-метода состоит в построении с помощью искусственных переменных эквивалентной задачи с базисом, а затем решении её [[симплекс-метод]]ом.

== [[Каноническая задача]] ==
Математическая модель канонической задачи имеет следующий вид:

[[файл:СМ01.JPG]]

или

[[файл:СМ02.JPG]]

== Постановка эквивалентной задачи ==
Для решения задачи канонического вида необходимо составить эквивалентную задачу. Введём новые (искусственные) переменные '''x<sub>j</sub>''' – остатки ресурсов '''(j-n)'''-го ограничения, '''j=n+1,n+2,…,n+m'''. Добавим эти переменные к соответствующим ограничениям и введём их в целевую функцию с отрицательным коэффициентом '''-M''', где '''M''' – очень большое положительное число.

Математическая модель эквивалентной задачи принимает следующий вид:

[[файл: ММ01.JPG]].

или

[[файл:ММ02.JPG]]

== Метод решения ==
Эквивалентная задача решается [[симплекс-метод]]ом.

Начальная симплекс-таблица для эквивалентной задачи имеет вид:

[[файл:ММ03.JPG]]

Если оптимальное значение целевой функции эквивалентной задачи не содержит '''M'''-множителей, то получено оптимальное решение, которое при отбрасывании искусственных переменных совпадает с оптимальным решением исходной задачи канонического вида.
В случае если оптимальное значение целевой функции эквивалентной задачи содержит '''M'''-множители, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений.

== Другие методы: ==
*[[Симплекс-метод]];
*[[Метод искусственного базиса]].

== Ссылки ==
* Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
* [[Участник:Logic-samara]]
[[Категория:Линейное программирование]]

@@ Строка 34: / Строка 34: @@
 *[[симплекс-метод]];
 *[[метод искусственного базиса]];
-*[[M-метод]].
+*[[М-метод]].
 == Ссылки ==
 * Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
 * [[Участник:Logic-samara]]
 [[Категория:Линейное программирование]]

@@ Строка 31: / Строка 31: @@
 Если оптимальное значение целевой функции эквивалентной задачи не содержит '''M'''-множителей, то получено оптимальное решение, которое при отбрасывании искусственных переменных совпадает с оптимальным решением исходной задачи канонического вида.
 В случае если оптимальное значение целевой функции эквивалентной задачи содержит '''M'''-множители, то это означает несовместность системы ограничений исходной задачи канонического вида и отсутствие допустимых решений.
-== Другие алгоритмы: ==
+== Другие методы: ==
 *[[симплекс-метод]];
 *[[метод искусственного базиса]];
-*[[М-метод]];
+*[[M-метод]].
-*[[алгоритм северо-западного угла]];
-*[[алгоритм расчёта потенциалов]];
-*[[алгоритм перераспределения перевозок]];
-*[[алгоритм решения ТЗПП с запретами]];
-*[[алгоритм расчёта потенциалов для ТТЗ]];
-*[[алгоритм перераспределения перевозок для ТТЗ]].
 == Ссылки ==
 * Юдин Д. Б., Гольштейн Е. Г. Линейное программирование., М.,1963.
 * [[Участник:Logic-samara]]
 [[Категория:Линейное программирование]]

@@ Строка 1: / Строка 1: @@
 [[файл:СМ01.JPG|thumb|300|[[Математическая модель]] КЗ]]
 [[файл:ММ01.JPG|thumb|300|Математическая модель эквивалентной КЗ]]
-'''M-метод''' — метод решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.
+'''M-метод''' — это метод решения задач линейного программирования канонического вида, т.е. задач с ограничениями в форме равенств.
 == Описание метода ==
 Суть '''M'''-метода состоит в построении с помощью искусственных переменных эквивалентной задачи с базисом, а затем решении её [[симплекс-метод]]ом.