Министерство образования РФ
1 Дайте определение опорного плана задачи линейного программирования.
2 В чем заключается идея симплекс-метода?
3 Как строится симплексная таблица?
4 Сформулируйте критерий оптимальности симплексной таблицы.
5 Сформулируйте критерий допустимости симплексной таблицы.
6 Сформулируйте правило выбора разрешающего элемента.
7 Сформулируйте признак неограниченности целевой функции (по симплексной таблице).
8 Может ли задача линейного программирования, удовлетворяющая условиям, перечисленным в разделе 3.2, быть неразрешимой по причине того, что ее ОДП пуста?
9 Если критерий оптимальности нарушен в нескольких столбцах, в чем заключается способ выбора разрешающего столбца, при котором решение может быть получено быстрее?
10 Нельзя ли найти способ (и в чем он заключается) определения по заключительной симплексной таблице того, является ли полученное решение единственным?
11 Решите симплекс-методом следующие задачи:
Пример 1.
max -4х1 + 3х2 - 3х3
-2х1 + х2 + х3 = 1
х1 - 3х2 - х4 = -13
4х1 + х2 + х5 = 26
-х1 - 3х2 ³ -6
х1-5 ³ 0
| Пример 2.
min -3х2 + 2х3
4х1 + 10х2 - 5х3 £ 7
0,5х1 - 3х2 + х4 = 4
3х1 +12х2 - 8х3 £ 3
х1-4 ³ 0
| Пример 3.
max 5х2 - 2х4
4х1 + 10х2 - 5х3 £ 7
х1 - 3х2 + 2х3 + х4 ³ 4
3х1 - 8х2 £ 12
х1-4 ³ 0
| Пример 4.
max 2х1 + х2 - х3 + 5х4
х1 + 7х2 + х3 + 7х4 £ 46
4х1 - х2 + х3 + 2х4 £ 8
2х1 + 3х2 - х3 + х4 £10
х1-4 ³ 0
| 12 Решите симплекс-методом задачу 9 из раздела 1.5.
* Симплекс представляет собой выпуклую оболочку m+1 аффинно независимых точек в m-мерном пространстве (т.е. пересечение всех выпуклых множеств, содержащих эти точки). Не приводя здесь определение аффинной независимости, ограничимся утвержением, что в m-мерном пространстве таких точек может быть не больше m+1. Можно сказать, что любой треугольник на плоскости (в двумерном пространстве) - симплекс.
Название метода связано с тем, что изначально он был разработан для задачи, ОДП которой представляло собой так называемый стандартный симплекс (определялось ограничениями; xi ³ 0, i=1,n). На плоскости это треугольник с вершиной в начале координат и точках (0;1) и (1;0).
* Вектора А1... Аn называются линейно независимыми, если не существует таких чисел d1... dn, не равных одновременно нулю, при которых djАj = 0.
* Число сочетаний из n по m рассчитывается по формуле.
* Знак $ при вводе формул в Microsoft Excel означает абсолютную ссылку. В дальнейшем при копировании формулы номер столбца или строки, перед которыми стоит этот знак, не будет изменяться.
Министерство образования РФ
Дата добавления: 2015-01-18 | Просмотры: 790 | Нарушение авторских прав
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |
|