Линейное и целочисленное программирование

ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

Лабораторный практикум

Лабораторная работа 1

Задания на построение моделей линейного программирования.

1.  Оптимизация оперативно-производственного планирования. В цехе имеются 3 взаимозаменяемых станка, каждый из которых может работать не более 350 часов в месяц. На этих станках должны обрабатываться 5 изделий. Каждое изделие требует различных затрат времени и различных издержек для разных станков. Кроме того, имеются определенные количественные требования по выпуску каждого из изделий в течение месяца. Размеры временных затрат, издержки и количества изделий, которые необходимо выпустить приведены в таблице.

Станки	Нормы времени, ч. (числитель) и издержки, руб. (знаменатель) при обработке 1 изделия	Фонд времени станка, ч.
1-е изделие	2-е изделие	3-е изделие	4-е изделие	5-е изделие
1	1,5 6,0	1,6 6,5	1,5 7,0	2,3 10,0	1,2 5,0	350
2	2,0 6,0	1,8 7,3	1,8 7,5	1,6 9,0	1,7 7,5	350
3	1,3 6,5	1,5 7,5	1,6 7,5	1,8 8,0	2,0 9,0	350
Программа выпуска изделий, шт.	30	40	20	60	50

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

2.  Составление оптимального плана перевозки угля. В трех шахтах ежемесячно добывается 135 тыс. т угля, который в определенных количествах необходимо распределить между 5 пунктами потребления, расположенными на различных расстояниях от шахт. Цифровые характеристики задачи приведены в таблице.

Шахты	Пункты потребления и расстояния до них, км	Количества добываемого на шахтах угля, тыс. т
1	2	3	4	5
1	4	1	3	4	4	60
2	2	3	2	2	3	35
3	3	5	2	4	4	40
Требуется угля в пунктах потребления, тыс. т	22	45	20	18	30	135

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

3.  Планирование транспортного хозяйства. На заводе алмазного инструмента (АИ) имеются три склада материалов. Каждый из них имеет годовую мощность 1800, 2600 и 2400 кг. Материалы направляются на три участка, годовая потребность которых: 1-го – 6100, 2-го –100, 3-го – 600 кг. Склады и участки находятся на расстоянии (в м), указанном в таблице.

Участки	Склады (расстояния до участков, м)	Потребности участков
№1	№2	№3
1. АИ из синт. сплавов	120	100	150	6100
2. АИ из природных алмазов	160	130	180	100
3. Инструмент из эльбора	130	190	110	600
Мощности складов	1800	2600	2400

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

4.  Расчет оптимальной производственной программы. На предприятии имеется три группы взаимно заменяемых станков, на которых изготавливаются два вида изделий: А и Б. Фонд рабочего времени по I группе станков составляет 400 ч, по II группе360, по III группе – 3200 ч. Реализация каждого изделия А дает предприятию прибыль 120 руб. а изделия Б – 480 руб. Характеристики загрузки оборудования представлены в таблице.

Группы станков	Затраты времени на одно изделие, ч	Фонд рабочего времени
Изделие А	Изделие Б
I	0,4	2,0	400
II	0,84	1,2	360
III	8,0	4,0	3200

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

5.  В трех пунктах отправления находится однородный груз в количествах, соответственно равных 250,350 и 400 т. Этот груз необходимо перевезти в три пункта назначения в количествах, соответственно равных 200, 450 и 350 т. Стоимости перевозок 1 т груза из каждого пункта отправления в каждый пункт назначения являются известными величинами и задаются матрицей

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

6.  Ежедневный рацион откорма животных должен включать не менее 60 единиц питательного вещества А, не менее 50 единиц вещества В и не менее 12 единиц вещества С. Эти вещества содержатся в трех видах кормов. Количество единиц питательных веществ, содержащихся в 1 кг каждого из видов корма приведено в таблице

Питательные вещества	Количество единиц питательных веществ в 1 кг корма вида
I	II	III
А	1	3	4
В	2	4	2
С	1	4	3

Составить дневной рацион, обеспечивающий получение необходимого количества питательных веществ и имеющий минимальную стоимость, если цена 1 кг корма I вида составляет 9 руб., корма II вида – 12 руб., корма III вида – 10 руб.

7.  В пунктах могут быть размещены предприятия, производящие однородную продукцию в количестве не более единиц и затратами на производство единицы продукции руб. для -го предприятия . Эта продукция поступает в пунктов ее потребления, причем в -м пункте потребности в продукции равны единицам. Затраты, связанные с доставкой единицы продукции с -го пункта отправления в -й пункт потребления составляют руб. Составить план размещения предприятий, при котором обеспечиваются потребности пунктов потребления при наименьших общих затратах, связанных с производством и доставкой продукции.

8.  Для производства видов изделий предприятие использует групп взаимозаменяемого оборудования. Изделий -го вида необходимо изготовить единиц (), причем -я группа оборудования может быть занята изготовлением изделий не больше чем часов (). Время изготовления одного изделия -го вида на -й группе оборудования равно часам, а себестоимость производства - руб. Определить, сколько изделий каждого вида следует изготовить на каждой из групп оборудования, чтобы произвести требуемое

количество изделий при наименьшей общей стоимости их производства.

9.  Имеется видов удобрений в количествах , , которые используются при выращивании некоторой сельскохозяйственной культуры. Вся посевная площадь содержит участков, причем площадь -го участка равна га (). Внесение на каждый гектар площади -го участка 1 кг удобрений -го вида увеличивает среднюю урожайность на центнеров. Распределить фонд удобрений между посевными зонами так, чтобы максимизировать суммарный прирост урожайности культур.

10.  Предприятие производит два вида конечной продукции I и II. Технологический процесс состоит из двух этапов. На первом этапе поступающее сырье перерабатывается в три вида промежуточного продукта А, В и С, которые на втором этапе используются для производства конечных продуктов I и II. В таблице указаны количества промежуточных продуктов, производимые из одной тонны сырья и количества промежуточных продуктов, затрачиваемые на производство 1 т конечных продуктов каждого вида.

Промежуточный продукт	Выход из 1 т сырья, кг	Расход на 1 т конечного продукта, кг
I	II
А	460	250	800
В	200	250	200
С	340	500	-

Оптовая цена тонны конечной продукции I вида - $200, II вида -$240. Определить производственную программу, максимизирующую общую стоимость произведенной продукции в расчете на одну тонну сырья.

11.  Линейная распределительная задача. Предприятие изготавливает изделия четырех видов А, В,С и D. Для изготовления любого из изделий требуется три вида оборудования I, II и III. Информация о количестве времени, необходимого для изготовления каждого вида продукции на каждом оборудовании, фонде времени работы оборудования (сколько времени может проработать оборудование за рассматриваемый период) и величине прибыли от реализации единицы каждого из изделий приведена в таблице.

Оборудование	Затраты времени на одно изделие	Фонд времени работы оборудования
А	В	С	D
I	3	5	2	7	15
II	4	3	3	5	9
III	5	6	4	8	30
Прибыль от реализации единицы	40	50	30	20

Составить план распределения производства изделий по видам оборудования, максимизирующий прибыль.

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

13. Для изготовления двух видов , продукции используют три вида сырья , ,.Запасы сырья, количество единиц сырья, затрачиваемых на изготовление единицы продукции, а. также величина прибыли, получаем. ал от реализации единицы продукции, приведении в таблице

Количество единиц сырья, идущих на

изготовление ед. продукции

Вид сырья	Запас сырья
	20	2	5
	40	8	5
	30	5	6
		50	40

Прибыль от единицы продукции, руб.

Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыл.

14. Завод выпускает два вида сплавов – никель и сталь. Для их изготовления требуется железо и цветные металлы.

Исходный	Расход на изготовление 1т сплава	Расход на изготовление 1т сплава	Запас, т
Продукт	никель	сталь
Железо	0.3	0.8	2000
Цветные металлы	0.7	0.2	1800

Никеля требуется изготовить не более 1200 тонн, а стали не более 2000 тонн.

Стоимость одной тонны никеля равна 120 у. е., одной тонны стали -50 у. е. Наши соотношение выплавки стали и никеля, максимизирующее стоимость вылущенной продукции.

15. Городской молокозавод производит молоко, кефир и сметану, расфасованные в пакеты.. На производство 1 т молока, кефира, и сметаны требуется соответственно 1010, 1010, и 9450 кг молока. Затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и 0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы в течение 3,25 часа. Всего для производства молочной продукции завод может использовать 136000 кг молока. Основное

оборудование ежедневно может быть занято в течение 21,4 маш.-ч, а втоматы по расфасовке сметаны - в течение 16,25 ч.

Прибыль от реализации 1 т молока, кефира, и сметаны соответственно равна 30, 22 и 136 рублей. Ккую продукцию и в каком количестве следует ежедневно изготовлять заводу, чтобы прибыль от ее реализации была максимальной.

16. Фабрика выпускает баскетбольные и волейбольные мячи. На изготовление одного баскетбольного мяча уходит 0,2 метра кожи, 1 метр резины, 1 трудодень рабочего времени. Расходы на. один волейбольный мяч - 0,5 метров кожи, 0,3 метра резины и 1 трудодень.

еженедельные ресурсы фабрики составляют 200 метров кожи, 140 метров резины и 140 трудодней,

По плану необходимо выпустить не менее 110 единиц мячей. Найти оптимальный план выпуска мячей, максимизирующий недельную прибыль, если прибыль от продажи баскетбольного мяча, составляет 8 руб, а волейбольного мяча - 10 руб.

17. Фабрика, шьет мужские и женские пальто. На изготовление 1 мужского пальто уходит 3 метра драла, 1 метр кашемира и 2 трудоднярабочего времени. На изготовление женского пальто расходуется 3,1 метра драпа, 1,5 метра, .кашемира и 2,5 трудодня.

Ресурсы фабрики составляют 650 метров драна., 350 метров кашемира и 450 трудодней. По плану необходимо выпустить не менее 200 единиц одежды.

Найти план выпуска пальто, максимизирующий прибыль, если прибыль от продажи мужского пальто составляет 20 рублей, а от женского - 23 рубля.

18. На фабрике эксплуатируются ставки двух видов: старого и нового образца. Станок старого образца изготавливает 20 изделий в час, при этом вероятность того, что изделие окажется бракованным, составляет 7%. Станок нового образца изготавливает 30 изделий в час, при этом вероятность брака, для него 2%. Расходы на обслуживание станков составляют 10$ и 8$ в день соответственно.

В случае изготовления бракованного изделия фабрика, несет убыток в размере 50$. Могут быть закуплены не боле 15 станков старого и не более 5 станков нового образца.

Найти оптимальное количество станков старого и нового образца., при котором затраты будут минимальными, учитывая, что за 8-часовой рабочий день фабрика, должна, изготовить не менее 2000 изделий.

19. Кондитерская фабрика для изготовления трех видов карамели А, В и С использует три вида основного сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода, сырья на производство 1 т карамели каждого вида, приведены в таблице.

Кроме того, в таблице указано общее количество сырья каждого вида, которое может быть использовано фабрикой, и прибыль от реализации 1 т карамели каждого вида.

	Нормы расхода сырья(т) на 1 т карамели
Вид сырья	А	В	С	Общее количество сырья
Сахарный песок	0,8	0,5	0,6	800
Патока	0,4	1,4	0,3	600
Фруктовое пюре	_	0,1	0,1	120
Прибыль от реализации 1 т продукции(у. е)	108	112	126

Найти план производства карамели, обеспечивающий максимальную прибыл от ее реализации.

Решение задач регрессионного анализа на компьютере в пакетах EUREKA, MAPLE и STATISTICA

Как правило, возможности решения задач регрессионного анализа есть во всех статистических программах, таких, например, как STATA, SAS, SPSS, STATISTICA, STATGRAPHICS, MS EXCEL (только линейная и полиномиальная регрессия), SHAZAM, а также во многих других, в том числе бесплатно поставляемых и учитывающих особенности различных операционных систем. Информацию о них можно найти, например, по адресу:

http://members. /johnp71/javasta2.html (апрель 2001).

Кроме того, разделы, посвященные статистике и, в частности, регрессионному анализу, есть в универсальных вычислительных пакетах, таких как IMSL, MATHEMATICA, MAPLE, EUREKA. Все эти пакеты немного отличаются друг от друга способами ввода данных, но основные шаги решения задач регрессии, естественно, одни и те же. А именно, для получения коэффициентов регрессии (в примере 1.4 – вектора ), необходимо задать:

1.  уравнение регрессии в общем виде ;

2.  данные об измерениях моделируемой зависимости.

Рассмотрим, как решается задача регрессии в пакете EUREKA: The Solver. Это очень небольшой по объему пакет – его версия 1.0 содержит всего 8 системных файлов, занимающих на диске в общей сложности 250 К. Программа создана Роджером Шлафли и выпущена фирмой Borland Int. в 1987 г. для операционной системы MS DOS, но может работать и под управлением различных версий WINDOWS. Впоследствии на базе этой программы был создан пакет Mercury. Информацию о программе Mercury и некоторых других математических пакетах можно найти, например, по следующему адресу:

http://www. economics. ltsn. ac. uk/software/maths. htm#Mercury (апрель 2001).

Программа Eureka не реагирует на движения мыши, поэтому передвигаться по пунктам меню и окнам программы можно только с помощью клавиш управления курсором. Пакет EUREKA позволяет решать несложные модельные задачи с небольшим количеством данных. После запуска программы с помощью файла eureka. exe открывается окно, изображенное на рисунке 1.5.

Если после старта появляется сообщение: Error: Invalid Directory. Press ESC, то, нажав клавишу Esc, можно продолжать работу. Сообщение связано с тем, что по умолчанию системные файлы пакета должны храниться на диске С в директории (папке) с именем Eureka. Если это не так, то можно либо задать имя и путь папки, в которой эти файлы на самом деле хранятся с помощью опции Directories, в пункте Options главного меню, либо каждый раз нажимать клавишу Esc при запуске программы.

Решаемая задача записывается в окне Edit. Для этого в главном меню необходимо выбрать соответствующую опцию и нажать на Enter. При этом окно Edit становится активным (выделяется двойной рамкой). Введя данные о задаче, вернемся в главное меню (по клавише Esc) и, выбрав опцию Solve, нажмем Enter. Если записанная в окне Edit задача не содержала синтаксических ошибок, то в окне Solution появятся цифры, претендующие на то, чтобы называться решением. Конечно, качество полученного решения зависит не только от правильности введенной информации, но и от сложности решаемой задачи.

Информация о синтаксических ошибках выводится в окне Edit при попытке решить задачу. При этом иногда курсор указывает на символ, вызвавший сообщение об ошибке. Для исправления ошибок необходимо вернуться в главное меню (Esc) и опять выбрать опцию Edit.

Рассмотрим способ ввода информации в пакете для задачи из примера 1.4 о зависимости прибыли от цены товара. Способ записи постановки задачи и результаты решения и приведены на рис. 1.6.

Символ «;» является признаком того, что записанный после него текст – комментарий и к постановке задачи прямого отношения не имеет. Несколько операторов могут быть записаны на одной строке с использованием разделителя – символа «:», например:

y(20)=0 : y(22)=16

y(23)=21 : y(28)=16 : y(29)=9

Если при вводе данных в окно Edit после нажатия на Enter курсор не переходит на следующую строку, нажмите клавишу Insert – режим вставки.

Рис. 1.6. Построение регрессивной зависимости дохода от цены(пример 1.4) в пакете Eureka

Некоторые другие опции меню пакета Eureka: The Solver. Опция Commands имеет свое меню, в котором есть следующие возможности:

Verify – проверка правильности полученного результата. А именно: полученные в окне Solution значения подставляются в соотношения, записанные в окне Edit, и в окне Verify выводятся отдельно значения левых и правых частей. По величине погрешности (difference и max error) можно судить о близости найденных значений к истинному решению.

Find other – попытка найти другое решение данной задачи (например, если требуется найти корни квадратного или любого другого нелинейного уравнения.

Iterate – уточнение найденного решения.

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

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

Пункт меню Options позволяет менять значения текущих переменных задачи (Variables), менять цвета оформления экрана (Colors) и значения системных переменных (Settings), таких как точность расчетов (accuracy), режим расчетов с комплексными переменными, начальные значения переменных задачи, задаваемых по умолчанию равными 1, количество выводимых на экран значащих цифр решения и т. д. Опция Directories, как уже отмечалось, предназначена для задания имен папок, в которых хранятся как сами файлы пакета Eureka, так и постановки пользовательских задач. Измененные параметры пакета можно сохранить по команде Write setup, а загрузить сохраненные в предыдущий раз – соответственно Load setup. Стандартные установки хранятся в файле с именем Config. eka.

С помощью опции Window можно открывать или закрывать какие-либо окна, менять характер их расположения (Tile или Stack) переходить в следующее окно (Next или клавиша F6), раскрывать окно на весь экран (Zoom или клавиша F5), а также переходить в текущее окно из главного меню (Goto или F7).

О способе записи математических функций и выражений можно узнать из подсказки, вызываемой, как обычно по F1. Выход из пакета – по команде Quit опции File.

Решение регрессионных задач в пакете Maple. Версия Maple V, Release 4.00a занимает 30 Мбайт на диске и имеет, конечно, больше возможностей, чем пакет Eureka: The Solver. Обо всех функциях программы можно узнать либо из пункта меню Help, либо с помощью команды

> ?;

Описание возможностей пакета в опции Help сопровождается подробными примерами, текст которых можно скопировать в рабочее поле (имеющее белый фон и символ «>»), и тут же, проверив их работоспособность, подставить данные своей задачи. В пакете Maple можно решать задачи регрессионного анализа только для функций регрессии линейных по параметрам. Для этого необходимо подключить статистический пакет stats и ввести данные, например, в виде, изображенном на рис. 1.7.

Если говорить об особенностях ввода данных в пакете Maple, то, например, для того, чтобы ввести текстовую строку, необходимо щелкнуть левой клавишей мыши по кнопке с символом Т, расположенной на панели инструментов под главным меню. Символ # означает, что после него идет комментарий, однако наличие этого символа после некоторых команд, например, convert или maximize, может привести к «зависанию» программы.

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

Решение задач в пакете EUREKA

Рассмотрим задачу о формировании штата отдела технического контроля, графическое решение которой изображено на рисунке 2.1.

Как было описано в п. 1.2.2, запуск пакета EUREKA производится с помощью файла eureka. exe. После появления основного окна (Рис. 1.5, 1.8), необходимо выбрать пункт главного меню Edit (с помощью клавиш управления курсором, так как мышь в пакете EUREKA не работает) и ввести в одноименном окне постановку задачи (Рис. 1.8).

Заметим, что условие минимизации или максимизации функции записывается в виде

$MIN(z) или $MAX(z),

где z – имя оптимизируемой функции, которая должна быть задана выше.

После того, как постановка задачи записана в окне Edit, необходимо вернуться в главное меню (по клавише Esc) и, перейдя к команде Solve, нажать на ввод. В окне Solution появится решение. Заметим, что компонента решения найдена с погрешностью (точное значение ) из-за того, что задача решается численно с определенной точностью (по умолчанию процесс поиска решения прекращается, если компоненты решения, найденные на соседних итерациях отличаются друг от друга меньше, чем на 10-7).

Решение задач в пакете MAPLE

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

Способ записи ограничений, целевой функции и форма вывода результатов демонстрируются на примере задачи о формировании штата ОТК (п. 1.1.2) и приводятся на рисунке 2.4.

Заметим, что решение найдено точно. Дело в том, что в пакете MAPLE эта задача решается симплекс-методом и, поскольку сам пакет поддерживает аналитические вычисления, то при возникновении дробных выражений числители и знаменатели храняться отдельно и не происходит их приведение к десятичным дробям с потерей значащих разрядов в силу конечности разрядной сетки в компьютере.

Для вычисления значения функции , она может быть задана следующим

образом (Рис. 1.10).

Решение задач в пакете EXCEL

Для решения задач оптимизации в пакете Excel необходимо предварительно подключить надстройку Поиск решения. В главном меню выберите опцию Сервис а в ней пункт Надстройки. Установите флажок на надстройке Поиск решения (Рис. 1.11).

После подключения надстройки Поиск решения необходимо в некоторой ячейке основного листа (например в А1) задать в виде формулы функциональную зависимость оптимизируемой величины от изменяемых переменных. На рисунке 1.12 показан способ задания зависимости минимизируемого выражения от переменных (ячейка А3, начальное значение 8) и (ячейка А4, начальное значение 10). Эта точка соответствует максимальному значению целевой функции (см. рис. 1.4).

Для задания ограничений и нахождения решения порядок действий следующий.

1. 

В главном меню выбрать Сервис/Поиск решения;

2.  В окне Поиск Решения (Рис. 1.13) задать адрес целевой функции ($A$1), диапазон ячеек, в которых заданы начальные значения изменяемых переменных ($A$3:$A$4);

3.  С помощью кнопки Добавить ввести ограничения, например, в следующем виде: слева от знака равенства или неравенства записывается адрес ячейки, содержащей значение изменяемой переменной, а справа – выражение, которое может включать в себя как числа (константы), так и адреса других переменных;

4. 

Щелкнув по кнопке Параметры (Рис 1.14), установить флажки в окошках Линейная модель и Неотрицательные значения (); щелкнуть по кнопке OK;

5.  Щелкнуть по кнопке Выполнить.

Заметим, что за счет указания параметров модели (линейная) в пакете Excel производится настройка используемых методов, и решение, по сравнению, например, с пакетом EUREKA, получается практически точное (Рис. 1.15).

Совершенно аналогично в пакете Excel решаются и задачи нелинейного программирования. При решении этих задач становятся существенными радиокнопки Разности и Метод поиска. Дело в том, что пользователь задает только вид целевой функции, а предлагаемые методы используют еще и ее производные (метод сопряженных градиентов первые, а метод Ньютона – первые и вторые). Поэтому с помощью кнопки Разности задается конкретный способ аппроксимации производных с помощью конечных разностей.

Лабораторная работа II

Решить графически и с помощью компьютерных программ следующие задачи линейного программирования.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.

Лабораторная работа III

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

Лабораторная работа IV

Найти минимум (максимум) целевой функции L при заданных ограничениях

№ варианта	Экстремум	L	ограничения
1	MinL=
2	Min L=
3	MaxL=
4	MaxL=
5	MaxL=
6	MinL=
7	MinL=
8	MinL=
9	MaxL=
10	MaxL=
11	MaxL=
12	MaxL=
13	MinL=
14	MaxL=
15	MinL=
16	MaxL=
17	MinL=
18	MinL=
19	MinL=
20	MaxL=
21	MinL=
22	MinL=
23	MaxL=
24	MinL=
25	MinL=
26	MaxL=
27	MaxL=

Лабораторная работа V

Для следующих задач записать двойственную и найти решение двойственной задачи по решению приямой.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

Лабораторная работа VI

1. Для строительства четырех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может производить 100, 150 и 50 тысяч штук кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектов соответственно равны 75, 80, 60 и 85 тысяч штук. Тарифы перевозок 1 тысячи штук кирпича с каждого завода к каждому из строящихся объектов задаются следующей матрицей

Составить план перевозок кирпича к строящимся объектам, минимизирующий стоимость перевозок.

2. На трех хлебокомбинатах ежедневно производится 110, 190 и 90 т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равны соответственно 80, 60, 170 и 80 т. Тарифы перевозок 1 т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей

Составить план доставки муки, при котором общая стоимость перевозок минимальна.

3. В трех хранилищах горючего ежедневно хранится 175, 125 и 140 т бензина. Этот бензин ежедневно получают четыре заправочные станции в количествах, равных соответственно 180, 120, 60 и 80 т. Стоимости перевозок 1 т бензина от хранилищ до заправочных станций задаются матрицей

Составить план доставки бензина, при котором общая стоимость перевозок минимальна.

Методом северо-западного угла и методом потенциалов найти опорные и оптимальные планы транспортных задач.

4.

Склады	Предприятия	Запасы
A	B	C	D
I	2	3	4	3	180
II	5	3	1	2	60
III	2	1	4	2	60
Потребности	120	40	60	80

5.

Склады	Предприятия	Запасы
A	B	C	D
I	1	2	4	1	50
II	2	3	1	5	30
III	3	2	4	4	10
Потребности	30	30	10	20

6.

Склады	Предприятия	Запасы
A	B	C	D
I	2	4	7	9	200
II	5	1	8	12	270
III	11	6	4	3	130
Потребности	120	80	240	160

7.

Склады	Предприятия	Запасы
A	B	C	D
I	18	2	3	12	180
II	3	4	8	7	160
III	4	5	6	12	140
IV	7	1	5	6	220
Потребности	150	250	120	180

8.

Склады	Предприятия	Запасы
A	B	C	D
I	7	12	10	5	180
II	1	8	11	3	350
III	6	13	15	4	20
Потребности	110	90	200	150

9.

Склады	Предприятия	Запасы
A	B	C	D
I	5	4	2	4	140
II	8	1	4	1	180
III	9	3	7	2	160
Потребности	130	120	130	100

10.

Склады	Предприятия	Запасы
A	B	C	D
I	4	5	4	6	115
II	3	1	9	3	175
III	9	6	7	1	130
Потребности	70	220	70	60

11.

Склады	Предприятия	Запасы
A	B	C	D
I	4	5	3	7	280
II	7	6	2	9	175
III	3	7	14	14	255
Потребности	90	180	310	130

12.

Склады	Предприятия	Запасы
A	B	C	D
I	1	4	7	3	510
II	5	6	8	9	90
III	7	2	4	8	120
Потребности	270	140	200	110

13.

Склады	Предприятия	Запасы
A	B	C	D
I	1	2	3	7	280
II	7	6	2	9	120
III	3	4	12	10	200
Потребности	90	110	220	180

14.

Склады	Предприятия	Запасы
A	B	C
I	4	5	4	280
II	1	3	2	120
III	3	7	14	260
Потребности	120	180	230

15.

Склады	Предприятия	Запасы
A	B	C
I	2	5	4	280
II	1	3	2	120
III	3	2	10	200
Потребности	220	280	130

16.

Склады	Предприятия	Запасы
A	B	C
I	2	5	4	180
II	6	3	5	120
III	4	7	3	160
Потребности	120	80	230

17.

Склады	Предприятия	Запасы
A	B	C
I	4	5	4	140
II	1	6	2	100
III	3	2	1	260
Потребности	120	180	230

18.

Склады	Предприятия	Запасы
A	B	C	D
I	1	8	3	7	280
II	6	7	2	5	120
Потребности	110	90	120	180

19.

Склады	Предприятия	Запасы
A	B	C	D
I	3	2	3	3	280
II	5	1	2	4	220
Потребности	110	90	120	80

20.

Склады	Предприятия	Запасы
A	B	C	D
I	8	2	3	7	180
II	7	4	2	1	120
Потребности	50	110	140	60

21.

Склады	Предприятия	Запасы
A	B	C	D
I	2	1	5	4	160
II	4	3	2	1	240
Потребности	40	110	140	60

22.

Склады	Предприятия	Запасы
A	B	C	D
I	8	3	1	4	180
II	3	2	2	10	120
Потребности	80	120	120	30

23.

Склады	Предприятия	Запасы
A	B	C	D
I	1	2	3	10	170
II	4	3	2	1	230
Потребности	80	70	150	50

24.

Склады	Предприятия	Запасы
A	B	C	D
I	1	10	3	7	310
II	7	8	2	9	190
Потребности	120	30	220	180

25.

Склады	Предприятия	Запасы
A	B	C	D
I	1	2	3	7	550
II	7	6	2	9	150
Потребности	140	160	190	110

Лабораторная работа VII

1. Найдите целочисленное решение задачи о формировании штата отдела технического контроля.

2.

3.

Лабораторная работа VIII

Построить геометрически тестовую задачу линейного программирования с двумя переменными, в которой максимальное значение целевой функции достигается в точке с координатами:

где N - номер варианта (номер студента в списке группы). Найти целочисленное решение построенной задачи методом Гомори.

СОДЕРЖАНИЕ

Лабораторная работа 1………………………………………………4

Решение задач регрессионного анализа на компьютере в пакетах …11 EUREKA, MAPLE и STATISTICA

Лабораторная работа 2………………………………………………21

Лабораторная работа 3………………………………………………23

Лабораторная работа 4………………………………………………23

Лабораторная работа 5………………………………………………27

Лабораторная работа 6………………………………………………29

Лабораторная работа 7………………………………………………35

Лабораторная работа 8………………………………………………35