- •6.030509, 6.030504, 6.030601Дневной и заочной форм обучения
- •1.Решение систем линейных уравнений методом гаусса – жордана
- •1.1. Основные понятия
- •1.2. Приведение системы линейных уравнений к жордановой форме
- •1.3. Понятие общего, частного и базисного решений.
- •2. Общие свойства задачи линейного программирования
- •2.І. Пример задачи линейного программирования - задача об использовании оборудования.
- •2.2. Задача об использовании сырья.
- •2.3. Задача составления рациона (задача о диете).
- •2.4. Общая постановка задачи линейного программирования
- •2.5. Геометрический метод решения злп.
- •Пример 1
- •2.6. Канонический вид злп.
- •2.7. Понятие опорного плана злп.
- •3. Симплексный метод решения злп
- •3.1. Общая характеристика и основные этапы симплекс – метода
- •3.2. Табличный вид злп. Симплекс - таблицы.
- •3.3. Условие оптимальности опорного плана.
- •3.4. Условие неразрешимости злп из-за неограниченности снизу на одр целевой функции.
- •3.5. Переход к новому опорному плану.
- •3.6. Табличный симплекс-алгоритм.
- •После выбора генерального элемента переходим к таблице 3.11
- •Снова выбираем генеральный элемент и переходим к таблице 3.14
- •3.7. Отыскание исходного опорного плана злп методом искусственного базиса
- •3.8. Вырожденность опорного плана. Зацикливание.
- •Двойственность в линейном программировании
- •Экономическая интерпретация двойственных задач
- •Понятие двойственной задачи
- •Теоремы двойственности
- •Транспортная задача.
- •Задача о перевозках.
- •Общая постановка транспортной задачи.
- •Отыскание исходного опорного плана перевозок.
- •5.4. Циклы пересчета
- •5.4.1. Понятие цикла пересчета
- •5.4.2. Максимально допустимый сдвиг по циклу пересчета.
- •5.4.3. Цена цикла пересчета
- •5.5. Потенциалы.
- •5.6. Алгоритм решения транспортной задачи методом потенциалов.
- •5.7. Открытые транспортные задачи.
- •6. Целочисленное линейное программирование
- •6.1. Общая постановка задачи целочисленного линейного программирования (зцлп).
- •6.2. Целочисленная задача об использовании сырья.
- •6.3. Задача о рюкзаке.
- •6.4. Решение зцлп методом округления.
- •6.5. Метод ветвей и границ.
- •Оптимальный план оптимальный план
- •7. Общая постановка и разновидности задач математического программирования
- •Литература
- •Содержание
1.3. Понятие общего, частного и базисного решений.
.
Пусть система (І.І) представлена в жордановой форме (1.2). Выразим базисные переменные через свободные.
(1.6)
(1.6) называется общим решением системы (I.I).
Если свободным переменным придать любые числовые значения и вычислить значения базисных переменных из системы (1.6), то получится решение исходной системы, называемое частным. Частное решение называется базисным, если свободные переменные принимают нулевые значения. Решение (1.3) является базисным.
В примере общее решение таково:
а базисное решение. Если в жордановой форме число уравнений равно числу переменных n, т.е. жорданова форма имеет вид:
то система имеет единственное решение; оно является и общим, и частным, и базисным. Если же k‹n , т.е. жорданова форма содержит свободные переменные, то система имеет бесконечно много решений.
2. Общие свойства задачи линейного программирования
2.І. Пример задачи линейного программирования - задача об использовании оборудования.
Предприятие выпускает два вида изделий А и В, для производства которых используются три типа станков. Известны затраты времени (в часах) станками на производство единицы каждого вида изделий, резервы времени станков, а также прибыль от реализации каждого вида изделия. Все эти данные приведены в таблице:
Изделия станки |
А |
В |
Резервы времени (в часах) |
I |
Затраты времени на пр-во ед. изделия (в часах) | ||
2 |
3 |
30 | |
II |
4 |
2 |
40 |
III |
3 |
4 |
60 |
Прибыль от реализации ед. изделия |
6 |
7 |
|
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.
Это пример оптимизационной экономической задачи. Решение таких задач включает в себя следующие этапы:
построение экономико-математической модели;
решение полученной математической задачи каким-либо математическим методом;
внедрение результата решения в практику.
Под экономико-математической моделью понимается система математических соотношений, описывающих экономический процесс.
Построим экономико-математическую модель задачи об использовании оборудования.
Пусть х1 - количество изделий А, а - количество изделий В, которые будут выпущены предприятием. Тогда прибыль, полученная предприятием, будет равна , Переменныеинужно подобрать так, чтобы функциямаксимизировалась. Так как первый станок может работать не более 30 часов, то должно выполняться соотношение. Аналогичные ограничения на переменные х1 и х2 накладываются резервами времени второго и третьего станков. Учитывая еще, что переменные х1 и х2 могут принимать только неотрицательные значения, получим следующую экономико-математическую модель задачи:
max
при ограничениях
2.2. Задача об использовании сырья.
С математической точки зрения эта задача является обобщением той, которая рассмотрена в предыдущем параграфе. Формулируется она так.
Предприятие выпускает продукцию n видов , на изготовление которой расходуется сырьеm видов , запасы которого на предприятии равны соответственно . Известны расходысырьяSi на производство единицы продукции (i = ; j =). Стоимость единицы продукции равна(j =). Требуется составить такой план выпуска продукции, при котором выручка от реализации продукции была бы наибольшей.
Составим математическую модель задачи.
Пусть - количество единиц продукции(j =).
Математическая модель имеет вид:
f =→ max
при ограничениях:
( 2.0)