6.4. Решение задачи симплекс-методом
Приведём задачу к канонической форме:
max z = | 15 x1 | +10 x2 | +8 x3 | +2 x4 | +0 s1 | +0 s2 | +0 s3 | +0 s4 |
|
| x1 | + 4 x2 | + x3 | +5 x4 | + s1 |
|
|
| =70 |
| 3 x1 | + 2 x2 | + 3 x3 | + 5 x4 |
| + s2 |
|
| =80 |
| 2 x1 | + 3 x2 |
| + 4 x4 |
|
| - s3 |
| =25 |
| x1 |
| + x3 | + x 4 |
|
|
| - s4 | =10 |
| 2 x1 | - x2 | + x3 |
|
|
|
|
| =0 |
| x1, | x2, | x3, | x4, | s1, | s2, | s3, | s4 | 0 |
В таблицах 6.2 – 6.9 приведены результаты итераций решения задачи табличным двухэтапным симплекс-методом. В табл. 6.2 – 6.7 представлены результаты реализации этапа I, а в табл. 6.8 -.6.9 - результаты реализации этапа II.
Таблица 6.2
Б.п. | x1 | x2 | x3 | x4 | s1 | s2 | s3 | s4 | R1 | R2 | R3 | Реш. |
r (min) | 5 | 2 | 2 | 5 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 35 |
z (max) | -15 | -10 | -8 | -2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
s1 | 1 | 4 | 1 | 5 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 70 |
s2 | 3 | 2 | 3 | 5 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 80 |
R1 | 2 | 3 | 0 | 4 | 0 | 0 | -1 | 0 | 1 | 0 | 0 | 25 |
R2 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | -1 | 0 | 1 | 0 | 10 |
R3 | 2 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Таблица 6.3
Б.п. | x1 | x2 | x3 | x4 | s1 | s2 | s3 | s4 | R1 | R2 | R3 | Реш. |
r (min) | 0 | 9/2 | -1/2 | 5 | 0 | 0 | -1 | -1 | 0 | 0 | -5/2 | 35 |
z (max) | 0 | -35/2 | -1/2 | -2 | 0 | 0 | 0 | 0 | 0 | 0 | 15/2 | 0 |
s1 | 0 | 9/2 | 1/2 | 5 | 1 | 0 | 0 | 0 | 0 | 0 | -1/2 | 70 |
s2 | 0 | 7/2 | 3/2 | 5 | 0 | 1 | 0 | 0 | 0 | 0 | -3/2 | 80 |
R1 | 0 | 4 | -1 | 4 | 0 | 0 | -1 | 0 | 1 | 0 | -1 | 25 |
R2 | 0 | 1/2 | 1/2 | 1 | 0 | 0 | 0 | -1 | 0 | 1 | -1/2 | 10 |
x1 | 1 | -1/2 | 1/2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1/2 | 0 |
Таблица 6.4
Б.п. | x1 | x2 | x3 | x4 | s1 | s2 | s3 | s4 | R1 | R2 | R3 | Реш. |
r (min) | 0 | -1/2 | 3/4 | 0 | 0 | 0 | 1/4 | -1 | -5/4 | 0 | -5/4 | 15/4 |
z (max) | 0 | -31/2 | -1 | 0 | 0 | 0 | -1/2 | 0 | 1/2 | 0 | 7 | 25/2 |
s1 | 0 | -1/2 | 7/4 | 0 | 1 | 0 | 5/4 | 0 | -5/4 | 0 | 3/4 | 155/4 |
s2 | 0 | -3/2 | 11/4 | 0 | 0 | 1 | 5/4 | 0 | -5/4 | 0 | -1/4 | 195/4 |
x4 | 0 | 1 | -1/4 | 1 | 0 | 0 | -1/4 | 0 | 1/4 | 0 | -1/4 | 25/4 |
R2 | 0 | -1/2 | 3/4 | 0 | 0 | 0 | 1/4 | -1 | -1/4 | 1 | -1/4 | 15/4 |
x1 | 1 | -1/2 | 1/2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1/2 | 0 |
Таблица 6.5
Б.п. | x1 | x2 | x3 | x4 | s1 | s2 | s3 | s4 | R1 | R2 | R3 | Реш. |
r (min) | -3/2 | 1/4 | 0 | 0 | 0 | 0 | 1/4 | -1 | -5/4 | 0 | -2 | 15/4 |
z (max) | 2 | -33/2 | 0 | 0 | 0 | 0 | -1/2 | 0 | 1/2 | 0 | 8 | 25/2 |
s1 | -7/2 | 5/4 | 0 | 0 | 1 | 0 | 5/4 | 0 | -5/4 | 0 | -1 | 155/4 |
s2 | -11/2 | 5/4 | 0 | 0 | 0 | 1 | 5/4 | 0 | -5/4 | 0 | -3 | 195/4 |
x4 | 1/2 | 3/4 | 0 | 1 | 0 | 0 | -1/4 | 0 | 1/4 | 0 | 0 | 25/4 |
R2 | -3/2 | 1/4 | 0 | 0 | 0 | 0 | 1/4 | -1 | -1/4 | 1 | -1 | 15/4 |
x3 | 2 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
Таблица 6.6
Б.п. | x1 | x2 | x3 | x4 | s1 | s2 | s3 | s4 | R1 | R2 | R3 | Реш. |
r (min) | -5/3 | 0 | 0 | -1/3 | 0 | 0 | 1/3 | -1 | -4/3 | 0 | -2 | 5/3 |
z (max) | 13 | 0 | 0 | 22 | 0 | 0 | -6 | 0 | 6 | 0 | 8 | 150 |
s1 | -13/3 | 0 | 0 | -5/3 | 1 | 0 | 5/3 | 0 | -5/3 | 0 | -1 | 85/3 |
s2 | -19/3 | 0 | 0 | -5/3 | 0 | 1 | 5/3 | 0 | -5/3 | 0 | -3 | 115/3 |
x2 | 2/3 | 1 | 0 | 4/3 | 0 | 0 | -1/3 | 0 | 1/3 | 0 | 0 | 25/3 |
R2 | -5/3 | 0 | 0 | -1/3 | 0 | 0 | 1/3 | -1 | -1/3 | 1 | -1 | 5/3 |
x3 | 8/3 | 0 | 1 | 4/3 | 0 | 0 | -1/3 | 0 | 1/3 | 0 | 1 | 25/3 |
Таблица 6.7
Б.п. | x1 | x2 | x3 | x4 | s1 | s2 | s3 | s4 | R1 | R2 | R3 | Реш. |
r (min) | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | -1 | 0 |
z (max) | -17 | 0 | 0 | 16 | 0 | 0 | 0 | -18 | 0 | 18 | -10 | 180 |
s1 | 4 | 0 | 0 | 0 | 1 | 0 | 0 | 5 | 0 | -5 | 4 | 20 |
s2 | 2 | 0 | 0 | 0 | 0 | 1 | 0 | 5 | 0 | -5 | 2 | 30 |
x2 | -1 | 1 | 0 | 1 | 0 | 0 | 0 | -1 | 0 | 1 | -1 | 10 |
s3 | -5 | 0 | 0 | -1 | 0 | 0 | 1 | -3 | -1 | 3 | -3 | 5 |
x3 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | -1 | 0 | 1 | 0 | 10 |
Так как нашей целью является проведение постоптимального анализа модели, то искусственные переменные, вышедшие из базиса, из модели исключать не надо – в дальнейшем нам понадобятся все столбцы оптимальной симплекс-таблицы. В таблицах следующих итераций коэффициенты z-строки при искусственных переменных не считаем, так как при использовании двухэтапного метода (в отличие от М-метода) на втором этапе эти коэффициенты не имеют смысла.
Таблица 6.8
Б.п. | x1 | x2 | x3 | x4 | s1 | s2 | s3 | s4 | R1 | R2 | R3 | Реш. |
z (max) | -13/5 | 0 | 0 | 16 | 18/5 | 0 | 0 | 0 |
|
|
| 252 |
s4 | 4/5 | 0 | 0 | 0 | 1/5 | 0 | 0 | 1 | 0 | -1 | 4/5 | 4 |
s2 | -2 | 0 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | -2 | 10 |
x2 | -1/5 | 1 | 0 | 1 | 1/5 | 0 | 0 | 0 | 0 | 0 | -1/5 | 14 |
s3 | -13/5 | 0 | 0 | -1 | 3/5 | 0 | 1 | 0 | -1 | 0 | -3/5 | 17 |
x3 | 9/5 | 0 | 1 | 1 | 1/5 | 0 | 0 | 0 | 0 | 0 | 4/5 | 14 |
Таблица 6.9
Б.п. | x1 | x2 | x3 | x4 | s1 | s2 | s3 | s4 | R1 | R2 | R3 | Реш. |
z (max) | 0 | 0 | 0 | 16 | 17/4 | 0 | 0 | 13/4 |
|
|
| 265 |
x1 | 1 | 0 | 0 | 0 | 1/4 | 0 | 0 | 5/4 | 0 | -5/4 | 1 | 5 |
s2 | 0 | 0 | 0 | 0 | -1/2 | 1 | 0 | 5/2 | 0 | -5/2 | 0 | 20 |
x2 | 0 | 1 | 0 | 1 | 1/4 | 0 | 0 | 1/4 | 0 | -1/4 | 0 | 15 |
s3 | 0 | 0 | 0 | -1 | 5/4 | 0 | 1 | 13/4 | -1 | -13/4 | 2 | 30 |
x3 | 0 | 0 | 1 | 1 | -1/4 | 0 | 0 | -9/4 | 0 | 9/4 | -1 | 5 |
Итак: z=265, x1=5, x2=15, x3=5, x4=0.
- Содержание
- 1. Порядок выполнения расчетно-графической работы
- Решение задачи симплекс-методом.2
- 2. Содержание отчета по расчетно-графической работе
- Планирование операции
- Содержательная постановка задачи.
- Решение задачи симплекс-методом.
- 3. Варианты заданий расчетно-графической работы
- 3.1. Задания на планирование операции
- 3.2. Задания на применение графического способа решения задач линейного программирования
- 4. Электронная таблица Microsoft Excel
- 4.1. Терминология Excel
- 4.3.6. Ввод чисел или текста
- Ввод текста
- Ввод чисел
- Ввод дат или времени суток
- 4.3.7. Формулы
- 5. Решение задачи линейного программирования средствами Microsoft Excel
- 5.1. Содержательная формулировка задачи Задача определения ассортимента выпуска продукции [3]
- 5.2. Математическая формулировка задачи
- Суммарное время Предельное время
- 5.3. Решение задачи с помощью Microsoft Excel
- Содержимое ячеек таблицы:
- 5.4. Нахождение оптимального решения с помощью процедуры поиска решения
- 5.5. Итоговые сообщения процедуры поиска решения
- 6. Постоптимальный анализ задач линейного программирования
- 6.1. Содержательная постановка задачи
- 6.2. Математическая модель
- 6.3. Решение с помощью Microsoft Excel
- 6.4. Решение задачи симплекс-методом
- 6.5. Определение ценности ресурсов
- Прямая задача:
- В нашей задаче:
- 6.6.1.2. Дефицитные ресурсы Теоретические сведения
- В нашей задаче:
- Теоретические сведения:
- В нашей задаче:
- 6.6.2. Изменение коэффициентов целевой функции
- 6.6.2.1. Небазисные переменные Теоретические сведения
- 6.6.2.2. Базисные переменные Теоретические сведения
- В нашей задаче:
- 6.6.3. Результаты решения и постоптимального анализа задачи
- 6.6.3.1. Оптимальное решение задачи
- 6.6.3.2. Диапазоны изменения уровня запасов ресурсов
- 6.6.3.3. Ценность ресурсов
- 6.6.3.4. Диапазоны изменения цен продукции
- 6.6.4. Некоторые особенности проведения постоптимального анализа задач средствами Excel
- 6.6.4.1. Наличие ограничений типа или
- 6.6.4.2. Наличие альтернативных оптимумов
- Список литературы
- Приложение а Основные положения теории двойственности а.1. Построение двойственных задач
- А.2. Основные теоремы двойственности
- А.3. Получение решения задачи по решению двойственной задачи