-
Notifications
You must be signed in to change notification settings - Fork 0
/
analysis.lyx
2141 lines (1606 loc) · 38.7 KB
/
analysis.lyx
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#LyX 2.2 created this file. For more info see http://www.lyx.org/
\lyxformat 508
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass amsart
\begin_preamble
\usepackage{placeins}
\end_preamble
\use_default_options true
\begin_modules
theorems-ams
eqs-within-sections
figs-within-sections
\end_modules
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "ccfonts" "Linux Libertine Display G"
\font_sans "tgheros" "Linux Biolinum O"
\font_typewriter "courier" "DejaVu Sans Mono"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts true
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header
\begin_body
\begin_layout Title
Print Job Optimization
\end_layout
\begin_layout Author
James Jones
\end_layout
\begin_layout Date
May 30, 2018
\end_layout
\begin_layout Abstract
We try to formalize a print job optimization problem brought to the meetup
iand come up with a reasonably quick way to, given a print job, determine
how to print it at minimal cost.
\end_layout
\begin_layout Section
Definitions and Presumptions
\begin_inset Foot
status open
\begin_layout Plain Layout
We have revised this document for consistency, to the extent possible, with
terms used in
\begin_inset CommandInset citation
LatexCommand cite
key "key-1"
\end_inset
and
\begin_inset CommandInset citation
LatexCommand cite
key "key-2"
\end_inset
.
An appendix describes possibly-unfamiliar notation.
\end_layout
\end_inset
\end_layout
\begin_layout Subsection
Job and Version
\end_layout
\begin_layout Standard
A
\noun on
job
\noun default
\emph on
j
\emph default
is a pair
\begin_inset Formula $(V,q)$
\end_inset
where
\begin_inset Formula $V$
\end_inset
is a non-empty, finite set of
\noun on
versions
\noun default
, identically-sized images of pieces to be printed, and
\begin_inset Formula $q:V\rightarrow\mathbb{Z^{\mathrm{+}}}$
\end_inset
is a function indicating how many of each version the customer wants printed.
We presume that our printer can print sheets of paper large enough to let
us print at least one piece.
For a given job, we define
\begin_inset Formula $U$
\end_inset
to be the number of pieces that can fit on a sheet.
\end_layout
\begin_layout Subsection
Form and Run
\end_layout
\begin_layout Standard
A
\noun on
form
\noun default
is a function
\begin_inset Formula $f:V\rightarrow\mathbb{N}$
\end_inset
such that
\begin_inset Formula $0<u(f)\leq U$
\end_inset
where
\begin_inset Formula $u(f)=\sum_{v\in V}f(v)$
\end_inset
, i.e.
a form must print something and fit on a sheet.
\begin_inset Formula $f(v)$
\end_inset
is the number of pieces of version
\begin_inset Formula $v$
\end_inset
printed per sheet for form
\begin_inset Formula $f$
\end_inset
.
A form
\begin_inset Formula $f$
\end_inset
is said to be
\begin_inset Quotes eld
\end_inset
\begin_inset Formula $u(f)$
\end_inset
-up
\begin_inset Quotes erd
\end_inset
.
We call the set of possible forms for a job
\begin_inset Formula $\mathbb{F}$
\end_inset
, and define
\begin_inset Formula $\pi:\mathbb{F\mathrm{\rightarrow\mathscr{\mathscr{P\mathrm{\left(\mathrm{\mathit{V}}\right)}}}}}$
\end_inset
by
\begin_inset Formula $\pi\left(f\right)=f^{-1}\left(\mathbb{Z^{\mathrm{+}}}\right)$
\end_inset
.
\end_layout
\begin_layout Standard
A form
\begin_inset Formula $f$
\end_inset
corresponds to plates that print
\begin_inset Formula $\pi\left(f\right)$
\end_inset
.
The printer uses
\noun on
process color
\begin_inset CommandInset citation
LatexCommand cite
key "key-4"
\end_inset
,
\noun default
so each form requires four or eight plates for single-sided or double-sided
printing respectively.
\end_layout
\begin_layout Standard
A
\noun on
run
\noun default
is the process of preparing the plates corresponding to a form and printing
a number of sheets using it.
\end_layout
\begin_layout Subsection
Solution
\end_layout
\begin_layout Standard
A
\noun on
solution
\noun default
for a job
\begin_inset Formula $(V,q)$
\end_inset
is a pair
\begin_inset Formula $(F,p)$
\end_inset
such that
\begin_inset Formula $\textrm{Ø}\subset F\subseteq\mathbb{F}$
\end_inset
and
\begin_inset Formula $p:F\rightarrow\mathbb{Z^{\mathrm{+}}}$
\end_inset
satisfies
\begin_inset Formula $\forall v\in V,\,q'(v)\geq q(v)$
\end_inset
, where
\begin_inset Formula $q'(v)=\sum_{f\in F}p(f)f(v)$
\end_inset
.
\begin_inset Formula $p$
\end_inset
maps a form to the number of sheets to be printed with it, and
\begin_inset Formula $q'$
\end_inset
maps a version to the total number of copies that will be printed with
the specified solution, so the constraint just means
\begin_inset Quotes eld
\end_inset
we print at least as many of each version as the customer wants
\begin_inset Quotes erd
\end_inset
.
Given a solution
\begin_inset Formula $(F,p)$
\end_inset
, for each
\begin_inset Formula $f\in F,$
\end_inset
one does a run printing
\begin_inset Formula $p(f)$
\end_inset
sheets using the plates created for
\begin_inset Formula $f$
\end_inset
.
\end_layout
\begin_layout Standard
Clearly if
\begin_inset Formula $(F,p)$
\end_inset
solves
\begin_inset Formula $(V,q)$
\end_inset
,
\begin_inset Formula $(F,v\mapsto kp(v))$
\end_inset
solves
\begin_inset Formula $(V,v\mapsto kq(v))$
\end_inset
for all
\begin_inset Formula $k\in\mathbb{Z^{\mathrm{+}}}$
\end_inset
.
One can thus solve
\begin_inset Formula $(V,q)$
\end_inset
by solving
\begin_inset Formula $(V,v\mapsto\frac{q(v)}{\gcd\,q[V]})$
\end_inset
.
If the
\begin_inset Formula $q$
\end_inset
values tend to be round numbers, the smaller job may be easier to solve.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
That property helps one work out examples by hand, but the code won't need
to bother.
This is just as well, because an order often includes
\begin_inset Quotes eld
\end_inset
seed
\begin_inset Quotes erd
\end_inset
copies.
These go to people who will confirm receipt, providing evidence that a
mailing actually took place.
\end_layout
\end_inset
\end_layout
\begin_layout Section
The cost function
\end_layout
\begin_layout Standard
We don't just want solutions; we want solutions that minimize some cost
function
\begin_inset Formula $c(F,p)$
\end_inset
.
What should the cost function reflect?
\end_layout
\begin_layout Subsection
Wasted paper
\end_layout
\begin_layout Standard
Wasted paper comes in two flavors: blank piece-sized spaces on sheets and
excess pieces printed.
There are
\begin_inset Formula $\sum_{f\in F}p(f)(U-u(f))$
\end_inset
of the former and
\begin_inset Formula $\sum_{v\in V}\left(q'(v)-q(v)\right)$
\end_inset
of the latter, and their sum reflects the total wasted paper.
\end_layout
\begin_layout Subsection
Wasted ink?
\end_layout
\begin_layout Standard
The printer who brought us this problem said that ink wasn't a concern,
so we'll ignore it; besides,
\end_layout
\begin_layout Itemize
Without detailed knowledge of what's being printed, we can't tell how much
ink we're wasting anyway, but...
\end_layout
\begin_layout Itemize
...wasted ink is ink printed on wasted paper, so minimizing wasted paper minimizes
wasted ink.
One could argue for weighting printed-on waste more heavily than blank
waste, but that requires the detailed knowledge we lack.
\end_layout
\begin_layout Subsection
Forms
\end_layout
\begin_layout Standard
Creating forms is, we're told, the resource-intensive part of an offset
print job, and looking at videos of the process just for small sheets,
I can believe it
\begin_inset CommandInset citation
LatexCommand cite
key "key-6"
\end_inset
.
For double-sided printing (which the example we were first given requires),
each form requires eight frames made from the CMYK separations for each
side.
\end_layout
\begin_layout Subsection
Weighting
\end_layout
\begin_layout Standard
The obvious cost function is, then, a weighted sum of wasted paper and the
number of forms...but what are the weights, or equivalently, how many sheets
would you waste to avoid another form?
\end_layout
\begin_layout Standard
Probably quite a few, from looking at how plates are prepared and the cost
of plates and materials.
One example of what, at least to me, seems a large job, involved printing
nearly 800,000 pieces with 186 versions.
It was printed 12-up and sheetwise, with thirty forms, at a cost per sheet
of $0.20 and setup cost per press run of $475.
At $0.20/sheet, that would pay for 2,360 sheets of paper, or
\begin_inset Formula $2360U$
\end_inset
pieces, so you'd have to seriously reduce waste to make it worth another
form.
\end_layout
\begin_layout Subsection
Why not just use the actual cost?
\end_layout
\begin_layout Standard
Maybe we should.
I was trying to reflect how far away a solution is from the optimum, but
there's no way to express wasted forms without actually knowing the optimal
solution.
(It
\emph on
did
\emph default
show what an optimal one-form solution must be.)
\end_layout
\begin_layout Section
Solutions
\end_layout
\begin_layout Subsection
Maximum forms
\end_layout
\begin_layout Standard
Given a job
\begin_inset Formula $(V,q),$
\end_inset
\begin_inset Formula $(\{w\mapsto U\delta_{vw}|v\in V\},\,v\mapsto\left\lceil \frac{q(v)}{U}\right\rceil )$
\end_inset
is a solution with
\begin_inset Formula $\left\Vert V\right\Vert $
\end_inset
forms.
\begin_inset Foot
status collapsed
\begin_layout Plain Layout
Here we use a flavor of the Kronecker delta
\begin_inset CommandInset citation
LatexCommand cite
key "key-5"
\end_inset
that compares versions rather than integers.
\end_layout
\end_inset
If
\begin_inset Formula $\left\Vert V\right\Vert $
\end_inset
=1 or
\begin_inset Formula $U=1,$
\end_inset
that is
\emph on
the
\emph default
solution.
In general, it's pretty expensive, but at least it serves as an existence
proof.
\end_layout
\begin_layout Subsection
Minimum forms
\begin_inset CommandInset label
LatexCommand label
name "subsec:Minimum-forms"
\end_inset
\end_layout
\begin_layout Standard
Every job has a solution with
\begin_inset Formula $\left\lceil \frac{\left\Vert V\right\Vert }{U}\right\rceil $
\end_inset
forms.
For simplicity's sake, let's start with the simple case, and then add the
minor complication.
\end_layout
\begin_layout Subsubsection
\begin_inset Formula $U|\left\Vert V\right\Vert $
\end_inset
\end_layout
\begin_layout Standard
If
\begin_inset Formula $U$
\end_inset
divides
\begin_inset Formula $\left\Vert V\right\Vert ,$
\end_inset
there are
\begin_inset Formula $\frac{\left\Vert V\right\Vert }{U}$
\end_inset
forms, all stuffed to the gills.
More formally,
\begin_inset Formula $\forall f\in F,\left\Vert \pi\left(f\right)\right\Vert =U$
\end_inset
, so
\begin_inset Formula $\forall v\in f,\,f(v)=1$
\end_inset
and hence
\begin_inset Formula $q'(v)=p(f)=\max\,q[\pi\left(f\right)]$
\end_inset
.
\begin_inset Formula $f$
\end_inset
thus adds
\begin_inset Formula $p(f)\sum_{v\in\pi\left(f\right)}\left(p(f)-q(v)\right)$
\end_inset
to the paper portion of the cost.
\begin_inset CommandInset label
LatexCommand label
name "q-spread--versus-waste"
\end_inset
Note that if
\begin_inset Formula $\left\Vert q\left[\pi(f)\right]\right\Vert =1$
\end_inset
, said contribution is zero, which suggests printing versions with the same
quantity together on a form.
\end_layout
\begin_layout Subsubsection
\begin_inset Formula $U\nmid\left\Vert V\right\Vert $
\end_inset
\end_layout
\begin_layout Standard
Otherwise, the forms are just as described above, plus one more with
\begin_inset Formula $\left\Vert \pi(f)\right\Vert <U.$
\end_inset
This extra form and its leftover slots can be handled as described in
\begin_inset CommandInset ref
LatexCommand ref
reference "subsec:Pretty-good"
\end_inset
.
\end_layout
\begin_layout Subsection
The one-form case
\end_layout
\begin_layout Standard
As long as
\begin_inset Formula $\left\Vert V\right\Vert <U$
\end_inset
, we can print everything with one form.
We'll discuss whether we should later.
\end_layout
\begin_layout Subsubsection
The perfect solution
\end_layout
\begin_layout Standard
A perfect solution uses one form and prints exactly what the customer wants.
If there's an integer
\begin_inset Formula $p'$
\end_inset
such that
\begin_inset Formula $\forall v\in V,\,p'|q(v)$
\end_inset
and
\begin_inset Formula $\sum_{v\in V}\frac{q(v)}{p'}=U$
\end_inset
, then
\begin_inset Formula $(\{f\},\,f\mapsto p'),$
\end_inset
where
\begin_inset Formula $f(v)=\frac{q(v)}{p'}$
\end_inset
, is the perfect solution, because
\end_layout
\begin_layout Itemize
\begin_inset Formula $U=\sum_{v\in V}\frac{q(v)}{p'}=\sum_{v\in V}f(v)=u(f)$
\end_inset
, so
\begin_inset Formula $f$
\end_inset
is
\begin_inset Formula $U$
\end_inset
-up; all printed sheets are full.
\end_layout
\begin_layout Itemize
\begin_inset Formula $\forall v\in V,\,q'(v)=\sum_{f\in F}p(f)f(v)=p'\frac{q(v)}{p'}=q(v)$
\end_inset
, so no excess copies are printed and no ink is wasted.
\end_layout
\begin_layout Itemize
One form is the best we can do.
\end_layout
\begin_layout Standard
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none
\begin_inset Formula $\sum_{v\in V}\frac{q(v)}{p'}=U\Rightarrow p'=\frac{\sum_{v\in V}q(v)}{U}$
\end_inset
, so just calculate that value.
If it's an integer that divides all the quantities, you're golden.
If not, there will be some waste.
\end_layout
\begin_layout Subsubsection
Pretty good solution
\begin_inset CommandInset label
LatexCommand label
name "subsec:Pretty-good"
\end_inset
\end_layout
\begin_layout Standard
A perfect solution may not be possible, but one can come close.
Consider the example from the first meetup where we talked about the problem,
with
\end_layout
\begin_layout Itemize
\begin_inset Formula $V=\left\{ v_{1},v_{2},v_{3}\right\} $
\end_inset
\end_layout
\begin_layout Itemize
\begin_inset Formula $q(v_{1})=1100,\,q(v_{2})=1000,\,q(v_{3})=300$
\end_inset
\end_layout
\begin_layout Itemize
\begin_inset Formula $U=12$
\end_inset
\end_layout
\begin_layout Standard
For doing this by hand, we can turn it into a search for a solution for
(11, 10, 3).
I came up with
\begin_inset Formula $f(v_{1})=5,\,f(v_{2})=5,\,f(v_{3})=2$
\end_inset
, so that printing three sheets gives you 15 of
\begin_inset Formula $v_{1}$
\end_inset
and
\begin_inset Formula $v_{2}$
\end_inset
and six of
\begin_inset Formula $v_{3}.$
\end_inset
Three's necessary to get eleven copies of
\begin_inset Formula $v_{1}$
\end_inset
.
\end_layout
\begin_layout Standard
We could stop there and print 300 sheets to accommodate the order—but we
shouldn't.
A scaled-up perfect solution is necessarily perfect.
A scaled-up less-than-perfect solution gives an even less perfect solution
for a larger problem, but if
\emph on
all
\emph default
versions have excess copies, there may be room to improve.
220 sheets gives us 1100 of each of
\begin_inset Formula $v_{1}$
\end_inset
and
\begin_inset Formula $v_{2}$
\end_inset
, and 440 of
\begin_inset Formula $v_{3}$
\end_inset
, resulting in 100 excess of
\begin_inset Formula $v_{2}$
\end_inset
and 140 excess of
\begin_inset Formula $v_{3}$
\end_inset
.
240 excess copies at 12-up is 20 sheets of paper, only four dollars more
expensive than a perfect solution, if one even exists.
I spent maybe five minutes coming up with that form, but our goal is to
avoid such work, so...
\end_layout
\begin_layout Standard
...let's try our perfect formula anyway.
\begin_inset Formula $11+10+3=24,$
\end_inset
a multiple of 12, giving
\begin_inset Formula $p'=2$
\end_inset
.
11 and 3 are odd, so they fail the first constraint—but look at what we
got for our hand-generated form.
Integer division of the
\begin_inset Formula $v$
\end_inset
s by 2 gives us 5, 5, and 1 which add to 11, one less than
\begin_inset Formula $U$
\end_inset
.
Using that leftover for anything other than
\begin_inset Formula $v_{3}$
\end_inset
forces the full 300 sheets to get 300 of
\begin_inset Formula $v_{3}$
\end_inset
, so 5, 5, 2 looks like (and in fact is) the best we can do, suggesting
that the formula can guide us even if we can't achieve perfection.
\end_layout
\begin_layout Standard
We were fortunate with that first example, because our
\begin_inset Formula $p'$
\end_inset
did meet one constraint if not both.
Let's try one that meets neither.
\end_layout
\begin_layout Itemize
\begin_inset Formula $V=\left\{ v_{1},v_{2},v_{3}\right\} $
\end_inset
\end_layout
\begin_layout Itemize
\begin_inset Formula $q(v_{1})=1000,\,q(v_{2})=800,\,q(v_{3})=300$
\end_inset
\end_layout
\begin_layout Itemize
\begin_inset Formula $U=12$
\end_inset
\end_layout
\begin_layout Standard
10 + 8 + 3 = 21, and
\begin_inset Formula $12\nmid21$
\end_inset
.
\begin_inset Formula $p'=1$
\end_inset
fails, because 10 + 8 + 3 > 12.
\begin_inset Formula $p'=\left\lceil \frac{\sum_{v\in V}q(v)}{U}\right\rceil $
\end_inset
works whether or not the sum is a multiple of
\begin_inset Formula $U$
\end_inset
.
Then we have 5, 4, 1 and two leftover slots to play with.
As before, at least one must go to
\begin_inset Formula $v_{3}$
\end_inset
, or we need 300 sheets to get the needed copies of
\begin_inset Formula $v_{3}$
\end_inset
.
200 sheets of 5, 4, 2 gives us 1000 of
\begin_inset Formula $v_{1}$
\end_inset
, 800 of
\begin_inset Formula $v_{2}$
\end_inset
, and 400 of
\begin_inset Formula $v_{3}$
\end_inset
, wasting 100 printed copies and 200 blank spaces, equivalent to 25 sheets
or $5.
Further improvement requires more leftovers than remain.
\end_layout
\begin_layout Standard
The key: for an imperfect solution, no one
\begin_inset Formula $p'$
\end_inset
is best for all versions.
You have to use
\begin_inset Formula $p'=\max\left\{ \left\lceil \frac{q(v)}{f(v)}\right\rceil |v\in V\right\} $
\end_inset
, which in turn tells us where to hand out leftovers.
\end_layout
\begin_layout Subsection
The general case
\end_layout
\begin_layout Standard
At the top level, we hand the one-form solver at most
\begin_inset Formula $U$
\end_inset
versions at a time (if we don't, you can easily have all
\begin_inset Formula $f$
\end_inset