Таблица 13 – Оптимальная симплексная таблица для задачи производственного планирования
|
N |
xб |
cб |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
|
1 |
x1 |
108 |
266,67 |
1 |
0 |
1,3333 |
0 |
-6,6667 |
|
2 |
x4 |
0 |
77,333 |
0 |
0 |
-0,2133 |
1 |
-2,9333 |
|
3 |
x2 |
140 |
1173,3 |
0 |
1 |
-0,1333 |
0 |
10,667 |
|
m+1 |
193067 |
0 |
0 |
125,33 |
0 |
773,33 |
Таблица оптимальна, так как в критериальной строке нет отрицательных коэффициентов. Из таблицы видно, что решением задачи будет Х* = (266,67; 1173,3; 0; 77,333; 0), z*=19306,7. Если изменить формат ячеек на дробный, то ответ совпадет с полученным в разделе 2.1.
Ответ задачи: кондитерской фабрике следует выпускать
266,7 т карамели
«Снежинка» и 1173,3 т
карамели «Яблочная». При этом сахарный песок и фруктовое пюре будут
израсходованы полностью (так как x3 = x5 =0), а остаток
патоки составит 77,3 т. Максимальная прибыль составит
193067 руб.
1 Дайте определение опорного плана задачи линейного программирования.
2 В чем заключается идея симплекс-метода?
3 Как строится симплексная таблица?
4 Сформулируйте критерий оптимальности симплексной таблицы.
5 Сформулируйте критерий допустимости симплексной таблицы.
6 Сформулируйте правило выбора разрешающего элемента.
7 Сформулируйте признак неограниченности целевой функции (по симплексной таблице).
8 Может ли задача линейного программирования, удовлетворяющая условиям, перечисленным в разделе 3.2, быть неразрешимой по причине того, что ее ОДП пуста?
9 Если критерий оптимальности нарушен в нескольких столбцах, в чем заключается способ выбора разрешающего столбца, при котором решение может быть получено быстрее?
10 Нельзя ли найти способ (и в чем он заключается) определения по заключительной симплексной таблице того, является ли полученное решение единственным?
11 Решите симплекс-методом следующие задачи:
|
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 |
|
max 5х2 - 2х4
х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 означает абсолютную ссылку. В дальнейшем при копировании формулы номер столбца или строки, перед которыми стоит этот знак, не будет изменяться.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.
Пример 1.
Пример 3.
4х1
+ 10х2 - 5х3 £ 7