Решение транспортной задачи линейного программирования в среде MS Excel (стр. 8 из 9)

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

В таблице Ограничения выводятся значения для ограничений, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.

Рисунок 2. Отчет по устойчивости Поиска решения

- Отчет по пределам- в отчете показано, в каких пределах может изменяться количество материалов, вошедших в оптимальное решение, при сохранении структуры оптимального решения; приводятся значение переменных в оптимальном решение, а также нижние и верхние пределы изменения значений переменных; здесь также указаны значения целевой функции при выпуске данного типа продукции на верхнем и нижнем пределах.

Глава III Двойственная задача линейного программирования

3.1 Математическая формулировка двойственной задачи

линейного программирования

В общем случае двойственной по отношению к стандартной задаче линейного программирования (1.6) и (1.7) называется такая задача линейного программирования, которая может быть записана в следующем виде:

b1y1+b2y2+,…,+bmym →

(3.1)

где множество допустимых альтернатив

формируется следующей системой ограничений типа неравенств:

(3.2)

и y1,y2,,…,yn

0.

Как не трудно заметить, количество переменных двойственной задаче линейного программирования равно количеству ограничений стандартной задачи, а количество ограничений двойственной задачи равно количеству переменных стандартной задачи линейного программирования. При этом, если исходная задача формулируется как задача максимизации целевой функции, то двойственная- как задача минимизации и наоборот. Аналогично изменяются и знаки ограничений двойственной задачи по отношению к исходной задаче линейного программирования.

Существует важная взаимосвязь между двойственной и стандартной задачами линейного программирования. А именно, если одна из задач (1.6) и (1.7) или (3.1) и (3.2) имеет оптимальное решение, то и двойственная ей задача линейного программирования имеет оптимальное решение, при этом оптимальные значения соответствующих целевых функций двойственных задач имеют равные значения, т.е. f’op=fopt , где f’(y)- целевая функция в выражении (3.1), а f(x)–целевая функция в выражении (1.6). Если же для одной из задач (1.6) и (1.7) или (3.1) и (3.2) целевая функция не ограничена на допустимом множестве альтернатив, то соответствующая ей двойственная задача линейного программирования не имеет решения, т.е. имеет множество допустимых альтернатив. Наконец, если одна из задач (1.6) и (1.7) или (3.1) и (3.2) имеет пустое множество допустимых альтернатив, то соответствующая ей двойственная задача линейного программирования либо имеет неограниченную целевую функцию, либо пустое множество допустимых альтернатив.

В общем случае совместное рассмотрение пары двойственных задач линейного программирования позволяет не только выполнить качественный анализ их решения, но и практически использовать найденное решение одной из них для более простого решения другой задачи. Хотя данное свойство оказывается полезным, главным образом, при выполнении ручных расчетов, далее рассмотрим процесс решения двойственных задач линейного программирования с помощью программы MS Excel применительно к задаче о красках.

3.2 Математическая постановка двойственной задачи о красках

Напомним, что исходная постановка задачи о красках сформулирована в форме (3.1) и (3.2). двойственная к ней задача линейного программирования после выполнения простейших преобразований с целью получения целочисленных коэффициентов целевой функции и ограничений может быть записана в следующем виде:

100y1+70y2+100y3→

(3.3)

где множество допустимых альтернатив

формируется следующей системой ограничений типа:

(3.4)

и y1,y2,y3

0.

3.3 Решение двойственной задачи о красках

с помощью MS Exsel

Для решения двойственной задачи о производстве красок с помощью программы MS Exsel создадим новый рабочий лист с именем Двойственная задача. Далее необходимо выполнить следующие действия:

1. Внесем необходимые записи в ячейки А1:Е1, А2:А6, Е4:F4. Следует отметить, что конкретное содержание этих надписей не оказывает никакого влияния на решение рассматриваемой двойственной задачи линейного программирования.

2. В ячейки B2:D3 введем значения коэффициентов целевой функции (3.3) b1=10, b2=7, b3=5.

3. В ячейку E2 введем формулу: =суммпроизв(В2:D2; B3:D3), которая представляет целевую функцию (3.3).

4. В ячейки B5:D6 введем значения коэффициентов ограничений (3.4.).

5. В ячейки F5:F6 введем значения правых значений ограничений (3.4.).

В ячейку E5 введем формулу: =суммпроизв($В$2:$D$2; B5:D5), которая представляет левую часть первого ограничения (3.4).

Рисунок 3.1 Исходные данные для решения двойственной

задачи о производстве красок

7. Скопируем формулу, введенную в ячейку Е5, в ячейку Е6.

Внешний вид рабочего листа MS Office Excel 2003 с исходными данными для решения задачи об оптимальном рационе питания имеет следующий вид рисунок 3.1.

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

После появления диалогового окна Поиск решения следует выполнить следующие действия:

1. В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки $Е$2.

2. Для группы Равной: выбрать вариант поиска решения- минимальному значению.

3. В поле с именем Изменяя ячейки: ввести абсолютный адрес ячеек $В$2:$D$2.

4. Добавить три ограничения, соответствующие (3.5), и одно ограничение на допустимые значения переменных.

5. В дополнительном окне параметров поиска решения следует выбрать отметки Линейная модель и Неотрицательные значения рисунок 3.2.