Постановка задачи линейного программирования. 1. Приведите основную классификацию стандартов в области программного обеспечения

ТЕМА 3. Линейное программирование.

Internet-ресурсы

Вопросы для самопроверки

1. Приведите основную классификацию стандартов в области программного обеспечения.

2. Охарактеризуйте стандарт «де-факто».

3. Охарактеризуйте стандарт «де-юре» и основные отличия от стандарта «де-факто».

4. Кратко приведите переход к стандарту «де-юре» от «де-факто» на примере развития языка SQL.

№ п/п	Адрес	Описание
1.1	http://oitzi.ru/Materials.aspx?doc_id=27&id=535	Классификация стандартов в области программного обеспечения.
1.2	http://lineburg.ru/ohrtruda/zapechnikov_s_v__standartizacija_informacionnykh_tekhnologii_v_aspekte_zahhity_informacii_v_otkrytykh_sistemakh__m___2000__87_s_2.html	Классификация стандартов в области программного обеспечения. Стандарты «де-факто» и «де-юре».
1.3	http://www.distanz.ru/ViewLesson.aspx?Lesson=2046	Классификация стандартов в области программного обеспечения. Стандарты «де-факто» и «де-юре». переход стандарта «де-факто» в «де-юре» на примере языка SQL

Цели: изучить основные понятия линейного программирования.

Линейное программирование (ЛП) - наука о методах исследования и отыскания экстремумов линейной функции, на неизвестные которой наложены линейные ограничения.

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

Экономико-математическая модель - это математическое описание экономического процесса или объекта. Такие модели используются для исследований и анализа экономических процессов. Реализуя их обработку на ЭВМ, мы получаем выигрыш во времени и средствах, так как проведение опытов, как правило, более трудоёмкий и дорогостоящий процесс, кроме того, не всегда возможный. Не буду здесь вдаваться в теорию моделирования, скажу лишь, что именно реализация исследования экономических процессов с помощью ЭВМ для нас и представляет интерес, а проявляется это в машинном решении задач линейного программирования, которые в свою очередь и являются экономико-математическими моделями.

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

· Задачи об использовании ресурсов, сырья, планирования производства

· Задачи составления рациона

· Задачи об использовании мощностей, загрузке оборудования

· Задачи о раскрое материалов

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

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

Но надо представлять общую задачу линейного программирования (ОЗЛП), так как для составления алгоритма необходимо понимать математический смысл решения задачи. Ниже, приведено математическое описание общего вида задачи линейного программирования.

Дана система из m линейных уравнений и неравенств с n переменными:

(1)

и линейная функция

(2)

Необходимо найти такое решение (план) системы

(3)

где

(4)

при котором линейная функция F (2) принимает оптимальное (то есть максимальное или минимальное в зависимости от задачи) значение. При этом система (1) - система ограничений, а функция F (2) - целевая функция (функция цели).

Геометрически область допустимых решений такой задачи можно представить как многогранник в n мерном пространстве (рис. 1).

Рис. 1. Геометрическое представление области допустимых значений задачи

Пример геометрического представления области допустимых решений задачи (рис. 1), где F - линия целевой функции, F=0 начальное положение функции, F=F_max оптимальное положение функции, A, B, C, D, E - вершины многоугольника.

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

Дата добавления: 2014-01-04