Задача № 1

1. Присваиваем название листу 1 – Симплекс-метод.

2. В ячейке А1 введем Z = 3x₁ + 1x₂ max

3. В ячейке А3 введем 3х₁ + 2х₂ 40

1х₁ + 4х₂ 60

3х₁ + 0х₂ 120

4. В ячейке Е3 введем x₁ 0; x₂ 0

5. В ячейке А8 приведем уравнение к каноническому виду и запишем:

Z = 3x₁ + x₂ + 0 * х₃ +0 * х₄ + 0 * х₅ max

6. В ячейке А10 введем 3х₁ + 2х₂ + х₃ = 40

х₁ + 4х₂ + х₄ = 60

3х₁ + х₅ = 120

7. В ячейке Е10 введем х_j 0

8. Найдем первое базисное решение. х₁, х₂ – свободные переменные, то есть количество продукции 1-го и 2-го видов, х₃, х₄, х₅ – базисные переменные, то есть остатки ресурсов 1-го, 2-го, 3-го вида соответственно. Свободные переменные равны нулю, а базисные определяем из системы ограничений. Получаем х₁ = 0, х₂ = 0, х₃ = 40, х₄ = 60, х₅ = 120.

Запишем решение в виде вектора. х₁ = (0, 0, 40, 60, 120); Z₁ = 0. – значение целевой функции при этом решении.

Все вычисления проводим в симплексных таблицах.

Заполним симплексную таблицу:

9. Выделим ячейки (А15:Н20), и заполним теми данными, которые имеем. Первая клетка в оценочной строке – это значение целевой функции.

Z = = 0 * 40 + 0 * 60 + 0 * 120 = 0

Оценки:

₁ = - С₁ = 0 * 3 + 0 * 1 + 0 * 3 – 3 = – 3

₂ = - С₂ = 0 * 2 + 0 * 4 + 0 * 0 – 1 = – 1

₃ = - С₃ = 0 * 1 + 0 * 0 + 0 * 0 – 0 = 0

₄ = - С₄ = 0 * 0 + 0 * 1 + 0 * 0 – 0 = 0

₅ = - С₅ = 0 * 0 + 0 * 0 + 0 * 1 – 0 = 0

10. Заполняем оценочную строку. В оценочной строке отрицательные оценки

₁ = – 3, ₂ = – 1. Следовательно, решение неоптимальное. Для перехода к новому решению выбираем ведущий столбец и ведущую строку. Из отрицательных оценок выбираем максимальную по модулю: max {│-3│,│-1│} это будет ₁ = – 3; номер ведущего столбца будет равен 1.

11. Составляем отношение свободных членов b_i к положительным элементам ведущего столбца. Затем находим минимальное из отношений. Номер строки соответствует номеру минимального из отношений.

12. В ячейке J₁₇ вводим формулу = С17/D17.

13. В ячейки J₁₈ и J₁₉ скопируем формулу из ячейки J₁₇, путем перетаскивания уголка. Получим следующее: min {b_i/ai2} = min {40/3, 60/1, 120/3} = min {13,333; 60; 40} = 13,333

Ведущей строкой является первая строка.

14. Итак, в базис войдет х₁ вместо х₃.

Для перехода ко второй таблице разрешающую строку разделим на разрешающий элемент; в разрешающем столбце поставим 0, кроме разрешающего элемента, остальные элементы пересчитаем по формуле прямоугольников.

и заполняем симплексную таблицу.

15. Базисное решение соответствующее данной таблице,

х₂ = (13,333; 0; 0; 46,667; 80), z₂ = 40

В оценочной таблице нет отрицательных элементов, следовательно, решение оптимально.

Решение: х₁ = 13,333, х₂ = 0, Z = 40

Для получения максимальной прибыли необходимо использовать только первый ресурс в количестве 13,33 единиц, при этом максимальная прибыль достигает 40 условных единиц.

Правильность найденных значений проверим через Поиск решения.

1. Присваиваем листу 2 имя Поиск решения.

2. В ячейке А1 введем: Поиск решения.

3. В ячейку А3 введем Прибыль на единицу продукции (z).

4. В ячейках А4:В4 введем элементы целевой функции.

5. В ячейку А6 введем Нормы сырья.

6. В ячейках А7:В9 введем элементы нормы сырья.

7. В ячейку D6 введем Запасы ресурсов.

8. В ячейках D7:D9 введем компоненты запасов ресурсов.

9. В ячейку А11 введем Вектор решения.

10. В ячейки А12:В12 будут помещены найденные значения Х₁, Х₂. А пока присвоим им некоторое начальное значение, например 0. Внесем в ячейки А12:В12 значение 0.

11. В ячейку G6 введем Ограничение.

12. В ячейку G7 введем 7x₁ + 4x₂ 56. Для этого в ячейку G7 введем, Вставка – функция – СУММПРОИЗВ, =СУММПРОИЗВ(А7:В7;$A$13:$В$13) и скопируем содержимое этой ячейки в ячейки G8, G9.

Приступим к решению задачи с помощью модуля поиск решения.

11. Выберем команду Сервис – Поиск решения.

12. В поле установить ячейку установим А16.

13. В поле Изменяя ячейки введем диапазон $A$13:$В$13.

14. В поле Ограничения щелкнем на кнопке Добавить.

15. В поле Ссылка на ячейку введем $G$7.

16. В поле знаков выберем знак <=.

17. В поле Ограничение введем $D$7.

18. Щелкнем на кнопке Добавить. Выполняя шаги 15-17 введем ограничения для второго и третьего уравнения.

19. Щелкнем еще раз на кнопке Добавить. В поле Ссылка на ячейку введем $A$13:$B$13. В поле знаков выберем знак >=. В поле Ограничение введем 0.

Выберем команду Параметры, отметим галочкой Линейная модель.

20. Щелкнем по кнопке Выполнить для поиска решения. Найдя решение поставленной задачи, модель поиска решения отобразит диалоговое окно: Результаты поиска решения, в котором и сообщит о результатах выполненной работы.

Сопоставим данные полученные через Поиск решения с данными рассчитанными симплекс-таблицей.

Максимальная прибыль z составляет 40 условных единиц.

Задача 2

Для перехода к двойственной задаче мы вектор целевой функции прямой задачи принимаем за вектор ограничений двойственной и, наоборот, при этом количество переменных в двойственной задаче равно числу ограничений в прямой.

Цель двойственной задачи – минимизировать стоимость (W) ресурсов (у)

1. Запишем двойственную задачу в каноническом виде:

W = 40у₁ + 60у₂ + 120у₃ min

y_j

2. Для решения системы неравенств необходимо применить вторую теорему двойственности, согласно которой:

3. Тогда подставив в систему неравенств результаты оптимального решения задачи получим:

3* 13,33 + 2* 0 = 40 → у₁ > 0

1 * 13.33 + 4* 0 = 13.333 < 60 → у₂ = 0

3 * 13.33 + 0 * 0 = 40<120 →у₃ =0

т.к х₁ = 13.33, то 3у₁ + 1у₂ + 3у₃ = 3

т.к х₂ = 0, то 2у₁ + 4у₂ + 0у₃ = 1

т.к. y₂ = 0, y₃ = 0, то

Проверка.

W= 40*1+ 60*0+ 120*0 = 40 = Z

Cогласно первой теореме двойственности, полученные результаты подтверждают оптимальность решения прямой задачи.

Для анализа чувствительности делаем следующее:

1. На листе под именем Поиск решения выбираем меню – Сервис – Поиск решения.

2. Нажимаем кнопочку выполнить.

3. В появившемся окне Результаты поиска решения в графе Тип отчета выделяем РЕЗУЛЬАТ и нажимаем клавишу ENTER.

4. На отдельном листе появляются данные отчета по результатам.

5. На листе поиск решения производим шаги с 1 по 3, но в Типе отчета выделяем УСТОЙЧИВОСТЬ и получаем на отдельном листе отчет по устойчивости.

6. На листе поиск решения производим шаги с 1 по 3, но в Типе отчета выделяем ПРЕДЕЛЫ и получаем на отдельном листе отчет по пределам.