3.2. Выполнение задания 2

Рассмотрим задачу в стандартной форме:

• найти план выпуска продукции x₁, x₂, который обеспечивают максимальную выручку

(1.1.4)

при ограничениях:

, (1.1.5)

, (1.1.6)

. (1.1.7)

Решение задачи

1. Установить надстройку Поиск решения, выполнив команды: СервисНадстройки, установить флажок Поиск решения.

2. В электронную таблицу внести исходные данные:

в ячейки B7:C7 – коэффициенты целевой функции,

в ячейки B11:C12 – нормы затрат ресурсов на каждый вид продукции,

в ячейки F11:F12 – запасы ресурсов.

3. В ячейку D7 (целевая ячейка) внести формулу для вычисления выручки. Для этого:

• щелкнуть по пиктограмме fx;

• в окне Мастера функцийвыбрать категориюМатематические, функцию СУММПРОИЗ;

• заполнить окно этой функции щелкнуть по ОК.

4. Содержимое ячейки D7 скопировать в ячейки D11: D12

5. Выполнить команды: Сервис Поиск решения. Откроется диалоговоеокно Поиск решения.

6. Заполнить поля целевой ячейки и изменяемые ячейки.

7. Для ввода ограничений щелкнуть по кнопке Добавить. Появится окно Добавление ограничений. Ввести ограничение. Нажать кнопку ОК.

8. В окне Поиск решения нажать кнопку Параметры и в появившемся окне заполнить окна параметров, нажать кнопку ОК.

9. В окне Поиск решения нажать кнопку Выполнить для запуска режима Поиск решения и нажать кнопку ОК.

Работа 2. Решение транспортной задачи и матричной игры

1. Цель работы

Ознакомление с решением транспортной задачи и матричной игры надстройкой Поиск решения

2. Основные теоретические положения

Транспортная задача

Предположим, что заданы величины a₁,a₂,…,a_n, иb₁,b₂,…,b_m, которые определяют максимальные производительности пунктов производства и минимальные потребности пунктов потребления соответственно.

Обозначим:

c_ij– стоимость перевозок единицы продукции из пункта производстваA_iв пункт потребленияB_j;

x_ij– количество продукции, направляемое из пункта производстваA_iв пункт потребленияB_j. Совокупность чисел {x_ij} образует план перевозок.

Требуется определить такой план перевозок, который минимизирует транспортные расходы.

Математически в транспортной задаче требуется найти план перевозок {x_ij}, который минимизирует транспортные расходы

(2.1.1)

при ограничениях

, (2.1.2)

, (2.1.3)

x_ij ≥ 0. (2.1.4)

Отсюда следует, что транспортная задача является задачей линейного программирования.

Решение матричных игр симплекс – методом

Для определения значения игры vи оптимальных стратегий игрокаIp₁,p₂,…, p_n необходимо решить задачу линейного программирования:

найти переменные v,p₁,p₂,…, p_n, которые максимизируют выигрышvигрокаI

max v

при ограничениях

для всех j = 1, 2,…,m

p₁+p₂ +…+p_n = 1

p_i≥ 0,v -не имеет ограничения на знак.

Для определения значения игры vи оптимальных стратегий игрокаIq₁,q₂,…, q_m необходимо решить задачу линейного программирования:

найти переменные v,p_i, которые максимизируют выигрышvигрокаI

max v

при ограничениях

для всех j= 1, 2,…,m

p₁+p₂ +…+p_n = 1

p_i≥ 0,v- не имеет ограничения на знак.

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