- •2) Переход от общей (стандартной) формы злп к канонической.
- •Переход от канонической формы к стандартной.
- •1.1.3. Контрольные вопросы:
- •1.1.4. Варианты индивидуальных заданий:
- •1.2 Графический метод решения задач
- •1.2.2. Теоретическая часть:
- •1.2.3. Контрольные вопросы:
- •1.2.4. Варианты индивидуальных заданий:
- •1.3 Симплекс-метод решения задач линейного программиро-вания
- •1.3.2. Теоретическая часть
- •1.3.2.1. Симплекс-метод
- •1.3.2.2. Cимплекс-метод для неполного базиса (м-метод).
- •1.3.3. Контрольные вопросы:
- •1.3.4. Варианты индивидуальных занятий
- •1.4 Двойственность в линейном программировании
- •1.4.2. Теоретическая часть:
- •1.4.2.1. Общая модель задачи
- •1.4.2.2. Решение злп с помощью графического анализа двойственной задачи
- •1.4.3. Контрольные вопросы:
- •1.4.4. Варианты индивидуальных заданий.
- •1.5 Транспортная задача (т-задача)
- •1.5.2. Теоретическая часть:
- •1.5.2.1. Алгоритм решения т-задачи.
- •1.5.2. Примеры решения т-задачи.
- •1.5.3. Контрольные вопросы.
- •1.5.4. Варианты индивидуальных заданий:
- •1.6 Целочисленное программирование
- •1.6.2. Теоретическая часть: Описание метода отсечений (метода Гомори).
- •1.6.3. Контрольные вопросы:
- •1.6.4. Варианты индивидуальных заданий.
- •2.1.2.2. Метод Франка-Вулфа решения задач квадратичного программирова-
- •2.2 Контрольные вопросы.
- •2.3. Индивидуальные задания.
|
|
Содержание |
|
|
Предисловие ......................................................................................................................... |
4 |
|||
1. |
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ .......................................................................... |
5 |
||
|
1.1 |
ОСНОВНЫЕ ФОРМЫ ЗЛП ...................................................................................... |
5 |
|
|
1.2 |
ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ..................................................... |
13 |
|
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (ЗЛП) .............................................................. |
13 |
|||
|
1.3 СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО |
|
||
|
ПРОГРАММИРОВАНИЯ .............................................................................................. |
18 |
||
|
1.4 |
ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ........................ |
33 |
|
|
1.5 |
ТРАНСПОРТНАЯ ЗАДАЧА (Т-ЗАДАЧА)............................................................. |
38 |
|
|
1.6 |
ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ..................................................... |
45 |
|
2. |
НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. .................................................................. |
49 |
||
|
2.1 |
КЛАССИЧЕСКАЯ ЗАДАЧА МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ |
||
|
......................................................................................................................................... |
49 |
||
|
|
|
||
|
|
|
СОДЕРЖАНИЕ ОТЧЕТА
Отчет по практической работе должен содержать:
-
титульный лист,
-
название практической работы,
-
цель и задание,
-
решение с подробными объяснениями
-
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
1.1 ОСНОВНЫЕ ФОРМЫ ЗЛП
1.1.1. Цель: освоить постановку задач линейного программирования, формы за-писи ЗЛП, их эквивалентность, переход от одной формы записи к другой.
1.1.2. Теоретическая часть:
-
Формы записи ЗЛП и их эквивалентность.
Общей формой ЗЛП является задача на нахождение экстремума (максимума, ми-нимума) линейной целевой функции, система ограничений которой содержит как ра-венства, так и неравенства обоих знаков, а условия неотрицательности наложены не на все переменные.
-
стандартной форме ЗЛП требуется найти экстремум целевой функции, система ограничений представлена в виде однородных неравенств (имеющих один знак), все переменные подчинены условиям неотрицательности.
-
канонической ЗЛП необходимо найти максимум функции, система ограничений представлена в виде равенств.
От одной формы ЗЛП можно перейти к другой, проделав ряд несложных преобра-зований.
2) Переход от общей (стандартной) формы злп к канонической.
Для перевода общей или стандартной формы к канонической нужно учесть три момента:
- устремить функцию к максимуму, применив следующее соотношение max( f (x)) min( f (x));
-
неравенства привести к виду равенств, добавив в них балансовые переменные с знаком «-« или «+» в зависимости от знака неравенства;
-
избавиться от отрицательных или предположительно отрицательных перемен-ных. Для этого можно применить два способа.
I способ: каждую предположительно отрицательную переменную хj (j=1,2,…,s) представим в виде разности двух неотрицательных переменных x j x1j x2j , где
x1j 0, x2j 0 . Этот способ приводит к загромождению задачи дополнительными пе-ременными, зато не требует предварительных расчетов.
-
способ: каждую предположительно отрицательную переменную хj (j=1,2,…,s) выразим через остальные неотрицательные переменные хs+1, xs+2,…,xn, для чего эти от-рицательные переменные сделаем базисными в любых s уравнениях системы. Затем эти уравнения выбросим из системы и решим упрощенную систему, которая будет со-держать меньшее количество уравнений и (n-s) переменных. После решения упрощен-ной системы подставим полученные значения в отброшенные уравнения и найдем зна-чения предположительно неположительных переменных.
Пример: Привести к канонической следующую ЗЛП в общей форме:
-
2x1 x2 3x3 2x4 min,
2x1 x2 3x3 x4 4,
3x1 x2 2x3 x4 2,
5x1 3x2 x3 6,
x1 0, x2 0.
5
Введем неотрицательные балансовые переменные х5 и х6 во второе и третье огра-ничения системы. Заменим отрицательную переменную х2 неотрицательной перемен-ной x12 x2 0 , а переменные х3 и х4 с неопределенным знаком представим первым способом как
x3 x13 x32 , x13 0, x32 0
x4 x14 x42 , x14 0, x42 0
Целевую функцию переведем от min к max и получим задачу в канонической форме:
2x |
x1 |
3x1 |
3x2 |
2x1 2x2 max, |
|
|
|
|
|
||||||||||||||||||||||||
1 |
2 |
|
3 |
3 |
|
|
|
4 |
|
4 |
|
|
|
|
|
|
|
|
|||||||||||||||
2x x1 |
3x1 |
3x2 |
x1 |
x2 |
|
4, |
|
|
|
|
|
|
|
||||||||||||||||||||
1 |
2 |
|
3 |
3 |
|
|
4 |
4 |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
3x x1 |
2x1 |
2x2 |
x1 |
x2 |
|
x |
5 |
2, |
|
|
|
|
|
||||||||||||||||||||
1 |
2 |
|
3 |
3 |
|
|
4 |
4 |
|
|
|
|
|
|
|
|
|
||||||||||||||||
5x 3x1 |
x1 |
x2 x |
6 |
6, |
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
1 |
|
2 |
3 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
x 0, x1 |
0, x1 0, x |
2 |
0, x1 |
0, x2 |
0, x |
5 |
0, x |
6 |
0. |
|
|||||||||||||||||||||||
1 |
|
2 |
|
3 |
3 |
|
|
4 |
|
4 |
|
|
|
|
|
|