3. Определение оптимального плана задачи с помощью математических методов

1. Преобразуем ограничения из неравенств в систему равенств путем ввода вспомогательных свободных переменных: x50, x60, x70, x80.

Тогда полученные равенства будут выглядеть следующим образом:

0,5*x₁+0,5*x₂ +x₅ =380

0,5*x₃+0,5*x₄ +x₆ =200

0,125*x₁ +0,125*x₄ +x₇ =90

2*x₁ +x₂ +x₃ +x₄ +x₈=1880

2) Построение исходной симплекс-таблицы (таблица 3).

Таблица 3

Базис	x1	x2	x3	x4	x5	x6	x7	x8	bi
x5	0,5	0,5	0	0	1	0	0	0	380
x6	0	0	0,5	0,5	0	1	0	0	200
x7	0,125	0	0	0,125	0	0	1	0	90
x8	2	1	1	1	0	0	0	1	1880
L	14	12	5	6	0	0	0	0

3) Все ли C_j0? Условие не выполняется – переход к шагу 4.

4) C_r=maх{14, 12, 5, 6, 0, 0, 0, 0}=14(r=1, где r столбец). Переменная x₁ вводится в базис, т.к. 1 столбец разрешающий.

5) Все ли a_ir0? Условие не удовлетворяется – переход к шагу 6.

6) Ds=min{380/0,5; -; 90/0,125; 1880/2}=720(x=3, где x строка). Переменная x₇ выводится из базиса, т.к. 3 строка разрешающая.

7) Пересчет элементов симплекс-таблицы – первая итерация (таблица 4).

Таблица 4

Базис	x1	x2	x3	x4	x5	x6	x7	x8	bi
x5	0	0,5	0	-0,5	1	0	-4	0	20
x6	0	0	0,5	0,5	0	1	0	0	200
x1	1	0	0	1	0	0	8	0	720
x8	0	1	1	-1	0	0	-16	1	440
L	0	12	5	-8	0	0	-112	0

8) Все ли C_j0? Условие не выполняется – переход к шагу 9.

9) C_r=maх{0, 12, 5, -8, 0, 0, -112, 0}=12(r=2, где r столбец). Переменная x₂ вводится в базис, т.к. 2 столбец разрешающий.

10) Все ли a_ir0? Условие не удовлетворяется – переход к шагу 11.

11) Ds=min{20/0,5; -; -; 440/1}=40(x=1, где x строка). Переменная x₅ выводится из базиса, т.к. 1 строка разрешающая.

12) Пересчет элементов симплекс-таблицы – вторая итерация (таблица 5).

Таблица 5

Базис	x1	x2	x3	x4	x5	x6	x7	x8	bi
x2	0	1	0	-1	2	0	-8	0	40
x6	0	0	0,5	0,5	0	1	0	0	200
x1	1	0	0	1	0	0	8	0	720
x8	0	0	1	0	-2	0	-8	1	400
L	0	0	5	4	-24	0	-128	0

13) Все ли C_j0? Условие не выполняется – переход к шагу 14.

14) C_r=maх{0, 0, 5, 4, -24, 0, -128, 0}=5(r=3, где r столбец). Переменная x₃ вводится в базис, т.к. 3 столбец разрешающий.

15) Все ли a_ir0? Условие не удовлетворяется – переход к шагу 16.

16) Ds=min{-; 200/0,5; -; 400/1}=400(x=2, где x строка). Переменная x₆ выводится из базиса, т.к. 2 строка разрешающая.

17) Пересчет элементов симплекс-таблицы – третья итерация (таблица 6).

Таблица 6

Базис	x1	x2	x3	x4	x5	x6	x7	x8	bi
x2	0	1	0	-1	2	0	-8	0	40
x3	0	0	1	1	0	2	0	0	400
x1	1	0	0	1	0	0	8	0	720
x8	0	0	0	-1	-2	-2	-8	1	0
L	0	0	0	-1	-24	-10	-128	0

18) Все ли C_j0? Условие выполняется, значит, допустимое базисное решение является оптимальным. L=720*14+40*12+400*5=12560.

4. Определение оптимального плана задачи с помощью

специализированного пакета прикладных программ

2. Краткий обзор специализированных программных средств с возможностями

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

Одна из задач ЭВМ - автоматизация труда, повышение эффективности научных исследований. Основная особенность ЭВМ - ориентация на применение пользователями, не владеющими языками программирования. Такой подход позволяет преодолевать языковой барьер, отделяющий человека от машины. С этой целью разрабатываются пакеты прикладных программ, рассчитанные на широкие круги специалистов. К подобным пакетам относится MATHCAD, EХCEL, QSB, LINDO и другие.

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

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

Библиотека встроенных функций содержит:

• Примерно 20 функций математической статистики

• более 20 функций аппроксимации и сглаживания данных

• Матричные игры

• Балансовые модели

• Транспортные задачи

• Целочисленное программирование

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

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

Табличными процессорами называют пакеты программ, предназначенные для создания электронных таблиц и манипулирования их данными. Табличный процессор Eхcel позволяет: организовывать связи нескольких таблиц, консолидацию данных, сложных формул, сценариев, автоматизированный поиск ошибок вычислений по формулам, таблицы подстановки, макросы, обмен данными с другими приложениями. Его целесообразно использовать для создания таблиц в случаях, когда предполагаются сложные расчеты, сортировка, статистический анализ массивов, построение на их основе диаграмм. Поиск решений является частью блока задач, который иногда называют анализ "что-если". Процедура поиска решения позволяет найти оптимальное значение формулы содержащейся в ячейке, которая называется целевой. Эта процедура работает с группой ячеек, прямо или косвенно связанных с формулой в целевой ячейке. Чтобы получить по формуле, содержащейся в целевой ячейке, заданный результат, процедура изменяет значения во влияющих ячейках. Чтобы сузить множество значений, используемых в модели, применяются ограничения. Эти ограничения могут ссылаться на другие влияющие ячейки. Процедуру поиска решения можно использовать для определения значения влияющей ячейки, которое соответствует экстремуму зависимой ячейки — например можно изменить объем планируемого бюджета рекламы и увидеть, как это повлияет на проектируемую сумму расходов.